Expert · Backtracking · 232 of 264
Sudoku solver
Solve a sudoku: fill the empty cells (0) so every row, column and 3x3 box contains the digits 1 to 9 once. Each puzzle has one solution.
Input: 9 lines of 9 digits. Output: the solved grid, 9 lines of 9 digits.
Examples
Input
530070000 600195000 098000060 800060003 400803001 700020006 060000280 000419005 000080079
Output
534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179
Input
003020600 900305001 001806400 008102900 700000008 006708200 002609500 800203009 005010300
Output
483921657 967345821 251876493 548132976 729564138 136798245 372689514 814253769 695417382
One more test checks 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.