LeetCode

52. N皇后 II

返回n皇后不同的解决方案的数量。不需要返回真正的解，更简单一些。

  1. int solutionCount = 0;
  2. int n;
  3. int[] columns;
  4. int[] diagonals1;
  5. int[] diagonals2;
  7. public int totalNQueens(int n) {
  8.     this.n = n;
  9.     columns = new int[n];
  10.     //i+j
  11.     diagonals1 = new int[2*n-1];
  12.     //j-i
  13.     diagonals2 = new int[2*n-1];
  14.     backtrack(0);
  15.     return solutionCount;
  16. }
  17. private void backtrack(int r) {
  18.     if (r == n) {
  19.         solutionCount++;
  20.         return ;
  21.     }
  22.     for (int c = 0; c < n; c++) {
  23.         if (!legal(r, c))   continue;
  24.         place(r, c, 1);
  25.         backtrack(r + 1);
  26.         place(r, c, 0);
  27.     }
  28. }
  29. private boolean legal(int r, int c) {
  30.     return columns[c] == 0 && diagonals1[r + c] == 0 && diagonals2[c - r + n - 1] == 0;
  31. }
  32. private void place(int r, int c, int target) {
  33.     columns[c] = target;
  34.     diagonals1[r + c] = target;
  35.     diagonals2[c - r + n - 1] = target;
  36. }