This post originated from an RSS feed registered with Python Buzz
by Ben Last.
Original Post: Solving Sudoku With Superpositions
Feed Title: The Law Of Unintended Consequences
Feed URL: http://benlast.livejournal.com/data/rss
Feed Description: The Law Of Unintended Consequences
Actually, no, but that is a killer first line, from the movie Confidence. And when you have a killer first line, you go with it.
So I find myself writing up some examples and explanations of how to do basic object oriented design and development, and thus having to come up with something to serve as an example of how you might actually approach designing and implementing some code in C#. A problem slightly more connected to the real world than, say, yet another example like:
class Shape { virtual void Draw{} { } }
class Circle : Shape { override void Draw{} { } }
Sudoku will serve pretty well. First of all, it's a fairly easy problem to understand. Also, anyone who's of an algorithmic frame of mind and has encoutered a Sudoku puzzle has probably spent a while thinking about how to generally solve them. Programmers know that working out how to solve any problem of type X is more fun than actually solving any given individual problem of type X. And writing the code to do it also keeps you looking busy while someone else goes and does the actual work.
So, here is the algorithm that I've used as a basis, which I like to call solving with superposition because it lets me get all quantum and esoteric about it. To follow, you'll need to know at least the basic rules of Sudoku puzzles, which are ably explained in the relevant Wikipedia article.
On first encountering a Sudoku puzzle, such as this: we can see that:
It's made up of 81 cells
They're arranged into 9 rows, 9 columns and 9 squares, each of which contains 9 cells.
Each cell either contains a number (we'll call these solved), or is blank (unsolved)
For the purposes of this algorithm, let's start off by assuming that each unsolved cell contains all the possible numbers 1 to 9 that it might hold. The work of solving the puzzle then involves finding numbers that cannot be in unsolved cells, and removing them, until each unsolved cell only contains one possible number, which means that it's then a solved cell. I call this process pruning.
I should point out here that there are many different ways to solve Sudoku puzzles. This is just one, and not necessarily the best one; I've chosen it because it's a nice little algorithmic example. If you have better approaches, go write a Wikipedia article.
Anyway, back to the explanation. Let's show how the top-left group of nine cells in the example puzzle might be written out by a programmer trying out this algorithm. Conceptually it looks like this:
5
3
123 456 789
6
123 456 789
123 456 789
123 456 789
9
8
When we prune the puzzle, we follow this approach:
For each solved cell in turn, remove the number it contains from all the unsolved cells in the same row, column and square.
If, as a result of that, an unsolved cell is left containing only one number, that cell is now solved.
Keep doing this until either the puzzle is completely solved, or there are no more solved cells to process.
The thoughtful amongst you will have noticed that this will, so far, only solve very simple puzzles. Patience: more is yet to follow. For the moment, let's prune that example square of the board I showed above.
First, the topmost/leftmost cell contains a 5. So we know that we must remove the 5 from all the unsolved cells in the same row, column and square.
5
3
123 4 6 789
6
123 4 6 789
123 4 6 789
123 4 6 789
9
8
We can then do the same for the other cells that are already solved (the 3, 6, 9 and 8):
5
3
12 4 7
6
12 4 7
12 4 7
12 4 7
9
8
Okay, we now have a number of cells that are still ambiguous; that is, we know that they may still be one of n possible values, even though we've reduced the value of n by eliminating values that can't be in the cell.
Here's the superposition bit: we take a cell that still needs to be solved, and for every value that the cell could hold, we generate a different version of the board. So if we take the cell after the 5 & 3, that could be 1, 2, 4 or 7 (in red here):
5
3
12 4 7
6
12 4 7
12 4 7
12 4 7
9
8
...we generate four versions of the board, one in which the red cell holds 1, one in which it holds 2, one in which it holds 4 and one in which it holds 7. You can think of this (if you like to play with quantum terminology) as a superposition of four possible boards. We then take each board in turn and proceed to try and solve it, using the same techniques again. For example, if we take the superposition in which the red cell holds 2, then we need to remove the 2 from any other cells in the same row, column and square...
5
3
2
6
1 4 7
1 4 7
1 4 7
9
8
We still have some ambiguous cells, such as the one in blue that could hold 1, 4 or 7. So we create three further superpositions, one for each of the possible values of the blue cell, and then proceed to solve each of those.
Okay, the software-oriented amongst you will immediately have started thinking about recursion and stacks. Which is exactly what I was after: an example which requires that the students think about objects as elements in data structures that must then be subjected to processing. I need only make it compulsory for them to use the generic System.Collections.Generic.Stack collection, and I have an interesting algorithmic problem for them to solve...
Previous Topic
