Problem 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.
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"]]
Constraints:
1 <= n <= 9
The description was taken from https://leetcode.com/problems/n-queens/.
Problem Solution
#O(N!) Time, O(N^2) Space
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
up_right, up_left, cols = {},{},{}
output = []
board = [["."]*n for row in range(n)]
def valid_spot(row:int, col:int) -> None:
if col in cols:
return False
if (row + col) in up_right:
return False
if (row - col) in up_left:
return False
return True
def backtrack(row:int) -> None:
if row == n:
output.append(list("".join(r) for r in board))
return
for col in range(n):
if not valid_spot(row, col):
continue
cols[col] = True
up_right[(row+col)] = True
up_left[(row-col)] = True
board[row][col] = "Q"
backtrack(row+1)
del cols[col]
del up_right[(row+col)]
del low_left[(row-col)]
board[row][col] = "."
backtrack(0)
return output
Problem Explanation
The question requires us to return all combinations of valid boards.
When we see an exhaustive requirement like this, backtracking is a good approach. Similar to other backtracking problems, we will traverse the board and try to place values. If our placement is valid, we will continue with that choice. When we need to explore a different placement, we will backtrack by un-marking the current spot as visited and removing the value we placed.
Keeping track of visited rows and columns so that there are no queens in the same row or column is easy enough, we will just not place queens in a row or column that there is already one in.
However, the diagonal rows will be more difficult. When we place a queen we could do a BFS on the cell's four diagonal corners and mark each cell as seen, but that would require an additional linear operation for each queen we place.
To fix that, we could utilize the row and column values themselves.
If we add a row and a column value, we will get a row identifier number for the upper-right, lower-left diagonal rows.
| 0 | 1 | 2 | 3 |
| 1 | 2 | 3 | 4 |
| 2 | 3 | 4 | 5 |
| 3 | 4 | 5 | 6 |
If we subtract the row by the column, we will get a row identifier number for the upper-left, lower-right diagonal rows.
| 0 | -1 | -2 | -3 |
| 1 | 0 | -1 | -2 |
| 2 | 1 | 0 | -1 |
| 3 | 2 | 1 | 0 |
With these diagonal identifiers, we will ensure that we are also not placing a queen into a diagonal row where there already is one.
Let's start by initializing both diagonal rows visited hashmaps and the visited columns hashmap.
There is no use making a rows hashmap because we are going to recurse to a different row within our DFS so there won't be two queens in the same row within any given combination regardless.
up_right, up_left, cols = {},{},{}
Let's also initialize our output array.
output = []
Now we will need an empty board with n rows and n columns.
board = [["."]*n for row in range(n)]
Let's make a helper function that will check if the current cell is a valid spot to place a queen.
def valid_spot(row:int, col:int) -> None:
If a queen exists in the column, we will return false.
if col in cols:
return False
If a queen exists in the upper-right, lower-left diagonal row, we will return false.
if (row + col) in up_right:
return False
If a queen exists in the upper-left, lower-right diagonal row, we will return false.
if (row - col) in up_left:
return False
Otherwise, this is a valid spot to place a queen.
return True
Now let's make our recursive, backtrack function.
def backtrack(row:int) -> None:
For the base case, if the current row is equal to n, then we have been able to place queens in each previous row in which case we will append the current combination to the output and return from the end of this Depth-First Search path.
if row == n:
output.append(list("".join(r) for r in board))
return
Otherwise, we will try to place a queen in each column within the current row.
But first off, before we place a queen, we will see if it is a valid spot.
If it is not, we will continue to the next column.
for col in range(n):
if not valid_spot(row, col):
continue
Otherwise, we have a valid placement in the current row and column. We will mark this coordinate as visited and place a queen, then we will continue our DFS on the next row.
cols[col] = True
up_right[(row+col)] = True
up_left[(row-col)] = True
board[row][col] = "Q"
backtrack(row+1)
Once the DFS yoyo has slung back up to the current row and coordinates, we will backtrack our placement.
del cols[col]
del up_right[(row+col)]
del low_left[(row-col)]
board[row][col] = "."
Now that we have our functions built, we will need to make the initial call on the first row.
backtrack(0)
When the DFS has been completed, we will return the output of each valid combination for the current board size.
return output