Question Link

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

Question Description

Give a nn size of board, return all distinct solutions to the n-queens.

Input: n = 4
Output: [[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
*Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Simulation

Solution 1: Backtracking

If a Queen can be placed, it must satisfy below four conditions

Starting with an empty chessBoard (at Status 0), we place the queen at the first position of the first row(at Status 1). At the same time, we will mark all its row, column, and diagonal \ and diagonal / to True.
Then, we place second queen at the second available position, and again mark all its row, column and diagonal positions, and so on until we get size of count to n.
For backtracking steps, we need to re mark the queen position, and its row, column and diagonal back to false.

Thus, when we trying to place Queen at position (1,2). We will mark the entire row and entire column to true first.

For diagonal, we noticed that each record of diagonal \ has equivalent substraction.
(0,0)=0, (1,1)=0, (2,2)=0, (3,3)=0
Each record of diagonal / has equivalent sum.
(2,0)=2,(1,1)=2, (0,2)=2,
Thus, we mark all the record that has row-column = curRow-curColumn and all row has row+column = curRow+curColumn to True

Solution 2: Optimized Backtracking

The solution 1 can be optimized by having three additional 1-D array
Column Array | [0,1,2,3]
Diagonal Array / [0,1,2,3,4,5]
Diagonal Array \ [0,1,2,3,4,5]
In here, when place the Queen, we can mark the corresponding position to True

For example
When place Queen at position (1，2). We mark following position to True
Column Array

Diagonal Array / sum of col and row

Diagonal Array \ subscrtion of col and row

and when doing the backtracking, we will remove the value at those three array.

Implementation

Solution 2: Backtracking

public List < List < String >> solveNQueens(int n) {
    List < List < String >> ret = new ArrayList < > ();
    char[][] chessBoard = new char[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            chessBoard[i][j] = '.';
        }
    }
    boolean[] col = new boolean[n];
    boolean[] diag1 = new boolean[2 * n - 1];
    boolean[] diag2 = new boolean[2 * n - 1];
    backTracking(chessBoard, 0, n, ret, col, diag1, diag2);
    return ret;
}
private void backTracking(char[][] curr, int idx, int n, List < List < String >> ret, boolean[] col, boolean[] diag1, boolean[] diag2) {
    if (idx == n) {
        List < String > toAdd = new ArrayList < > ();
        for (int i = 0; i < n; i++) {
            toAdd.add(String.valueOf(curr[i]));
        }
        ret.add(toAdd);
        return;
    }
    for (int j = 0; j < n; j++) {
        if (col[j] || diag1[idx + n - j - 1] || diag2[idx + j]) {
            continue;
        }
        col[j] = true;
        diag1[idx + n - j - 1] = true;
        diag2[idx + j] = true;
        curr[idx][j] = 'Q';
        backTracking(curr, idx + 1, n, ret, col, diag1, diag2);
        curr[idx][j] = '.';
        col[j] = false;
        diag1[idx + n - j - 1] = false;
        diag2[idx + j] = false;
    }
}