leetCode-八皇后问题
为了使脑袋不生锈，偶尔还是需要给脑子运动一下。今天找了一个leetCode上的一个算法来运动一下。
题目是这样的：
在 8 X 8 的网格中，放入八个皇后（棋子），满足的条件是，任意两个皇后（棋子）都不能处于同一行、同一列或同一斜线上，问有多少种摆放方式？
如果有兴趣的同学可以先自己思考一下，这个题目应该如何做。在看可能会更有体会。因为主要不是代码，看的还是思路 所以就没有优化代码了，可能代码比较粗糙。进入正题：
题目描述的大概意思是，如何摆放八颗棋子是每颗棋子的上下左右 以及两边的正斜对角线上没有棋子出现。用图来描述就是
图1.jpeg
图2.jpeg
图1表示的是一个正确的，图二因为右下的斜线上出现了同样的一个所以是不符合条件。
首先说一下解题思路。因为是一个8*8的格子，又同时需要放八个棋子。所以我们第一个得到的信息是每一行有且仅有一个棋子。因为斜线部分影响的因素很多所以暂时是不能得到什么有效的讯息。如果我们首先就将斜线的部分都考虑进去的话。这个干扰因素就会越来越多到最后我们只能选择放弃。既然不能一下从全局解决这个问题那就只能将复杂问题简单化，先从局部开始着手。
首先我们从第一行开始分析，因为是第一个棋子所以在第一行什么位置都是可以的。但是为了后面的统一化，我们都是将棋子从最左边开始放。比如我们将第一个棋子放在（0，0）位置。注意我这里是将整个棋盘看成一个长度为8的二维数组。左上角为（0，0）位置。接下来我们在第二行的最左边放第二个棋子。注意这时候我们需要判断这个位置是否符合条件。也就是上下左右以及斜面都不能有棋子。就这样以此类推。这个复杂的问题就是：我在第每行放棋子的时候进行以此判断，如果不符合条件自动水平往右移动一位，继续判断。直到我在第八行找到合适的位置时，表示已经找到了一个符合条件的正确解。分析到这里，这个复杂的问题是不是就已经分解成，我只需要每次放棋子的时候判断棋子的位置时候符合条件的一个递归问题了。同时这个递归结束的条件就是在第八行找到合适的位置放下棋子就表示这一次寻找结束了。
注意
这里我们要注意一个问题：就是我们可能第一次放棋子的位置不对导致找不到最优解。这时我们还需要考虑 回溯问题 就是回退到上一个我们的位置继续寻找。这样才能保证找到所有的最优解。 接下来就是代码来演示了：
/**
在 8 X 8 的网格中，放入八个皇后（棋子），
满足的条件是，任意两个皇后（棋子）都不能处于同一行、同一列或同一斜线上，问有多少种摆放方式？
*/
public class Def {
public static int[][] checkerboard = new int[8][8];//棋盘
// 打印符合条件的棋子位置
public static void print(){
for(int i=0;i<checkerboard.length;i++){
for(int j=0;j<checkerboard[i].length;j++){
if(checkerboard[i][j] == 0){
System.out.print(checkerboard[i][j]+" ");
}else{
System.out.print(checkerboard[i][j]+" ");
}
}
System.out.println();
}
}
// 检查当前棋子的位置是否符合条件
public static Boolean check2(int x,int y){
if(x>7 || x<0 || y<0 || y >7) return false;
if(checkerboard[x][y] != 0 ) return false;
for(int i=0;i<8;i++){
if(checkerboard[x][i] != 0) return false;
}
for(int i=0;i<8;i++){
if(checkerboard[i][y] != 0) return false;
}
if(!recursion2(x-1,y-1,"leftTop")) return false;
if(!recursion2(x-1,y+1,"leftDown")) return false;
if(!recursion2(x+1,y+1,"rightDown")) return false;
if(!recursion2(x+1,y-1,"rightTop")) return false;
return true;
}
// 对斜线上的位置进行检查
public static Boolean recursion2(int x,int y,String direction){
Boolean flag = true;
switch (direction) {
case "leftTop":
while (x>=0 && y>=0){
if(checkerboard[x][y]!=0) {
flag = false;
return flag;
}
x--;
y--;
}
break;
case "leftDown":
while (x>=0 && y<=7){
if(checkerboard[x][y]!=0) {
flag = false;
return flag;
}
x--;
y++;
}
break;
case "rightTop":
while (x<=7 && y>=0){
if(checkerboard[x][y]!=0) {
flag = false;
return flag;
}
x++;
y--;
}
break;
case "rightDown":
while (x<=7 && y<=7){
if(checkerboard[x][y]!=0) {
flag = false;
return flag;
}
x++;
y++;
}
break;
}
return flag;
}
public static int count = 0;
public static void add2(int x){
// 满足条件的棋子条件
if(x == 8) {
count++;
print();
System.out.println("=============================");
return;
}
for(int i=0;i<8;i++){
if(check2(x,i)){
checkerboard[x][i] = 1;
x++;// 这里++是推动下一行
add2(x);
x--;// 注意这里很重要 这就是处理 回溯问题 需要会到上一次的位置
checkerboard[x][i] = 0;//将上一次的记录抹掉
}
}
}
public static void main(String[] args) {
add2(0);
System.out.println(count);
}
}
结果
整个过程大概就是这样了。代码部分的注释比较清楚，不明白的可以去看一下注释。
