n皇后问题java版_n皇后问题java代码

n皇后问题是一个典型的回溯算法的题目，就是在n*n的面板上，放n个皇后，每个皇后会攻击同一列和同一行还有两个斜边上的元素，问你放的方法，返回形式是一个List嵌套List，每个List里都是一种解决方案，每一个解决方案都是画一个面板，解决方案里的每一个元素都是每一个横行，如果没有放皇后，则以.来形容，如果放了皇后，以Q填充，在思想上肯定还是有一定难度的，先贴上java代码的实现，这里已经优化了很多，因为我们是一行一行来放的，所以在放入一行之后，这一行(执行方法isVaild时还没有往该行放Q的操作，所以此行是不可能有Q的存在的)以及这一行下面的所有行都是.，不存在有没有Q的存在，所以只需要判断现在的棋盘面板上的上方、左上方、右上方是否有Q的存在(isVaild实现)即可，这样看起来通俗易懂，当然这个思想是用了回溯算法，在每一个循环里面，先实施放Q的操作，在递归进去之后的一行代码，再将其还原，这就是回溯，因为有可能我们放到某一行之后，全部continue掉了，也就是此时遍历完当前行的所有列都没有找到一个合适的位置放皇后，相当于此路不通，所以我们要还原之前的现场，换一列重新递归，甚至这一行的所有列遍历完后，他的下一列还是无解，此时还要返回到更上面一行，这样就更有回溯的感觉了:

class Solution {
    List<List<String>> res = new ArrayList<List<String>>();//创建一个List[List用来存放最终结果并返回
    public List<List<String>> solveNQueens(int n) {
    char[][] borad = new char[n][n];//设置一个n*n的正方形char型数组
    for(char[] rchar: borad){//遍历二维数组的每一行
        Arrays.fill(rchar,'.');//填充每一行，棋盘初始化，开始都没有放皇后Q，直接.初始化
    }
    sovleQuestion(borad,0);//真正执行解决方案
return res;
    }
    public void sovleQuestion(char[][] borad,int row){
        int n = borad.length;//判断一下这个是几个皇后的问题，也就是棋盘的宽度
if(row==n){//如果n-1也便利完了，那么此时就会row==n，说明找到了一组解，将这个解放到返回的集合中
   res.add(charToList(borad)); //进行了将每一行char变为String的操作，返回一个List<String>并添加到List<List<String>>中
   return;//返回
}
for(int col = 0; col < n; col++){//进行每一列试探
if(!isValid(borad,row,col)){//判断这个位置是否能放Q
    continue;//不能放就到当前行的下一列
}
borad[row][col] = 'Q';//说明可以放，填入(做选择)
sovleQuestion(borad,row+1);//进行下一行的递归
borad[row][col] = '.';//撤销选择
}

    }
    public boolean isValid(char[][] board,int row, int col){
        for(int i = 0;i<row;i++){//判断当前元素的所有前面行的同列元素是否存在Q
            if(board[i][col] == 'Q'){
                return false;
            }
        }

        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){//判断左上方，所以行和列都是先减一
 if(board[i][j] == 'Q'){
                return false;
            }
        }
        for(int i = row-1,j=col+1;i>=0&&j<board[row].length;i--,j++){
 if(board[i][j] == 'Q'){//判断右上方是否有Q
                return false;
            }
        }

        return true;
    }
    public List<String> charToList(char[][] board){//数组变为List操作
        List<String> list = new ArrayList<String>();
        for(char[] rchar: board){
list.add(String.copyValueOf(rchar));
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54