by Claude W Smith
(San Diego, CA)
Recently, My wife asked me to find a computer program so that she could play the game on her home computer. As her computer is not Intel x86 based, I decided to write a Sudoku program for her using an old programing language.
To make a program that she could play, was quite easy, but I went the extra mile, and started to program the thing to solve the puzzle without any guesswork. ( Pure Logic Only ).
During the programming of the solution, I found the concept of a list of possible values for each cell, did not work too well. So, I came up with another strategy that works quite well in my programming. ( So far so good. )
The concept is to give each cell a ‘Reject’ list. There are 81 cells, therefore, there are 81 ‘Reject’ lists.
For each cell(A), the computer first clears the ‘Reject(A)’ list for cell(A).
For each cell:
1) If cell(A) is filled, the ‘Reject(A)’ list is every value, So, if cell(A) is ‘4’, the ‘Reject(A) == ‘123456789’.
2) If cell(A) is empty, The computer examines each and every cell(B) that is in that cell(A)’s ROW, COLUMN and HOOD(3×3 Square). If, any cell(B) is filled, the computer adds cell(B)’s value to the ‘Reject(A)’ list.
3) Loops back to LOOP_REJECT: 81 times.
After that is done, for each cell(A), the computer then makes a long EXAMINE string of:
1) All the ‘Reject(B)’ lists of the cells in the same ROW.
2) All the ‘Reject(B)’ lists of the cells in the same COLUMN.
3) All the other ‘Reject(B)’ lists of the cells in the same HOOD(3×3 Square).
In each of the EXAMINE string, If any integer appears exactly 8 times in any of the three lists above, then that integer must be the value for cell(A). The computer plugs that integer into cell(A) and we go back to the START: routine and cycle again.
Example: In the diagram, looking at ROW 2.
The Reject lists are:
R(2)C(1) == 123 6789
R(2)C(2) == 123456789
R(2)C(3) == 123456789
R(2)C(4) == 123456789
R(2)C(5) == 12 56 89
R(2)C(6) == 123456789
R(2)C(7) == 1234 6789
R(2)C(8) == 123456789
R(2)C(9) == 12 56789
The (sorted) EXAMINE string for R(2)C(5) is all the ‘Reject’ lists which are in this ROW, namely,
If you look at the EXAMINE list for R(2)(5), the number ‘7’ appears exactly 8 times, therefore, the value of R(2)C(5) is ‘7’.
I will leave it an exercise for the reader, to examine the EXAMINE list for all the cells in the HOOD of R(3)(4). You will notice that the number ‘2’ appears exactly 8 times, making the value of R(3)C(4) == ‘2’.
1) This will also detect what you call, ‘Naked Singles’ and ‘Hidden Singles’ without any modification.
2) This will also detect: ‘Naked Pairs’ and ‘Hidden Pairs’. If any two integers appears exactly 7 times in the EXAMINE string, the computer probes all the other cells. If a match is found in the same ROW or COLUMN or HOOD, The computer adds these two numbers to the ‘Reject’ lists of the same ( ROW or COLUMN ) and to the cells in each of the associated HOODS.