[Leetcode] N-Queens

A complicated backtracking problem in matrix form.

Description

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

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Examples

Example 1:

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

Example 2:

Input: n = 1
Output: [["Q"]]

Solution

There are 3 directions to check if queens on board are conforming rules — vertical(r) / horizontal(c) / diagonal(X), only 1 queen can exist in line. The design of DFS would forward row by row. Within current row, iteratively check col is valid to use, and forward to r+1 if okay.

# design of DFS
. . . .
^  -> dfs(r, container)
for c in n
    if check okay
        dfs(r+1, container with c stored)
. . . .      |
^          < -
. . . .
. . . .

Here the container schema is important. We may call it q_cols representing col of queen at row so far. e.g. q_cols [1, 3] means (0, 1), (1, 3) are stored queen choices. Therefore, though in a form of array, the q_cols implies two dimensional info, and can be used to generate final res.

Another issue is how do we check if curr col is valid to push. Here compare col with q_cols to see if col will not conflict stored ones.

For row walked (according to q_cols), consider 3 directions
# vertical(r): need no check as DFS ensures only one chosed per r
# horizontal(c): traverse q_cols to search if target col used
# diagonal(gradient): the tricky part, ra-rb==|ca-cb| would be same for each point on same siagonal line

If curr col is okay to used, append it into q_cols and forward to r+1. For other col in same row may also be possible, backtrack q_cols after DFS, so q_cols remain the same state when checking next ro.

• code

ref: https://programs.programmingoneonone.com/2021/08/leetcode-n-queens-problem-solution.html