N-Queens
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Place n queens on an n x n chess board so that no two attack each other (same row, column or diagonal). Return all boards.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How many queens can be in one row? So what do you decide per row?
- Hint 2Two cells share a diagonal if row + column matches (one way) or row - column matches (other way).
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Seating n VIP guests at a banquet board where nobody may see another VIP along a row, column or diagonal. Row by row, you try each seat in the row: a seat is allowed only if its column and both diagonals are free. If a row has no free seat, you walk back to the previous row and move that VIP to the next seat. Each placed VIP puts three "taken" sticky notes: one on the column and one on each diagonal.
- The obvious way
Try all n^n column choices and check: far too slow.
- The key insight
Keep three sets: used columns, used (row + column) diagonals, used (row - column) diagonals. Recurse row by row: for each column that is free in all three sets, place a queen (add to the sets and the list of columns), recurse to the next row, then remove it. A full set of n rows becomes a board.
- The algorithm
- Sets for columns and both diagonals; list of chosen columns.
- Row == n: build the board from the chosen columns and save.
- For each column free in all three sets: place.
- Recurse to the next row, then remove the queen.
Watch it run
Examplen = 4
Row 0: try column 0. Row 1: columns 0 (same column) and 1 (diagonal) are blocked, column 2 works. Row 2: every column is blocked. Dead end.
queens: 0, 2, ?
Where people slip
- Remove the three marks when backtracking, not just the queen.
- In Java arrays, shift row - column by n so the index is never negative.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def solve_n_queens(n):
boards = []
queens = [] # queens[row] = the column of that row's queen
columns_taken = set()
down_right_taken = set() # cells with the same row - column
down_left_taken = set() # cells with the same row + column
def place(row):
if row == n:
boards.append(["." * column + "Q" + "." * (n - column - 1) for column in queens])
return
for column in range(n):
if column in columns_taken or row - column in down_right_taken or row + column in down_left_taken:
continue # this seat is attacked
columns_taken.add(column)
down_right_taken.add(row - column)
down_left_taken.add(row + column)
queens.append(column)
place(row + 1)
queens.pop() # backtrack: remove the sticky notes
columns_taken.remove(column)
down_right_taken.remove(row - column)
down_left_taken.remove(row + column)
place(0)
return boardsNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.