P237 N 皇后问题解的数量

描述#

这个题目说的是，给你一个整数 n，你要计算出 n 皇后问题解的数量。

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

比如说，给你的 n 等于 4。
4 皇后问题有两个解，因此你要返回 2。

相关视频：N 皇后问题

代码#

public class AlgoCasts {

  private void solve(int row, int n, int[] cnt, boolean[][] visited) {
    if (row == n) {
      ++cnt[0];
      return;
    }
    for (int col = 0; col < n; ++col) {
      if (!visited[0][col] && !visited[1][row-col+n] && !visited[2][row+col]) {
        visited[0][col] = visited[1][row-col+n] = visited[2][row+col] = true;
        solve(row+1, n, cnt, visited);
        visited[0][col] = visited[1][row-col+n] = visited[2][row+col] = false;
      }
    }
  }

  // Time: O(n!), Space: O(n)
  public int totalNQueens(int n) {
    int[] cnt = new int[]{0};
    boolean[][] visited = new boolean[3][2*n];
    solve(0, n, cnt, visited);
    return cnt[0];
  }

}