P233 N 皇后问题

描述#

这个题目说的是，给你一个整数 n，你要返回 n 皇后问题的所有解。其中，每个解是一个棋盘布局，用字符 'Q' 表示一个皇后，用字符 '.' 表示一个空位置。

n 皇后问题的定义是，你要把 n 个皇后放到一个 n x n 的棋盘上，使得任意两个皇后之间都不能互相攻击，也就是说任意两个皇后不能位于同一行、同一列以及同一斜线。

比如说，给你的 n 等于 4。
4 皇后问题有以下两个解：
[
[
".Q..",
"...Q",
"Q...",
"..Q."
],
[
"..Q.",
"Q...",
"...Q",
".Q.."
]
]

代码#

public class AlgoCasts {

  private List<String> buildList(char[][] board) {
    List<String> list = new ArrayList<>();
    for (char[] row: board)
      list.add(new String(row));
    return list;
  }

  private void solve(int row, int n, List<List<String>> result,
                     char[][] board, boolean[][] visited) {
    if (row == n) {
      result.add(buildList(board));
      return;
    }
    for (int col = 0; col < n; ++col) {
      if (!visited[0][col] && !visited[1][row-col+n] && !visited[2][row+col]) {
        board[row][col] = 'Q';
        visited[0][col] = visited[1][row-col+n] = visited[2][row+col] = true;
        solve(row+1, n, result, board, visited);
        visited[0][col] = visited[1][row-col+n] = visited[2][row+col] = false;
        board[row][col] = '.';
      }
    }
  }

  // Time: O(n!), Space: O(n^2)
  public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    boolean[][] visited = new boolean[3][2*n];
    char[][] board = new char[n][n];
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        board[i][j] = '.';
    solve(0, n, result, board, visited);
    return result;
  }

}