We’re given an unfinished Sudoku table and we’re asked to solve it. This is a normal constraint satisfaction problem (CSP), and we can solve it using backtracking. First, we gather some information
- the size of the board, and we take the square root of that to get the size of the boxes in the board.
We define two lambda helper functions, one to get the binary representation of a number we’ve selected, and another to get the box where a cell, defined by (row, col), is contained within. We’re using binary to represent what numbers are present in a row, column, or box, and we use bit manipulation to check if a number is present in a row, column, or box. These bitwise operations are faster than using sets or some other form of index, and the position of a bit determines the number or numbers current present in a row, column, or box.
We define two helper functions to fill or empty a box with a number, and another helper function to check if a number selection is valid for a cell. Finally, we recursively search from (0, 0).
If the location we’re at during search is already filled, we skip it. If we’re at the end of the board, we return True. Otherwise, we go to the next column if we’re not at the end of the row. If we’re at the end of the row, we go to the next row.
If the location we’re at during search is not filled, we try to fill it with a number from 1 to 9. If the number we’ve selected is valid, we fill the location with the number, and we recursively search from the next location. If the recursive search returns True, we return True. Otherwise, we empty the location and try the next number. Eventually, if we can’t find a valid number, we return False - this will cascade backwards during backtracking as well.
Eventually, we’ll have completed our search and the board will be solved.
The solution is as follows:
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
N = len(board)
n = int(N ** (1/2))
binary = lambda x: 1 << (x - 1)
box = lambda x, y: (x // n) * n + y // n
rows, cols, boxes = (
[0 for _ in range(N)],
[0 for _ in range(N)],
[0 for _ in range(N)],
)
def fill(row: int, col: int, num: int) -> None:
rep = binary(num)
rows[row] ^= rep
cols[col] ^= rep
boxes[box(row, col)] ^= rep
board[row][col] = str(num)
def empty(row: int, col: int, num: int) -> None:
rep = binary(num)
rows[row] ^= rep
cols[col] ^= rep
boxes[box(row, col)] ^= rep
board[row][col] = "."
def ok(row: int, col: int, num: int) -> bool:
rep = binary(num)
return (
not rows[row] & rep
and not cols[col] & rep
and not boxes[box(row, col)] & rep
)
def fillNext(row: int, col: int) -> bool:
if row == N - 1 and col == N - 1:
return True
elif col == N - 1:
return backtrack(row + 1, 0)
else:
return backtrack(row, col + 1)
def backtrack(row: int, col: int) -> bool:
if board[row][col] != ".":
return fillNext(row, col)
ans = False
for num in range(1, 10):
if ok(row, col, num):
fill(row, col, num)
ans = fillNext(row, col)
if ans:
return ans
empty(row, col, num)
return ans
for i in range(N):
for j in range(N):
if board[i][j] != ".":
fill(i, j, int(board[i][j]))
backtrack(0, 0)_ Time Complexity:
O(9^(n^2)) - Where n is the number of rows and columns, our recursive backtracking solution will execute this many operations.
_ Space Complexity:
O(n) - Where n is the number of rows and columns in the board, we use O(n) space for the rows, columns, and boxes.