N皇后问题
时间限制:
5秒
内存限制:
64M
N皇后问题是一个古老而经典的题目。该问题源自数学家高斯1850年提出八皇后问题:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任
意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
例如,在一个4x4的棋盘上,摆放4个皇后有两种方法,
用文本方式输出为
* Q * *
* * * Q
Q * * *
* * Q *
* * Q *
Q * * *
* * * Q
* Q * *
我们可以用一维整数数组Q[]来表示N个皇后的摆放位置,例如,对4皇后问题的第一个解可以表示
为,Q[0]=1,Q[1]=3,Q[2]=0,Q[3]=2。
当我们逐渐往棋盘上放置皇后时,用这种表示方法,可以做如下的判断来检查新放入的皇后的位置k是否可行:
1、如果Q[i]==Q[k],则有两个皇后在同一列,不可行;
2、如果Q[i]-Q[k]==(i-k),则有两个皇后在对角线上相互攻击,不可行;
3、如果Q[k]-Q[i]==(i-k),则有两个皇后在反对角线上相互攻击,不可行;
本题要求你按顺序输出N皇后问题的解。
输入:
棋盘的阶数N
输出:
对应的N皇后问题的解,请按照顺序输出。顺序可参考后面给出的参考解答。
样例输入:
4
样例输出:
*□
Q□
*□
*□
↵
*□
*□
*□
Q□
↵
Q□
*□
*□
*□
↵
*□
*□
Q□
*□
↵
↵
*□
*□
Q□
*□
↵
Q□
*□
*□
*□
↵
*□
*□
*□
Q□
↵
*□
Q□
*□
*□
↵
↵
import java.util.Scanner;
public class Main{
public static boolean Place(int Q[],int k) //考察皇后k放置在Q[k]列是否发生冲突
{
for(int i=1; i<k; i++)
{
if (Q[i]==Q[k]||Q[i]-Q[k]==(i-k)||Q[k]-Q[i]==(i-k))
return false;
}
return true;
}
public static void Queen(int n)
{
int Q[]=new int[n+1];
for (int i=1; i<=n; i++)//初始化
Q[i]=0;
int k=1;
while (k>=1)
{
Q[k]=Q[k]+1;//在下一列放置第k个皇后
while (Q[k]<=n&&!Place(Q,k))
Q[k]=Q[k]+1;//如果不符合条件,搜索下一列
if (Q[k]<=n && k==n)
{
boolean[][] bl = new boolean[n][n];
for (int i=1; i<=n; i++){
bl[i-1][Q[i]-1]=true;
}
for(int l=1;l<=n;l++){
for(int c=1;c<=n;c++){
if(bl[l-1][c-1]==true)
System.out.print("Q ");
else
System.out.print("* ");
}
System.out.println();
}
System.out.println();
}
else if (Q[k]<=n && k<n)
k=k+1; //放置下一个皇后
else {
Q[k]=0; //重置Q[k],回溯
k=k-1;
}
}
}
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
Queen(n);
}
}
附上论坛里最快的解法:http://www.iteye.com/topic/20059
分享到:
相关推荐
n 皇后问题是一道经典的回溯算法问题,其目标是在一个 � × � n×n 的棋盘上放置 � n 个皇后,使得任意两个皇后都不能在同一行、同一列或同一斜线上。 栈可以用来辅助实现回溯算法,本质上就是手动维护了递归...
n皇后问题C++源码。{典型的8皇后问题的扩展)
n皇后问题代码 回溯法 递归回溯 算法设计与分析
n皇后问题 Very Goodn皇后问题的求解n皇后问题的求解
使用分支限界法解决N皇后问题。因为是广度优先,而且占用比较多的额外空间,所以并不是解N皇后问题的很好的算法,主要是理解分支限界法的使用。
n皇后问题的没有同义的解。用java语言实现n-queens算法
在一个N×N的国际象棋棋盘中摆N个皇后,使这N个皇后不能互相被对方吃掉。N皇后问题摆法算法描述
算法设计作业,用c++编写的,回溯法求解n皇后问题 运行环境VC6.0
N皇后问题解法,采用队列分支限界算法。c++编程。
N皇后问题的3种实现方案
C语言实现的,用栈的n皇后问题源码+流程图 深度优先遍历
这个可以查看到所有n皇后问题的输出和计数~~
人工智能-CSP最小冲突法解决n皇后问题,(中国地质大学,计算机学院~~)
人工智能 N皇后问题 MFC
本程序是用C语言编写的N皇后问题(回溯法)
n皇后问题的三种算法,n^n穷举,n!穷举,回溯法,比较它们的效率
用java语言实现N皇后问题: 基本思路:X(j)表示一个解的空间,j表示行数,里面的值表示可以放置在的列数,抽象约束条件得到能放置一个皇后的约束条件(1)X(i)!=X(k);(2)abs(X(i)-X(k))!=abs(i-k)。应用回溯法,当可以...
八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个...八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。
本压缩包包含5个文档,都是关于用回溯法解决n皇后问题的。每一个文档都包含详细代码。
四、八、N皇后问题(数据结构C语言) 比较完善