52. N-Queens II.md

52. N-Queens II

---

leetcode-cn Daily Challenge on October 17th, 2020.

---

Difficulty : Hard

Related Topics : BackTracking

---

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

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.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

---

Solution

• mine
  • Java
    • Runtime: 1 ms, faster than 87.59%,Memory Usage: 36.4 MB, less than 61.56% of Java online submissions

      // O(N!)time
      // O(N)space
      int res = 0;
      public int totalNQueens(int n) {
          dfs(new int[n], 0, n);
          return res;
      }
      
      //pos[i]  mean we choose pos[i] in line i.
      //(i , pos[i])
      void dfs(int[] pos, int index, int n) {
          for (int i = 0; i < n; i++) {
              pos[index] = i;
              if (checkLegal(pos, index, i)) {
                  if (index + 1 == n) {
                      res++;
                  } else {
                      dfs(pos, index + 1, n);
                  }
              }
          }
      }
      
      boolean checkLegal(int[] pos, int index, int i) {
          for (int j = 0; j < index; j++) {
              if (pos[index] == pos[j]
                      || Math.abs(index - j) == Math.abs(pos[index] - pos[j])) {
                  return false;
              }
          }
          return true;
      }
      

---