All Safe Boards for N Queens
Problem statement
Place n queens on an n by n chessboard so that no two queens attack each other. Two queens attack each other when they share a row, a column or a diagonal. Return every safe board.
Show each board as n strings, one per row from top to bottom. In row strings, 'Q' is a queen and '.' is an empty square.
Every safe board has exactly one queen in each row. List the boards in this order:
- compare the column of the queen in row 0 (column 0 is the leftmost); the board with the smaller column comes first;
- if they are equal, compare row 1, then row 2, and so on.
If no safe board exists, return an empty list.
Function
placeQueens(n: int) → List<List<String>>Examples
Example 1
n = 6return = [[".Q....","...Q..",".....Q","Q.....","..Q...","....Q."],["..Q...",".....Q",".Q....","....Q.","Q.....","...Q.."],["...Q..","Q.....","....Q.",".Q....",".....Q","..Q..."],["....Q.","..Q...","Q.....",".....Q","...Q..",".Q...."]]There are exactly four safe boards for 6 queens. Reading the queen's column row by row, they are 1, 3, 5, 0, 2, 4, then 2, 5, 1, 4, 0, 3, then 3, 0, 4, 1, 5, 2, then 4, 2, 0, 5, 3, 1. They are listed in that order because their row 0 columns are 1, 2, 3 and 4. No safe board has its row 0 queen in a corner.
Example 2
n = 3return = []No board works for 3 queens. If the middle-row queen is in the center, every top-row square is in its column or on its diagonal. If it is at an edge, the top row and the bottom row each have only one safe square left, and both are in the same column. The answer is an empty list.
Example 3
n = 5return = [["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]]There are ten safe boards for 5 queens. Two start with the row 0 queen in each of the five columns. For column 0 they are 0, 2, 4, 1, 3 and 0, 3, 1, 4, 2, and the one whose row 1 queen is further left comes first.
Constraints
1 <= n <= 8