N皇后

51. N皇后

题目描述

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

ANUzjA.png

上图为 8 皇后问题的一种解法。

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

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

示例：

  1. 输入: 4
  2. 输出: [
  3.  [".Q..",  // 解法 1
  4.   "...Q",
  5.   "Q...",
  6.   "..Q."],
  8.  ["..Q.",  // 解法 2
  9.   "Q...",
  10.   "...Q",
  11.   ".Q.."]
  12. ]
  13. 解释: 4 皇后问题存在两个不同的解法。

问题分析

约束条件为每个棋子所在的行、列、对角线都不能有另一个棋子。

使用一维数组表示一种解法，下标（index）表示行，值（value）表示该行的Q（皇后）在哪一列。
每行只存储一个元素，然后递归到下一行，这样就不用判断行了，只需要判断列和对角线。

Solution1

当result[row] = column时，即row行的棋子在column列。

对于[0, row-1]的任意一行（i 行），若 row 行的棋子和 i 行的棋子在同一列，则有result[i] == column;
若 row 行的棋子和 i 行的棋子在同一对角线，等腰直角三角形两直角边相等，即 row - i == Math.abs(result[i] - column)

布尔类型变量 isValid 的作用是剪枝，减少不必要的递归。

  1. public List<List<String>> solveNQueens(int n) {
  2.     // 下标代表行，值代表列。如result[0] = 3 表示第1行的Q在第3列
  3.     int[] result = new int[n];
  4.     List<List<String>> resultList = new LinkedList<>();
  5.     dfs(resultList, result, 0, n);
  6.     return resultList;
  7. }
  9. void dfs(List<List<String>> resultList, int[] result, int row, int n) {
  10.     // 递归终止条件
  11.     if (row == n) {
  12.         List<String> list = new LinkedList<>();
  13.         for (int x = 0; x < n; ++x) {
  14.             StringBuilder sb = new StringBuilder();
  15.             for (int y = 0; y < n; ++y)
  16.                 sb.append(result[x] == y ? "Q" : ".");
  17.             list.add(sb.toString());
  18.         }
  19.         resultList.add(list);
  20.         return;
  21.     }
  22.     for (int column = 0; column < n; ++column) {
  23.         boolean isValid = true;
  24.         result[row] = column;
  25.         /*
  26.          * 逐行往下考察每一行。同列，result[i] == column
  27.          * 同对角线，row - i == Math.abs(result[i] - column)
  28.          */
  29.         for (int i = row - 1; i >= 0; --i) {
  30.             if (result[i] == column || row - i == Math.abs(result[i] - column)) {
  31.                 isValid = false;
  32.                 break;
  33.             }
  34.         }
  35.         if (isValid) dfs(resultList, result, row + 1, n);
  36.     }
  37. }

Solution2

使用LinkedList表示一种解法，下标（index）表示行，值（value）表示该行的Q（皇后）在哪一列。

解法二和解法一的不同在于，相同列以及相同对角线的校验。 将对角线抽象成【一次函数】这个简单的数学模型，根据一次函数的截距是常量这一特性进行校验。

这里，我将右上-左下对角线，简称为“\”对角线；左上-右下对角线简称为“/”对角线。

“/”对角线斜率为1，对应方程为y = x + b，其中b为截距。
对于线上任意一点，均有y - x = b，即row - i = b;
定义一个布尔类型数组anti_diag，将b作为下标，当anti_diag[b] = true时，表示相应对角线上已经放置棋子。
但row - i有可能为负数，负数不能作为数组下标，row - i 的最小值为-n（当row = 0，i = n时），可以加上n作为数组下标，即将row -i + n 作为数组下标。
row - i + n 的最大值为 2n（当row = n，i = 0时），故anti_diag的容量设置为 2n 即可。

ANXG79.png

“\”对角线斜率为-1，对应方程为y = -x + b，其中b为截距。
对于线上任意一点，均有y + x = b，即row + i = b;
同理，定义数组main_diag，将b作为下标，当main_diag[row + i] = true时，表示相应对角线上已经放置棋子。

有了两个校验对角线的数组，再来定义一个用于校验列的数组cols，这个太简单啦，不解释。

解法二时间复杂度为O(n!)，在校验相同列和相同对角线时，引入三个布尔类型数组进行判断。相比解法一，少了一层循环，用空间换时间。

  1. List<List<String>> resultList = new LinkedList<>();
  3. public List<List<String>> solveNQueens(int n) {
  4.     boolean[] cols = new boolean[n];
  5.     boolean[] main_diag = new boolean[2 * n];
  6.     boolean[] anti_diag = new boolean[2 * n];
  7.     LinkedList<Integer> result = new LinkedList<>();
  8.     dfs(result, 0, cols, main_diag, anti_diag, n);
  9.     return resultList;
  10. }
  12. void dfs(LinkedList<Integer> result, int row, boolean[] cols, boolean[] main_diag, boolean[] anti_diag, int n) {
  13.     if (row == n) {
  14.         List<String> list = new LinkedList<>();
  15.         for (int x = 0; x < n; ++x) {
  16.             StringBuilder sb = new StringBuilder();
  17.             for (int y = 0; y < n; ++y)
  18.                 sb.append(result.get(x) == y ? "Q" : ".");
  19.             list.add(sb.toString());
  20.         }
  21.         resultList.add(list);
  22.         return;
  23.     }
  24.     for (int i = 0; i < n; ++i) {
  25.         if (cols[i] || main_diag[row + i] || anti_diag[row - i + n])
  26.             continue;
  27.         result.add(i);
  28.         cols[i] = true;
  29.         main_diag[row + i] = true;
  30.         anti_diag[row - i + n] = true;
  31.         dfs(result, row + 1, cols, main_diag, anti_diag, n);
  32.         result.removeLast();
  33.         cols[i] = false;
  34.         main_diag[row + i] = false;
  35.         anti_diag[row - i + n] = false;
  36.     }
  37. }