八皇后问题：在8*8的棋盘上放置8个皇后，保证任意两个皇后之间不能相互攻击。（即没有两个皇后是在同一行、同一类、或者同一对角线上）
- 计算出8皇后或者N皇后可能的所有摆放结果。其中8皇后共计有92种不同的解。
- 打印显示出来其中的一种摆放结果或者所有的结果。
1. 回溯法：
回溯法：即试探法，系统的搜索所有解的方法。具体思想：从一条路往前走，能进则进，不能进则退出来，换条路再走。解决八皇后问题的经典算法。
伪代码如下：
- 将棋盘存到一个N*N的矩阵中（8*8），二维数组。
- 算法开始，清空棋盘，当前行设为第一行，当前列设为第一列。
- 在当前行当前列的位置是否满足条件：经过这一点的行、列、以及两条斜线上没有其他皇后。若满足：转到步骤4；若不满足，转到步骤5。
- 满足步骤3的条件：在当前位置放置一个皇后，分以下情况：
- 若当前行不是最后一行，当前行设为下一行， 当前列设为当前行的第一个待测位置(不一定是第一个位置)；转到步骤3。
- 如果是最后一行，记录下这个解。记录之后，若当前不是最后一列，当前列设为下一列；若当前列是最后一列，即最后一列，回溯，清空当前行，然后当前行设为上一行，当前列设为当前行的下一个待测位置。
- 不满足步骤3的条件，分以下情况：
- 如果当前列不是最后一列，当前列设为下一列，继续步骤3。
- 如果当前列是最后一列，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，继续步骤5。
算法改进：把棋盘存储为一个二维数组，然后需要在第i行第j列放置皇后时，根据问题的描述，首先判断是在第i行是否有皇后，由于每行只有一个皇后，这个判断也可以省略，然后判断第j列是否有皇后，这个也很简单，最后需要判断在同一斜线上是否有皇后，按照该方法需要判断两次，正对角线方向和负对角线方向。相对较为复杂。
若把棋盘存储为一个N维数组q[N]，数组中第i个元素的值代表第i行的皇后所在列的位置，这样便可以把问题的空间规模压缩为一维O(N)，在判断是否冲突时也很简单，首先每行只有一个皇后，且在数组中只占据一个元素的位置，行冲突就不存在了，其次是列冲突，判断一下是否有a[i]与当前要放置皇后的列j相等即可。至于斜线冲突，通过观察可以发现所有在斜线上冲突的皇后的位置都有规律即它们所在的行列互减的绝对值相等，即| row – i | = | col – a[i] | 。这样某个位置是否可以放置皇后的问题已经解决。
1. 递归实现
代码如下
//八皇后问题解法
public class Queen {
static int count=0; //统计解的个数
static int N = 8; //皇后个数：8
static int [] q = new int[N];
//大小为8的数组：数组下标表示：row，数组[i]对应内容：col。
public static void print()
{//打印解的坐标位置及图像
for(int i=0;i<N;i++)
System.out.println(i+" "+q[i]);
for(int i=0;i<N;i++)
{
System.out.print("|");
for(int j=0;j<N;j++)
{
if(j==q[i])
System.out.print("Q|");
else
System.out.print(" |");
}
System.out.println();
}
}
public static boolean canPlace(int i,int j)
{//判断坐标(i,j)处是否可以放置皇后
for(int k=0;k<i;k++)
{
if(q[k]==j||Math.abs(i-k)==Math.abs(j-q[k]))
return false;
}
return true;
}
public static void queen(int row)
{//递归，从第row行开始循环每一列
if(row==N)
{
count++;
if(count==1)
print();
}
else
{
for(int j=0;j<N;j++)
{
if(canPlace(row,j))
{
q[row]=j;
queen(row+1);
}
}
}
}
public static void main(String[] args) {
for(int i=0;i<N;i++) //初始化
{ q[i]=-1;}
queen(0);
System.out.println(count);
}
}
2. 非递归实现
public class Queen {
static int N=8;
static int[]q=new int[N];
static int count=0;
public static void print()
{
for(int i=0;i<N;i++)
System.out.println(i+" "+q[i]);
for(int i=0;i<N;i++)
{
System.out.print("|");
for(int j=0;j<N;j++)
{
if(j==q[i])
System.out.print("Q|");
else
System.out.print(" |");
}
System.out.println();
}
}
public static boolean canPlace(int i,int j)
{
for(int k=0;k<i;k++)
{
if(q[k]==j||Math.abs(i-k)==Math.abs(j-q[k]))
return false;
}
return true;
}
public static void queen()
{
int row=0,col=0;
while(row<N)
{
while(col<N)
{
if(canPlace(row,col))
{
q[row]=col;
col=0;
break;
}
else
{
++col;
}
}
if(col==N)//q[row]==-1
{
if(row==0)
break;
else
{
--row;
col=q[row]+1;
q[row]=-1; //把上一行皇后的位置清除，重新探测
continue;
}
}
if(row==N-1)
{
count++;
if(count==1)
print();
col=q[row]+1;
q[row]=-1;
continue;
}
++row;
}
}
public static void main(String[] args) {
for(int i=0;i<N;i++)//初始化
q[i]=-1;
queen();
System.out.println(count);
}
}
网友评论