Formatted question description: https://leetcode.ca/all/51.html
51 N-Queens 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. For example, There exist two distinct solutions to the 4-queens puzzle: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
The exhaustive method is to try all combinations. Every time a new queen is placed, it must be ensured that it does not conflict with all the previous queens. If a conflict occurs, it means that the current position cannot be placed, and a new place must be found.
This logic is very suitable for recursion. We first create an array queens of length nxn that is full of points, and then call recursion from line 0. In the recursive function, we first judge whether the current number of rows is already n,
- if yes, it means that all the queens have been successfully placed, so we only need to add the queens array to the result.
- Otherwise, we traverse the position of all the columns of the row, and after the positions of the row and column are determined, we need to verify whether the current position will conflict, then we need to use a sub-function to judge,
- first verify whether the column has a conflict, it traverses all the previous rows, if there is a queen in the same column in a certain row, the conflict returns false;
- then verify whether the two diagonals conflict, which is some coordinate conversion, mainly don’t write it wrong,
- if there is no conflict, then the conflict You can put the queen in the position. After you put the new queen, you can call recursion on the next line. Pay attention to the return state after the recursion.