Tech notes for everyone

So we now have a 9 x 9 grid with numbers that fit the constraints of Sudoku rules:

1. Each row must contain the numbers 1 to 9.

2. Each column must contain the numbers 1 to 9.

3. Each 3 x 3 local square must contain the numbers 1 to 9.

Now we have to remove numbers from the board. We can’t just remove any numbers. We can only remove numbers that allow us to solve the puzzle with one solution.

One way to accomplish this is to randomly select a number, remove it then see if we can solve the puzzle. If we can’t, replace the number and try again. If we can, try again.

So obviously we need to write a Sudoku solving algorithm.

MY algorithm uses a while loop:

while ( ($blanksquaresleft == 1) and ($solvable == 1) ) {keep trying to solve the Sudoku grid}

Obviously if there are no blank squares left in our Sudoku’s 9 x 9 grid then our Sudoku grid is solvable as we have filled it in. Return a success code.

The $solvable variable is set to 1 if we have at least filled in one blank square during the last loop. This at least gives us the hope that this 9 x 9 grid is solvable. If, during the last loop, we did not fill in any blank squares, this Sudoku grid is not solvable, so quit and return our failure.

if ( ($LpNS > 0) or ($LpHS > 0) ) {$solvable = 1} #still might be solvable! keep going

else {$solvable = 0} #our algorithm can’t solve this board! quit and return a failure code

The next part we need to code are the algorithms to actually fill in the blank squares.

To my knowledge, there are 7 basic methods to try and solve Sudoku puzzles. Naked Singles (NS), Hidden Singles (HS), Naked Pairs (NP), Hidden Pairs (HP), Intersection Removal (IR), X-Wing (XW), and Y-Wing (YW).

Naked Singles (NS): Naked Singles iterates through all the squares on the board, calculating the possible values in each cell based on Sudoku’s rules listed above. When we find a cell with a single possibility we fill in the Sudoku board with that value.  Then we recalculate all the possibilities based on the number we just added to the Sudoku board.

Hidden Singles (HS): Hidden Singles scan each row, column and 3 x 3 square for the ‘number of possibilities’ for each number ranging from one to nine. When it finds a cell containing a possibility which appears exactly once in a row, column or 3 x 3 square, we fill in the Sudoku board with that value.  Then we recalculate all the possibilities based on the number we just added to theSudoku board.

Naked Pairs (NP):

The first version of Naked Pairs searches each region for two possibility values that occur only twice in, and share two cells, which may or may not contain other possibilities. Because they occur
only in these two cells, one of them must go in one cell and the other in the second. Therefore,
any other values in these two cells may be eliminated.

The second version scans each region for two cells, each containing ONLY the same two possibilities. Because one of these values must occur in each of the two cells, they cannot occur anywhere else in that region, and may be eliminated from the lists of possibilities for every other cell in the region.

Hidden Pairs (HP):

Hidden Pairs are taken care of  by the combination of Naked Squares and Hidden Singles algorithms.

Intersection Removal (IR):

If exactly two or three possibilities exist for a single number in one row or column and they are also confined to one box, their values may be eliminated from the rest of the row or column.

If exactly two possibilities exist for a number in a row or column of a box, the number can be eliminated from the rest of the box.

X-Wing (XW):

Look for a single value that occurs exactly twice in two rows. If the cells containing
the value line up in two columns to form a rectangle, all occurrences of the value may be
removed from both columns. This also works the other way, starting with columns and eliminating
from rows.

Y-Wing (YW)
Y-wings work by eliminating possibilities from intersections of influence. Each cell exerts
a range of influence on all the others cells in the same row, column, and box. Y-wing is a
complex, advanced technique, so we present an example:

Suppose a cell has exactly two possibilities A and B. This cell AB is the pivot. Consider
two cells, AC and BC, which are influenced by AB, but do not influence each other. If they
each share exactly one possibility with AB and exactly one possibility with each other, then
the possibility held in common between AC and BC, C, can be eliminated from every cell in
the intersection of AC and BC’s ranges of influence.

If we finally fill in all the Sudoku squares, we return successfully and try to remove yet another square from the Sudoku board and try and solve that board.

My breakout condition for the Sudoku number removal loop, is set a time limit. My code is sufficiently fast that 2 seconds is plenty to get the Suduku board down to 25 visible numbers.