|
|
|
Diagonalization |
| |
While researching methods to use for speeding up the process to randomly generate very difficult Sudoku puzzles, we discovered an interesting phenomenon called diagonalization - that is that if you place your givens in diagonal boxes and diagonal cells within the boxes, then there is a much higher statistical probability that an extremely difficult Sudoku will emerge. Diagonalization is used in Sudoku Snake when using the random puzzle generator to create puzzles of skill level Expert or higher.
The basic definition of a diagonal arrangement as used here is that a given is not repeated in a row or column. There are 6 different types of diagonal arrangement to choose from as seen below.
Choose an arrangement at random for each box and place givens only in those cells. Note that it's perfectly acceptable to leave a few of the cells blank - you still don't infringe on the basic definition above.
You will also need to place given values in diagonal box arrangements - that is that you should not repeat a given value in any row of boxes or column of boxes. For instance, if you choose the first diagonal arrangement for all of your 3's, then you should place your 3's somewhere in the top-left box, center box, and bottom-right box only. This means that for optimal diagonalization you should not use more than three of any given value.
The theory behind diagonalization is that if you don't repeat givens in columns or rows, then you preserve a wide variety of candidates in those columns and rows, and the more variety of candidates you have, the more difficult of solving techniques is required to crack them.
The example below is an example of almost pure diagonalization. The only exception is that there are two 9's in the bottom row of boxes and two 9's in the right column of boxes. If the 9 in the bottom-right corner were instead a 5 then this would be pure diagonalization. At this point some givens can be taken away to increase the difficulty of the puzzle.
Note that small anomolies or variations are okay and sometimes necessary when creating diagonal puzzles. You'll see that some of the world's hardest puzzles such as Easter Monster and Golden Nugget are diagonal except for one or two changes. These small changes can create a tiny fissure or logical weakness necessary to turn a multiple-solution difficult puzzle into one with a unique solution.
|
|
|
|
|
|
|
|
