回溯算法经典题目之 N 皇后

 关注

“脚本之家

”，与百万开发者在一起

提到回溯算法那肯定离不开 n 皇后这道算法题，它实在是太经典了。

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

皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

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

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

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]]
解释：4 皇后问题存在两个不同的解法。

我觉得你应该能够结合视频动画和保姆级别的代码注释把这道题目弄清楚。

class Solution {

    // 保存所有符合要求的解
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
      
      // attack 用来表示皇后的攻击范围
      int[][] attack = new int[n][n];
      // queen 用来记录皇后的位置
      char[][] queen = new char[n][n];

      // 初始化二维数组 queen 中所有的元素为 '.'
      for(char[] c : queen) {
         Arrays.fill(c, '.');
      }

      // 初始化二维数组 attack 中所有的元素为 0
      // 0 代表没有皇后能攻击得到
      // 1 代表出于任意一个皇后的攻击范围内
      for(int[] c : attack) {
          Arrays.fill(c, 0);
      }

      // 从棋盘的第 0 行第 0 列处理 n 皇后的情况
      backtrack(0,n,queen,attack);

      // 最后，返回所有符合要求的解
      return res;
    }

    // 很显然，每一行只能放置一个皇后，所以我们每一行每一行的来放置皇后
    // k 表示当前处理的行
    // n 表示需要放置多少个皇后，同时也代表棋盘的大小为 n * n
    // queen 用来记录皇后的位置
    // attack 用来表示皇后的攻击范围
    private void backtrack(int k ,int n , char[][] queen,int[][] attack){

        // 如果发现在棋盘的最后一行放置好了皇后，那么就说明找到了一组符合要求的解
        if(k == n){
            // 由于 queen 为二维字符数组，所以需要转换为字符串数组
            List<String> list = new ArrayList<>();
            // 遍历二维数组 queen
            // 取出 queen 的每一行字符数组 c
            for (char[] c : queen) {
                // 把字符数组 c 中的所有字符转换为字符串的形式进行拼凑
                // 比如 ['.','Q','.','.',]
                // 转换为 '.Q..'
                // 把这个字符串加入到 list 中
                list.add(String.copyValueOf(c));
            }

            // list 即为一组符合要求的解，把它加入到结果数组中
            res.add(list);
            // 由于遍历完了所有的行，无需再遍历下去，所以返回
            return;
        }

        // 每一行只能放置一个皇后
        // 并且每一列也只能放置一个皇后
        // 所以在 k 行中，从 0 列到 n - 1 列，判断皇后应该放置到哪个位置
        for(int i = 0 ; i < n ; i++){
            // 如果发现 attack[k][i] == 0
            // 说明这个位置不在任何一个皇后的攻击范围内
            // 所以可以考虑放置皇后
            if(attack[k][i] == 0){

                // 如果在 ( k , i ) 位置放置了皇后，那么就需要考虑在 k + 1 行应该怎么放置其它的皇后了
                // 由于有可能在( k , i )  位置放置了皇后之后，在后续的其它行会无法再放置其它的皇后
                // 那么就需要回到 ( k , i )  的状态，考虑能不能在 ( k , i + 1 )的位置放置
                // 为了能够回到 ( k , i )  的状态，所以需要先记录此时的 attack
                // 使用一个临时的二维数组，深度拷贝 attack
                // 如果不使用深度拷贝，而是直接使用 int[][] temp = c
                // 会导致 attack 发生改变是 temp 也会发生改变
                // 这样也就无法保存之前的状态了
                int[][] temp = new int[n][n];
                
                // 通过两个 for 循环，把 attack 中的所有元素深度拷贝到 temp
                for(int l = 0 ; l < n ; l++){
                    for( int m = 0 ; m < n ; m++){
                        temp[l][m] = attack[l][m];
                    }
                }

                // queen 用来记录皇后的位置
                // 那么 ( k , i )  的位置 queen[k][i] = 'Q'
                queen[k][i] = 'Q';

                // 由于新放置了一个皇后，所以攻击范围又更多了
                // 所以需要更新 attack 数组
                // 新放置皇后的坐标为 ( k , i ) ，同样的需要更新它的八个方向
                checkQueenAttack(k,i,attack);
                
                // 如果在 ( k , i )  位置放置了皇后，那么就需要考虑在 k + 1 行应该怎么放置其它的皇后
                // 递归的调用 backtrack 在 k + 1 行放置皇后
                backtrack(k + 1,n,queen,attack);
                
                // 递归结束后，拿走皇后，恢复 attack 的状态，考虑能不能在 ( k ,i + 1 )的位置放置
                attack = temp;

                // 恢复 queen 的状态，说明此时皇后不放置在( k , i )  位置
                queen[k][i] = '.';
            }
        }


    }

    // 坐标 ( x , y) 为皇后所处的位置
    // 更新 attack
    private void checkQueenAttack(int x ,int y,int[][] attack){

        // 对于每一个坐标 (x,y) 来说，都有上、下、左、右、左上、左下、右上、右下 八个方向
        //【左上】的坐标为 (x - 1, y - 1)
        //【上】的坐标为 (x - 1, y )
        //【右上】的坐标为 (x + 1, y + 1)
        //【左】的坐标为 (x, y + 1)
        //【右】的坐标为 (x , y - 1)
        //【左下】的坐标为 (x + 1, y - 1)
        //【下】的坐标为 (x + 1, y)
        //【右下】的坐标为 (x + 1, y + 1)
        // 通过两个一维数组可以表示这八个方向
        // dx 表示 x 的方向
        int dx[] = { -1 , -1 , -1 , 0  ,  0 ,  1  , 1 , 1 };
        // dy 表示 y 的方向
        int dy[] = { -1 , 0  , 1 , -1 ,  1 ,  -1 , 0 , 1 };

        // 皇后所处的坐标肯定是皇后能攻击的位置，设置为 1
        attack[x][y] = 1;

        // 以坐标 ( x , y) 为中心，去更新它八个方向的坐标
        for(int j = 0 ; j < 8; j++){
            // 由内向外的进行更新
            for(int i = 1 ; i < attack.length ; i++){
                // 新的位置的坐标行为 x + i * dx[j]
                int nx = x + i * dx[j];
                // 新的位置的坐标列为 y + i * dy[j]
                int ny = y + i * dy[j];

                // 如果新位置的坐标在 n * n 的棋盘范围内
                if(nx >= 0 && nx < attack.length && ny >= 0 && ny < attack.length){
                    // 那么这些位置就是在坐标为 （x，y）的皇后的攻击范围内，更新为 1
                    attack[nx][ny] = 1;
                }

            }
        }
    }
}