Why is it important?
N-Queens is a classic backtracking problem that gets asked a lot during interviews.
You’re almost guaranteed to get some kind of backtracking problem during a silicon valley software job interview loop. The problem you get might not be N-queens, but the other common backtracking questions (like writing a sudoku solver or solving a word search) can be solved using the same idea and structure that we use to solve N-queens.
In our solution below, I’ll take you through the general backtracking template, how I’d solve this problem during an interview, and then finish by giving a nice 11 line solution for fun.
The N-Queens Problem - Leetcode #51
https://leetcode.com/problems/n-queens/description/ 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.
Example:
Input: 4
Output:
[
[“.Q..”, // Solution 1
“…Q”,
“Q…”,
“..Q.”],
[”..Q.”, // Solution 2
“Q…”,
“…Q”,
“.Q..”]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
Discussion of Backtracking Problems
The basic idea for solving a backtracking problem like n-queens, is to work towards every possible end position one move at a time; if ever it becomes impossible to place another queen, we undo our previous move and try another placement. Using this strategy, we explore all possibilities.
This process is usually called ‘traversing the game tree’. In n-queens the ‘game’ is single player, but in a two player game, like chess or tic-tac-toe, or checkers, we’d be:
- Trying a move
- Considering all possibilities for the opponent’s move
- Considering all possibilities for our next move.
- Repeating 2 and 3 until we reach the ‘terminal states’ (when someone has won or lost)).
Traversing a game tree has exponential complexity. For many games, we won’t actually have the ability to actually look at the whole thing (consider playing chess with a limited compute time for example). To make things run as fast as possible, we’ll look for problem specific ways to ‘prune’ the game tree . For an example of this, see alpha-beta pruning and how it relates to chess AIs.
The Solution to N-Queens
When we solve n-queens, our solution will be a depth first search (dfs) through the game tree. We want to consider all possibilities without duplicating any end scenarios. To do so, we can consider placing queens row by row (we could also use columns or diagonals instead of rows). This works, because, by the rules of n-queens, no two queens can be on the same row.
Assuming we have a ‘Board’ class (which we’ll write later) that keeps track of the board state (where queens have been placed) and can tell us whether or not placing a queen at a given square is valid (isn’t on the same diagonal, row, or column as any other queen), the code would look something like:
def solveNQueens(n):
# An array of strings to store solutions.
output = []
# Board (an as yet unwritten class that keeps track of game state).
board = Board(n)
# row - integer - The row number we are considering.
def dfs(row):
if row == n:
output.append(board.outputFormat())
return
for col in range(n):
if board.isValidPlacement(row, col):
board.add(row, col)
dfs(row + 1)
board.remove(row, col)
dfs(0)
return output
This code above is very similar for all backtracking problems. Most of the n-queens specific code is in the Board class. If you’re solving sudoku, or some other backtracking problem, you’ll just use code very similar to the above, but change the Board class.
Let’s start with a basic implementation of the Board class (we’ll make it a bit better later). We’ll use something very close to the required output format (an array of strings, one per row) as our internal representation of the board. We use a list of lists because strings are immutable in python. We’ll check the diagonals by just looping over each of them:
class Board:
def __init__(self, n):
self.n = n
self.board = [['.' for x in range(n)] for y in range(n)]
def isValidMove(self, row, col):
col_j = col
left_diag_j = col
right_diag_j = col
# Only checks rows before 'row' since we know we'll be filling
# rows from 0 to n so there can't be a queen on rows > row.
for i in range(row, -1, -1):
if self.board[i][col_j] == 'Q':
return False
if left_diag_j >= 0 and self.board[i][left_diag_j] == 'Q':
return False
if right_diag_j < self.n and self.board[i][right_diag_j] == 'Q':
return False
left_diag_j -= 1
right_diag_j += 1
return True
def placeQueen(self, row, col):
self.board[row][col] = 'Q'
def removeQueen(self, row, col):
self.board[row][col] = '.'
def outputFormat(self):
return [''.join(x) for x in self.board]
The board class as-is is probably good enough to get you a pass on the interview; but, an interviewer might ask you to make the diagonal and column checks O(1) instead of O(n). To do that, we can use a simple trick. Let’s draw the board, and see if we can notice a pattern in the diagonals (trying to find some ‘label’ for each diagonal)
| 0,0 0+0 = 0 | 0,1 0+1 = 1 | 0,2 0+2 = 2 | 0,3 0+3 = 3 |
| 1,0 1+0 = 1 | 1,1 1+1 = 2 | 1,2 1+2 = 3 | 1,3 1+3 = 4 |
| 2,0 2+0 = 2 | 2,1 2+1 = 3 | 2,2 2+2 = 4 | 2,3 2+3 = 5 |
| 3,0 3+0 = 3 | 3,1 3+1 = 4 | 3,2 3+2 = 5 | 3,3 3+3 = 6 |
Using inspection from our drawing and insight from how we update the indices when looping over the diagonal, we can see:
- right diagonals have row + column = Constant
- left diagonals have row - column = Constant
So, we can use row + column as an identifier for right diagonals and row - column as an identifier for left diagonals.
Using this idea, we can keep:
- a set of used right diagonals
- a set of used left diagonals
- a set of used columns
When we want to check if a move is valid, we can just check if our sets contain the diagonals and column we’re considering. Our updated Board class looks like:
class Board:
def __init__(self, n):
self.cols = set()
self.right_diags = set()
self.left_diags = set()
self.queen_locations = []
self.n = n
def add(self, row, col):
self.cols.add(col)
self.right_diags.add(row + col)
self.left_diags.add(row - col)
self.queen_locations.append(col)
def remove(self, row, col):
self.cols.remove(col)
self.right_diags.remove(row + col)
self.left_diags.remove(row - col)
self.queen_locations.pop()
def isValidPlacement(self, row, col):
return col not in self.cols and \
row + col not in self.right_diags and \
row - col not in self.left_diags
def outputFormat(self):
return ['.'*x + 'Q' + '.'*(self.n-x-1) for x in self.queen_locations]
This is pretty much as good as a solution gets, but for fun, to make a simple small solution (the kind leetcoders seem to like) we can:
- Do away with our Board class and keep all the state in our solve function.
- Keep all diagonals in the same set by subtracting an offset of n+1 from all left diagonals so that they are all negative and won’t clash with right diagonals. (i.e. use row-col-n-1 as the left diagonal identifier instead of just row-col).
- Use the function stack to do our insert and removal rather than doing it explicitly.
After we apply these tricks, the final solution is simply:
def solveNQueens(n):
output = []
def dfs(row, queens, diags):
if row == n:
output.append(['.'*x + 'Q' + '.'*(n-x-1) for x in queens])
return
for col in range(n):
if not any([row+col in diags, row-col-n-1 in diags, col in queens]):
dfs(row + 1, queens + [col], diags | {row+col, row-col-n-1})
dfs(0, [], set())
return output
Conclusion
N-Queens is an example of a constraint satisfaction problem that is solved easily with backtracking. Backtracking is extremely important in today’s software interviews and almost always comes up in some form.
If you are interested in learning more about constraint satisfaction problems, a good resource is the constraint satisfaction section in Artificial Intelligence: A modern Approach where they go into detail on how to solve more difficult constraint satisfaction problems.
If you have any questions regarding this or other leetcode problems, please comment below.
If you would like more solutions as they come out, please sign up for our email list below.