Preventing Multiple Puzzle Solutions

I've released version 2.0 of my Sudoku Maker program. When I first coded the program, I assumed the hard part was finding all the numbers to make up a Sudoku table. The problem of which squares to blank out seemed easy. After some reading and studying, I realize this is backwards. The hard part is determining which squares to blank out or mask.

The first thing I realized that the hardness level is not determined by only the number of masked squares. Two puzzles can have the same number of masked squares and be drastically different in difficulty. My program determines which numbers to mask in a random method and the easier levels mask fewer numbers. In future versions I'll try to develop better algorithms.

Random masking has a more serious problem in Sudoku puzzles. That problem is the possibility that a puzzle could have multiple solutions. In this second version of my program, I've added two functions that greatly reduce the chance of multiple solutions.

After version 1.0 I noticed two cases that can cause multiple solutions. First is when there are four numbers in two separate 3x3 boxes that are masked. This is shown in example one below. The multiple solutions have the 8 and the 1 in bold. In this example the 8 and the 1 for both columns can be flipped. This flipping maintains the 3x3 box and column requirements of no repeat numbers. By flipping the 8 and 1 in both columns, the row requirement is maintained.

These 2x2 combinations can also appear from top and bottom in addition to left and right. Also, these are quite common. To ensure a unique solution, my version 2.0 program looks for these 2x2 combinations after I generate the 9x9 numbers. I then randomly pick one of the four numbers that cannot be masked. If at least one of the four numbers is not masked, only one solution is possible.

After some more thought I realized that other combinations may cause similar multiple Sudoku solutions. After a lot of experimentation, I came up with a 3x3 combination that can cause multiple solutions that is similar to the 2x2 box. This is shown in example two below. In this case, a column of 3 numbers exist in 3 different 3x3 regions. If all 9 numbers are masked, there exists 6 possible solutions to the Sudoku puzzle. As before this can be prevented my ensuring at least one of the nine numbers are masked. As you would suspect, this 3x3 combination is much less likely than the 2x2 combination.

As more and more squares are masked, the chance of multiple solutions is likely to rise. I'm sure there are likely other combinations that I have not considered that could create multiple solutions. If you know of other combinations that can create multiple solutions, please leave a comment.

Example One - 2x2 Combination

The puzzle to the right has has 2 solutions due to the 4 specific blank squares. The two tables below show the 2 solutions. The top and bottom 8 and 1 can be interchanged and still meet the row, column and 3x3 box requirements of Sudoku.		3 7 8 6 5 9 2 1 4 1 5 4 3 2 8 7 6 9 6 2 9 4 7 1 5 3 8 7 4 3 5 6 9 2 8 6 2 9 4 7 3 5 1 9 1 5 2 3 6 8 4 7 4 8 7 5 9 3 1 2 6 2 3 6 4 9 7 5 5 9 1 7 6 2 4 8 3
3 7 8 6 5 9 2 1 4 1 5 4 3 2 8 7 6 9 6 2 9 4 7 1 5 3 8 7 4 3 1 8 5 6 9 2 8 6 2 9 4 7 3 5 1 9 1 5 2 3 6 8 4 7 4 8 7 5 9 3 1 2 6 2 3 6 8 1 4 9 7 5 5 9 1 7 6 2 4 8 3		3 7 8 6 5 9 2 1 4 1 5 4 3 2 8 7 6 9 6 2 9 4 7 1 5 3 8 7 4 3 8 1 5 6 9 2 8 6 2 9 4 7 3 5 1 9 1 5 2 3 6 8 4 7 4 8 7 5 9 3 1 2 6 2 3 6 1 8 4 9 7 5 5 9 1 7 6 2 4 8 3

Example Two - 3x3 Combination

The puzzle to the right has 6 solutions. The numbers 2, 5 and 7 are required in all three blank columns. Each column must have a different order of these numbers to maintain the row requirement. Each column may contain any of the 3 combinations just so each column has a different order.		3 8 6 9 1 4 1 4 3 8 6 9 6 9 4 1 3 8 7 4 3 1 8 5 6 9 2 8 6 2 9 4 7 3 5 1 9 1 5 2 3 6 8 4 7 4 8 7 5 9 3 1 2 6 2 3 6 8 1 4 9 7 5 5 9 1 7 6 2 4 8 3
3 7 8 6 5 9 2 1 4 1 5 4 3 2 8 7 6 9 6 2 9 4 7 1 5 3 8 7 4 3 1 8 5 6 9 2 8 6 2 9 4 7 3 5 1 9 1 5 2 3 6 8 4 7 4 8 7 5 9 3 1 2 6 2 3 6 8 1 4 9 7 5 5 9 1 7 6 2 4 8 3		3 7 8 6 2 9 5 1 4 1 5 4 3 7 8 2 6 9 6 2 9 4 5 1 7 3 8 7 4 3 1 8 5 6 9 2 8 6 2 9 4 7 3 5 1 9 1 5 2 3 6 8 4 7 4 8 7 5 9 3 1 2 6 2 3 6 8 1 4 9 7 5 5 9 1 7 6 2 4 8 3
3 5 8 6 2 9 7 1 4 1 2 4 3 7 8 5 6 9 6 7 9 4 5 1 2 3 8 7 4 3 1 8 5 6 9 2 8 6 2 9 4 7 3 5 1 9 1 5 2 3 6 8 4 7 4 8 7 5 9 3 1 2 6 2 3 6 8 1 4 9 7 5 5 9 1 7 6 2 4 8 3		3 5 8 6 7 9 2 1 4 1 2 4 3 5 8 7 6 9 6 7 9 4 2 1 5 3 8 7 4 3 1 8 5 6 9 2 8 6 2 9 4 7 3 5 1 9 1 5 2 3 6 8 4 7 4 8 7 5 9 3 1 2 6 2 3 6 8 1 4 9 7 5 5 9 1 7 6 2 4 8 3
3 2 8 6 7 9 5 1 4 1 7 4 3 5 8 2 6 9 6 5 9 4 2 1 7 3 8 7 4 3 1 8 5 6 9 2 8 6 2 9 4 7 3 5 1 9 1 5 2 3 6 8 4 7 4 8 7 5 9 3 1 2 6 2 3 6 8 1 4 9 7 5 5 9 1 7 6 2 4 8 3		3 2 8 6 5 9 7 1 4 1 7 4 3 2 8 5 6 9 6 5 9 4 7 1 2 3 8 7 4 3 1 8 5 6 9 2 8 6 2 9 4 7 3 5 1 9 1 5 2 3 6 8 4 7 4 8 7 5 9 3 1 2 6 2 3 6 8 1 4 9 7 5 5 9 1 7 6 2 4 8 3