Question Link

https://leetcode.com/problems/n-queens-ii/

Question Description

Give a nn size of board, return number of distinct solutions to the n-queens.
image.png
Input: n = 4
Output: 2
*Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Simulation

Refer to Leetcode 51 N-Queens

Implementation

  1. int res = 0;
  2. public int totalNQueens(int n) {
  3.     //List < List < String >> ret = new ArrayList < > ();
  4.     char[][] chessBoard = new char[n][n];
  5.     for (int i = 0; i < n; i++) {
  6.         for (int j = 0; j < n; j++) {
  7.             chessBoard[i][j] = '.';
  8.         }
  9.     }
  10.     boolean[] col = new boolean[n];
  11.     boolean[] diag1 = new boolean[2 * n - 1];
  12.     boolean[] diag2 = new boolean[2 * n - 1];
  13.     backTracking(chessBoard, 0, n, col, diag1, diag2);
  14.     return res;
  15. }
  17. private void backTracking(char[][] curr, int idx, int n, boolean[] col, boolean[] diag1, boolean[] diag2) {
  18.     if (idx == n) {
  19.         res++;
  20.         return;
  21.     }
  23.     for (int j = 0; j < n; j++) {
  24.         if (col[j] || diag1[idx + n - j - 1] || diag2[idx + j]) {
  25.             continue;
  26.         }
  27.         col[j] = true;
  28.         diag1[idx + n - j - 1] = true;
  29.         diag2[idx + j] = true;
  30.         curr[idx][j] = 'Q';
  31.         backTracking(curr, idx + 1, n, col, diag1, diag2);
  32.         curr[idx][j] = '.';
  33.         col[j] = false;
  34.         diag1[idx + n - j - 1] = false;
  35.         diag2[idx + j] = false;
  36.     }
  37. }