Monday, November 02, 2015

Sudoku

It's hard to find a newspaper without one, and I personally find that Sudoku solutions are an interesting problem. Randomly filling a grid of 81 cells with numbers from 1-9 wouldn't take long, but the end result probably wouldn't be a Sudoku solution, where each row, each column, and each box, all need to have the numbers 1-9 exactly once.

Instead of doing it randomly, we could try a constrained approach: only pick numbers from the set that would form an allowable Sudoku solution. We could start off by defining the set of all values in row M, all values in column N, and all values in box MN. The union of all three sets would indicate the values that have already been picked; therefore they're the numbers we couldn't re-use if we were to make a valid Sudoku solution. \( R(m) \cup C(n) \cup B(m,n) \) is the numbers that have been used, \( (R(m) \cup C(n) \cup B(m,n))' \) are the numbers available to us (this last set is the equivalent of \(R(m)' \cap C(n)' \cap B(m,n)'\)).

Let's assume we're looking at an empty cell, in an empty grid. \(R(m)=\emptyset, C(n)=\emptyset, B(m,n)=\emptyset\), therefore we can choose anything from \(\emptyset'\). The world is our oyster. Let's pick 1. We could have picked anything, but 1's a good place to start. In the adjacent cell, \(R(m)\) and \(B(m,n)\) would both yield \(\{1\}\) so we'd be forced to pick anything from \(\{1\}'\). Let's pick 2. Continuing in ascending order (and increasing level of constraint) we'd finally reach the 9th cell where \(R(m)=\{1,2,3,4,5,6,7,8\}\) and \(B(m,n)=\{7,8\}\). The only number we can pick is 9. Our top row is complete.

Continuing at the first column of the second row, and proceeding in the same fashion, we keep filling cells. It's too easy, something's got to break.

Ah. On the second row, at the seventh colum, we reach Box(2,7). We've already written \(\{4,5,6,1,2,3\}\) into the row, and \(\{7,8,9\}\) into the box. What can we do now?

The answer is to backtrack. We didn't have to choose the lowest value from \(R(m)' \cap C(n)' \cap B(m,n)'\) every time; in fact - more often than not - we had a wide array of options. So, we backtrack. That involves reverting the operation on the current cell (leaving it blank), moving to the previous cell, making sure it's blank (but we remembered which value(s) we'd already tried), and then trying another value. We don't need to limit ourselves to going back just one cell, either. In fact, in this case, we need to revert the last three cells. A second row that looks like \(\{4,5,6,7,8,9,1,2,3\}\) is a valid partial solution to a Sudoku problem. We use backtracking even more on the third row, producing \(\{7,8,9,1,2,3,4,5,6\}\). Still: a valid partial solution.

It turns out that our set-based constraints, plus the backtracking ability, give us the power to solve any Sudoku problem, even when the starting point is ambiguous (in the case of the empty grid).

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2