回溯——棋盘问题——N皇后

回溯——棋盘问题——N皇后

51. N 皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

 

解题思路：回溯 

我们可以将棋盘的 ‘行’ 看作回溯的横向for循环，棋盘的 ‘列’ 看作回溯的纵向递归，N皇后问题便可以转化成如下的树形结构。

代码实现和提交结果如下： 

class Solution {
    public static List> solveNQueens(int n) {
        List> res = new ArrayList<>();
        char[][] queenList = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(queenList[i],'.');
        }
        backTracking(0,n,res,queenList);
        return res;
    }
    private static void backTracking(int row , int n , List> res ,char[][] queenList){
        if(row == n){
            res.add(change(queenList));
            return;
        }
        for(int col = 0 ; col < n ; col++){
            if(isValue(row,col,queenList)){
                queenList[row][col] = 'Q';
                backTracking(row+1,n,res,queenList);
                queenList[row][col] = '.';
            }
        }
    }
    private static boolean isValue(int row , int col , char[][] queenList){
        //检查列
        for(int i = 0 ; i < row ; i++){
            if(queenList[i][col] == 'Q'){
                return false;
            }
        }
        //检查45度
        for(int i = row - 1,j = col - 1 ; i >= 0 && j >= 0; i--,j--){
            if(queenList[i][j] == 'Q'){
                return false;
            }
        }
        //检查135度
        for(int i = row - 1, j = col + 1 ; i >= 0 && j <= queenList.length - 1;i--,j++){
            if(queenList[i][j] == 'Q'){
                return false;
            }
        }
        return true;
    }
    private static List change(char[][] queenList){
        List res = new ArrayList();
        for(int i = 0 ; i < queenList.length ; i++){
            char[] temp = queenList[i];
            String s = String.copyValueOf(temp);
            res.add(s);
        }
        return res;
    }
}

 总结：主要还是放皇后的判断问题，不能同行，不能同列，不能斜。