Expert · Backtracking · 231 of 264
N queens
In how many ways can n queens be placed on an n by n board so that no two attack each other (same row, column or diagonal)? Use backtracking, row by row.
Input: n (1 to 9). Output: the number of placements.
Examples
Input
4
Output
2
Input
1
Output
1
Input
6
Output
4
2 more tests check other inputs when you press Check.
Stuck? The idea behind backtracking
Build an answer one choice at a time; when a choice leads nowhere, undo it and try the next. Recursion keeps track of where you are.
Check as early as you can whether a partial answer can still work, so dead ends are left quickly.
def subsets(items, chosen=[]):
if not items:
print(chosen)
return
subsets(items[1:], chosen + [items[0]])
subsets(items[1:], chosen)
subsets([1, 2])Watch for: Changing a shared list without undoing the change afterwards leaves the next choice with the wrong start.