Recursion
Solve Sudoku
Given a Sudoku puzzle board, solve the board by modifying it in-place. Do not return anything.
To solve the board, you must ensure that every row, column, and 3x3 section outlined in bold contains every digit 1 though 9.
Example:
board =
=> returns
Note that board always takes this form, where ' ' means empty:
solveSudoku([
['5', '3', ' ', ' ', '7', ' ', ' ', ' ', ' '],
['6', ' ', ' ', '1', '9', '5', ' ', ' ', ' '],
[' ', '9', '8', ' ', ' ', ' ', ' ', '6', ' '],
['8', ' ', ' ', ' ', '6', ' ', ' ', ' ', '3'],
['4', ' ', ' ', '8', ' ', '3', ' ', ' ', '1'],
['7', ' ', ' ', ' ', '2', ' ', ' ', ' ', '6'],
[' ', '6', ' ', ' ', ' ', ' ', '2', '8', ' '],
[' ', ' ', ' ', '4', '1', '9', ' ', ' ', '5'],
[' ', ' ', ' ', ' ', '8', ' ', ' ', '7', '9']])
# [
# ['5', '3', '4', '6', '7', '8', '9', '1', '2'],
# ['6', '7', '2', '1', '9', '5', '3', '4', '8'],
# ['1', '9', '8', '3', '4', '2', '5', '6', '7'],
# ['8', '5', '9', '7', '6', '1', '4', '2', '3'],
# ['4', '2', '6', '8', '5', '3', '7', '9', '1'],
# ['7', '1', '3', '9', '2', '4', '8', '5', '6'],
# ['9', '6', '1', '5', '3', '7', '2', '8', '4'],
# ['2', '8', '7', '4', '1', '9', '6', '3', '5'],
# ['3', '4', '5', '2', '8', '6', '1', '7', '9']]0. Problem
This problem is very similar to the N-Queens problem. In N-Queens we placed a queen row-by-row. In Sudoku we place a number square-by-square.
Our function should try every possible number 1-9 at each empty square, until it eventually reaches a complete board. The function needs to know the current board.
visitAll(board)1. Recursion
We can easily write this recursively. Just consider adding 1-9 to the current empty square, and then repeating the process. Here's pseudocode:
visitAll(board) = {
row, col = "the next empty square"
for num in range(1, 9+1):
if "num can be added at row, col":
visitAll(board with board[row][col]=num)
}2. Base case
We want the visitAll function to stop when the board is full.
3. Code
We wrote some pseudocode above, and we need to convert it to actual code.
Here's how we fill in "the next empty square":
Open SpoilerClose Spoiler
We could search the board to get to get the next empty square row, col, but if it's faster to store a data structure of all the empty squares, which we create just once at the very start. That way we don't need to waste time searching the board multiple times. We'll call it emptySquares. Here's how we'll initialize it:
emptySquares = [] # [(row, col) of each empty square]
for r in range(9):
for c in range(9):
num = board[r][c]
if num == 0:
emptySquares.append((r, c))We can now turn our pseudocode into real code:
row, col = "the next empty square"
# --change to-->
row, col = emptySquares.pop()
# ... rest of code ...
emptySquares.append((row, col)) # mark it as empty again when doneHere's how we fill in "num can be added at row, col":
Open SpoilerClose Spoiler
We need to check if the number num is already in this row, column, or box. It's fastest to store extra data structures that help us with this so we don't have to waste time searching the board. We'll store a Set of all the numbers in each row, column, and box. We'll add this code at the very start:
# numsInRow[row] = a set of all the numbers in that row.
# numsInRow[col] = a set of all the numbers in that col.
# numsInRow[box] = a set of all the numbers in that box.
numsInRow = [set() for n in range(9)]
numsInCol = [set() for n in range(9)]
numsInBox = [set() for n in range(9)]
for r in range(9):
for c in range(9):
num = board[r][c]
if num != 0:
numsInRow[r].add(num)
numsInCol[c].add(num)
numsInBox[3*(r//3) + c//3].add(num)The formula inside numsInBox looks kind of crazy, but it's really simple: we get the row and column of each 3x3 box using row//3 and col//3. Then, we put a unique number on each of these boxes by counting up in base 3. Use row//3 as the 3s digit, and col//3 as the ones digit.
We can now turn our pseudocode into real code:
if "num can be added at row, col":
# --change to-->
if ( num not in numsInRow[row]
and num not in numsInCol[col]
and num not in numsInBox[3*(row//3) + col//3]):Here's how we fill in the base case:
Open SpoilerClose Spoiler
The board is full if there are no empty squares left. We want to stop the recursion immediately at this point so the board doesn't get erased. We'll add a global variable stopRecursion to do this.
if not emptySquares:
stopRecursion = True
returnHere's the full code:
def solveSudoku(board):
# initialize global parameters
row, col = None, None
stopRecursion = False
emptySquares = [] # all the (row,col)s that are a 0
numsInRow = [set() for _ in range(9)] # numsInRow[row] = a set of nums in that row
numsInCol = [set() for _ in range(9)]
numsInBox = [set() for _ in range(9)]
def initialize(board):
nonlocal row, col, stopRecursion
for r in range(9):
for c in range(9):
num = board[r][c]
if num == ' ':
emptySquares.append((r,c))
else:
numsInRow[r].add(num)
numsInCol[c].add(num)
numsInBox[3*(r//3) + c//3].add(num)
def visitAll():
nonlocal row, col, stopRecursion
# base case
if not emptySquares:
stopRecursion = True
return
# recursion
r, c = row,col
row, col = emptySquares.pop()
for num in range(1, 9+1):
num = str(num)
if ( num not in numsInRow[row]
and num not in numsInCol[col]
and num not in numsInBox[3*(row//3) + col//3]):
board[row][col] = num
numsInRow[row].add(num)
numsInCol[col].add(num)
numsInBox[3*(row//3) + col//3].add(num)
visitAll()
if stopRecursion: return
board[row][col] = ' '
numsInRow[row].remove(num)
numsInCol[col].remove(num)
numsInBox[3*(row//3) + col//3].remove(num)
emptySquares.append((row, col))
row, col = r, c
initialize(board)
visitAll()
Time Complexity O(9num_dots). For each dot, we might try 9 different choices.
Space Complexity O(9∗9∗3) for all the data structures we use.
Call Stack Complexity O(num_dots). visitAll() gets as deep as the number of dots. One call per dot.