A cursed sudoku guards the last door of the dungeon. The curse breaks only when every empty square is filled so that no row, no column and no 3 x 3 box holds the same digit twice. Write solve_sudoku(board) that breaks it.
boardis 9 lists of 9 ints. A digit1–9is given;0is an empty square.- The givens never break the rules, and every board has exactly one solution.
- Return the solved board. Filling
boardin place and returning it is fine. Never change a given digit.
board = [
[0, 0, 0, 0, 0, 0, 0, 0, 4],
[0, 0, 0, 4, 0, 0, 1, 5, 8],
[0, 0, 0, 0, 5, 1, 7, 2, 0],
[0, 0, 2, 0, 8, 3, 5, 0, 1],
[6, 1, 5, 0, 4, 0, 0, 0, 9],
[8, 0, 3, 0, 0, 0, 0, 4, 0],
[0, 5, 6, 2, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 7, 6, 4, 9, 2],
[9, 2, 0, 0, 1, 0, 6, 7, 0],
]
solve_sudoku(board)
# [[5, 8, 1, 6, 2, 7, 9, 3, 4],
# [2, 6, 7, 4, 3, 9, 1, 5, 8],
# [3, 4, 9, 8, 5, 1, 7, 2, 6],
# [4, 7, 2, 9, 8, 3, 5, 6, 1],
# [6, 1, 5, 7, 4, 2, 3, 8, 9],
# [8, 9, 3, 1, 6, 5, 2, 4, 7],
# [7, 5, 6, 2, 9, 4, 8, 1, 3],
# [1, 3, 8, 5, 7, 6, 4, 9, 2],
# [9, 2, 4, 3, 1, 8, 6, 7, 5]]
Trying every way to fill the board grows like 9 to the power of the number of empty squares: hopeless with 50 or 60 of them. Backtrack instead: go to an empty square, try a digit that breaks no rule, and move on to the next empty square. When a square has no legal digit left, erase your last choice, go back, and try the next digit there.
Show hint
keep one set (or bitmask) of used digits per row, per column and per box, so "is this digit legal here?" costs O(1). The ⭐ speed test has boards built to punish going left to right. For those, always fill the empty square with the fewest legal digits next: a square with one option costs nothing, and a square with none is a dead end you find right away.