Yesterday, when I was on the bus, I got pulled into a sudoku. Then I started wondering how a machine could be programmed to solve these puzzles.
Note: For the rest of this post:
- A square is the un-devidable unit containing 1 number
- A section is a 3×3 grid of squares
- A column is a 10 square vertical strip
- A row is a 10 square horizontal strip
- A board is the 9×9 sudoku board
There a few simple rules that go into solving these puzzles. Namely :
- What are the possible values for this square (based on row, column and section)
- What are the possible places for this number (in this section)
The two questions aren’t identical, since a numbers position can be influenced by the positions of numbers in other columns or rows that share the section.
The first question comes down to :
- Take the ensemble of possible numbers
- Remove all that are already in the current row
- Remove all that are already in the current column
- Remove all that are already in the current section
- if there is only one left, put it in the square
- lather
- rinse
- repeat
The second question comes down to:
For each number not entered in each section
- Check for number in the rows that pass through this section, eliminate the squares that belong to them if found
- Check for number in the columns that pass through this section, eliminate the squares that belong to them if found
- if only one square is left, put the number in it
- …
- profit
OK, mabey that one’s a bit vague, I’ll try to make it clearer with a drawing
Example of a row and column problem
In the above image, concentrate on the bottom middle section. If you look, you’ll notice that there are 4s in the top 2 rows of this section, we can conclude that our 4 must be on the bottom row. We also notice that there is a 4 in the left most column of this section, which only leaves the bottom middle square as a possibility for this 4.
By combining the 2 rules stated above, we should be able to solve any sudoku puzzle.
Any how, that’s all for now. Proof by code will be comeing in an update.
