简单八皇后问题java一维数组递归
八皇后:
8*8的方格中放8个皇后,八个皇后不能再同一行同一列和同一条对角线反对角线上。
注意:
1.这个代码没有用回溯思想,只能输出一个八皇后的解。
2.只用了一个一维数组储存列号,并没有出现二维数组,实际上没有用到棋盘
3.check方法检验位置是否合法要看懂,下面有详细注释
4.递归那里,自己设置一个断点去追踪过程,看了过程就懂了,注意递归的时候如果8列走完了还没有合适的位置他就会跳回上一行去更改上一行的皇后放置的位置。这是这里为什么要用到递归的最大原因,要是写循环往前挪会死的…
5.之前写的代码一直爆栈,应该是哪里写错了,但是还是没有找到具体位置。这也是用递归的一个尴尬的地方,首先理解递归就不容易了,理解了要写出来更不容易,写出来要写对更更不容易,如果递归太深了爆栈爆内存了吧,还得怀疑一下到底是自己写的要问题还是分配的不够…
/*算法思想:
* 8*8的方格从每一行开始向下填,建一个一维数组,代表每一行,数组里存的内容是每一行皇后所在的列号(行列号均是从0到7)
* 方法:一个check检查是否同列,同对角线,同反对角线。一个search递归寻找八皇后的位置。一个paint打印结果
*/
public class bahuanghou{
public static void main(String[] args) {
// TODO 自动生成的方法存根
bahuanghou queen= new bahuanghou(); //new一个八皇后的对象
queen.search(0); //调用方法开始递归
paint(); //打印八皇后
}
public static final int SIZE = 8;
private static int[] queens=new int[SIZE]; //queens代表行,数组内存放每一行的列号
private boolean check(int row ,int column) {
for(int i=1;i<=row;i++) //检查第row行的列号是否重复,对角线反对角线上是否有其他元素
//已知queens[row]=column, 三种皇后不能放置的情况数学表达式意义:
//1.距row行i个单位的行的列号为column,也就是上面的竖线,2.row行以前i个单位的行列号也比row前i个单位,即左上的对角线。3.row行以后i个单位的行,列号比row后i个单位,也就是右上对角线
if(queens[row-i]==column||queens[row-i]==column-i||queens[row-i]==i+column)
return false;
return true;
}
private boolean search(int row) {
if(row==SIZE) //填满8行后就退出了
return true;
for(int column = 0;column<SIZE;column++) {
//没填满8行,就继续填。每一行从第0列开始尝试,检查是否符合条件,不符合就下一列。
//走满了8列之后还是没有合适的位置,就会return false, 之后再返回到上一行的column,循环上一行column,把上一行的皇后移动位置继续递归.....继续循环,一行填好了就下一行
queens[row]=column;
if(check(row,column)&&search(row+1))
{
return true;
}
}
return false;
}
public static void paint() {
char[][] x= new char[SIZE][SIZE];
for(int i=0;i<SIZE;i++)
{
System.out.print(queens[i]+" ");
for(int j=0;j<SIZE;j++)
{
System.out.print("|");
if(queens[i]==j)
System.out.print("Q");
else
System.out.print("-");
}
System.out.print("|");
System.out.print("\n");
}
}
}
输出结果:
This is my first colorful code snippet in CSDN .