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:
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.
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:
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":
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:
We can now turn our pseudocode into real code:
Here's how we fill in "num can be added at row, col":
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:
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:
Here's how we fill in the base case:
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.
Here's the full code:
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.
