N-Queens

描述

The n-queens puzzle is the problem of placing n queens on an n × n chessboard such that no two queens attack each other.

Eight Queens

Figure: Eight Queens

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,There exist two distinct solutions to the 4-queens puzzle:

  1. [
  2.  [".Q..",  // Solution 1
  3.   "...Q",
  4.   "Q...",
  5.   "..Q."],
  7.  ["..Q.",  // Solution 2
  8.   "Q...",
  9.   "...Q",
  10.   ".Q.."]
  11. ]

分析

经典的深搜题。

设置一个数组 vector<int> C(n, 0), C[i] 表示第i行皇后所在的列编号，即在位置 (i, C[i])上放了一个皇后，这样用一个一维数组，就能记录整个棋盘。

代码1

  1. // N-Queens
  2. // 深搜+剪枝
  3. // 时间复杂度O(n!*n)，空间复杂度O(n)
  4. public class Solution {
  5.     public List<List<String>> solveNQueens(int n) {
  6.         List<List<String>> result = new ArrayList<>();
  7.         int[] C = new int[n]; // C[i]表示第i行皇后所在的列编号
  8.         dfs(C, 0, result);
  9.         return result;
  10.     }
  11.     private static void dfs(int[] C, int row, List<List<String>> result) {
  12.         final int N = C.length;
  13.         if (row == N) { // 终止条件，也是收敛条件，意味着找到了一个可行解
  14.             List<String> solution = new ArrayList<>();
  15.             for (int i = 0; i < N; ++i) {
  16.                 char[] charArray = new char[N];
  17.                 Arrays.fill(charArray, '.');
  18.                 for (int j = 0; j < N; ++j) {
  19.                     if (j == C[i]) charArray[j] = 'Q';
  20.                 }
  21.                 solution.add(new String(charArray));
  22.             }
  23.             result.add(solution);
  24.             return;
  25.         }
  27.         for (int j = 0; j < N; ++j) {  // 扩展状态，一列一列的试
  28.             final boolean ok = isValid(C, row, j);
  29.             if (!ok) continue;  // 剪枝，如果非法，继续尝试下一列
  30.             // 执行扩展动作
  31.             C[row] = j;
  32.             dfs(C, row + 1, result);
  33.             // 撤销动作
  34.             // C[row] = -1;
  35.         }
  36.     }
  38.     /**
  39.      * 能否在 (row, col) 位置放一个皇后.
  40.      *
  41.      * @param C 棋局
  42.      * @param row 当前正在处理的行，前面的行都已经放了皇后了
  43.      * @param col 当前列
  44.      * @return 能否放一个皇后
  45.      */
  46.     private static boolean isValid(int[] C, int row, int col) {
  47.         for (int i = 0; i < row; ++i) {
  48.             // 在同一列
  49.             if (C[i] == col) return false;
  50.             // 在同一对角线上
  51.             if (Math.abs(i - row) == Math.abs(C[i] - col)) return false;
  52.         }
  53.         return true;
  54.     }
  55. }

代码2

  1. // N-Queens
  2. // 深搜+剪枝
  3. // 时间复杂度O(n!)，空间复杂度O(n)
  4. public class Solution {
  5.     public List<List<String>> solveNQueens(int n) {
  6.         this.columns = new boolean[n];
  7.         this.main_diag = new boolean[2 * n - 1];
  8.         this.anti_diag = new boolean[2 * n - 1];
  10.         List<List<String>> result = new ArrayList<>();
  11.         int[] C = new int[n];
  12.         Arrays.fill(C, -1); // C[i]表示第i行皇后所在的列编号
  13.         dfs(C, 0, result);
  14.         return result;
  15.     }
  18.     private void dfs(int[] C, int row, List<List<String>> result) {
  19.         final int N = C.length;
  20.         if (row == N) { // 终止条件，也是收敛条件，意味着找到了一个可行解
  21.             List<String> solution = new ArrayList<>();
  22.             for (int i = 0; i < N; ++i) {
  23.                 char[] charArray = new char[N];
  24.                 Arrays.fill(charArray, '.');
  25.                 for (int j = 0; j < N; ++j) {
  26.                     if (j == C[i]) charArray[j] = 'Q';
  27.                 }
  28.                 solution.add(new String(charArray));
  29.             }
  30.             result.add(solution);
  31.             return;
  32.         }
  34.         for (int j = 0; j < N; ++j) {  // 扩展状态，一列一列的试
  35.             final boolean ok = !columns[j] && !main_diag[row - j + N - 1]  &&
  36.                     !anti_diag[row + j];
  37.             if (!ok) continue;  // 剪枝，如果非法，继续尝试下一列
  38.             // 执行扩展动作
  39.             C[row] = j;
  40.             columns[j] = main_diag[row - j + N - 1] = anti_diag[row + j] = true;
  41.             dfs(C, row + 1, result);
  42.             // 撤销动作
  43.             // C[row] = -1;
  44.             columns[j] = main_diag[row - j + N - 1] = anti_diag[row + j] = false;
  45.         }
  46.     }
  47.     // 这三个变量用于剪枝
  48.     private boolean[] columns;  // 表示已经放置的皇后占据了哪些列
  49.     private boolean[] main_diag;  // 占据了哪些主对角线
  50.     private boolean[] anti_diag;  // 占据了哪些副对角线
  51. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/dfs/n-queens.html