Revision Date: January 8, 2017
Once you have a function that checks whether or not there are any duplicates in any row, column, or section of a Sudoku grid, you are well on your way towards writing a program that can solve a partially filled-out or even an empty grid.
A Sudoku solving function is quite difficult to write using loops, but is almost laughably easy using recursion. Suppose you have a solving function named solver, that takes a grid, a row index, a column index, and a digit to place at that row and column. Then it becomes a simple matter: if placing the digit at the given row and column leads to a solution, you are done! If it doesn't, you need to try the next digit. If no digit works at the given location, you need try a different digit at a previous location. This business of trying a different digit at a previous location is known as backtracking. Recursion allows you to backtrack so easily, you don't even realizing you are doing it.
Rather than giving you a formal recurrence equation for solving Sudoku (which would make this task too easy), we will describe the equation in English. Note that our solving function takes the grid, a row number, a column number, and a digit. When we wish to try a new digit at a location, we make a recursive call that changes the digit, but leaves the row and column numbers the same. When we wish to try a new column, we make a recursive call that increments the column number, keeping the row number the same, but resetting the digit back to one (since we wish to try all the digits at the new location). When we wish to work on a new row, we make a recursive call that increments the row number, but resets the column number and digit back to zero and one, respectively.
Here are the cases of the recurrence equation:
The initial call to our solver sends zero as the row number, zero as the column number, and one as the first digit to try. If our initial call returns True, we solved the puzzle. If it returns False, there is no solution.
The only tricky bits are in case 5. The first is how to check if the newly placed digit causes a conflict. Your solution checking function can be used to tell you that. The second is how to determine if the newly placed digit, while not causing an immediate conflict, leads to a future conflict down the line. We can make a recursive call to the solver function, having it start on the next column, to tell us that. If the recursive call returns False, that means the digit we placed caused a future problem. These two checks, together, can tell us if there is a problem with the current digit at the current location; if either the current solution fails with a duplicate value or the recursive call to fill out the rest of the grid returns False, we need to backtrack by resetting the current location back to a space and trying another digit.