Sudoku Solving Program                                                                          

Newspaper Sudoku

Well I got so discussed with the Stirling engine project that my mind started looking for diversions and, before I knew it, I was writing another image recognition program.

Sudoku solving program

A couple of years ago, I wrote a Sudoku VB6 program where I could enter the starting numbers into a 9x9 grid and the computer would fill in the remaining blank cells with the solution. I used the program to find out where I went wrong when I made a mistake doing a Sudoku, so I could back track and finish the puzzle. When writing the program, I realized right away that using a brute–force approach of looking for all possible puzzle number combinations was not going to work, due to the very high number of possibilities (Wiki says 6.67×10²¹⁾. In the program, I used the same algorithms that I apply when solving a puzzle.  I am not sure if all puzzles can be completely solved by these two algorithms but the program routinely solves the daily puzzles from the newspaper in a few tenths of a second.

Sudoku single

The Look-For-Singles algorithm finds what I call give-away-cells; cells that could only be filled by a single number.  Say a row contained the numbers 12345678. The empty cell could only be a nine. The way the algorithm detects this cell is by first filling all 81 cells of a grid with the string “123456789”,  then as each new answer is entered in the grid, that digit is removed from each cell string in that row, in that column and in that block. If any of the resulting cell strings diminish to the length of one character then a new result has been found.

Another Sudoku single

 In addition, any row, column or block that contains only one instance of a number, is also a solution. These processes are repeated until no new results are found. Newspaper Sudoku puzzles with one, two or three star difficulty ratings can usually be solved using this algorithm alone.

Sudoku Pair

If the Singles algorithm leaves some cells unsolved then the Look-For-Pairs algorithm is used. It looks for pairs of cells where the same two numbers are only possible in each. Say the top row contained the numbers BBB4567BB (B = a blank cell) and the top left block also contained the numbers 8 & 9. Each of the two empty cells at the end of the top row could only contain an eight or a nine. You still don't know which of those two cells contains the 8 & 9, but you can eliminate all other possible solutions. When the other solutions are eliminated from paired cells, it sometimes leaves adjacent rows, columns or blocks with new single solutions that the Look-For-Singles algorithm can find. 

So these two algorithms are repeatedly run until no additional answers are found. Newspaper Sudoku puzzles with four or five star difficulty ratings can usually be solved using one to three passes of these algorithms.

When I find that I’ve gone wrong solving a Sudoku puzzle, I get pretty irritated. Then I go to the puzzle solver program and get even more irritated tediously entering the 20 to 30 starting  numbers to find I’ve made a mistake doing that too. I kept thinking that the damn computer should be able to read the damn puzzle and solve it. So I wrote a program to do just that!