How is a puzzle generated?
One way to generate a new puzzle is to start with a latin square, in which a grid of size n x n is filled with the numbers 1-n, with each number appearing once in each row and in each column. The highest two numbers (n, n-1) then become the blocks. However, it must also be checked that the resulting puzzle is solvable, that is, it must be possible to start with an empty grid and fill all the cells on the basis of the clue values alone. The solution must also be unique.
This approach ensures that the resulting puzzle conforms to the basic constraints (2 blocks in each row and column, all other values appearing only once in each row and column). However, it also leads to a large number of duplicates due to the way the blocks are allocated. For example, when using this approach to generate a 5x5 puzzle, the numbers 4 and 5 would become the blocks. If the positions of all 4s and 5s would be swapped, the resulting puzzle would still be the same.
This approach ensures that the resulting puzzle conforms to the basic constraints (2 blocks in each row and column, all other values appearing only once in each row and column). However, it also leads to a large number of duplicates due to the way the blocks are allocated. For example, when using this approach to generate a 5x5 puzzle, the numbers 4 and 5 would become the blocks. If the positions of all 4s and 5s would be swapped, the resulting puzzle would still be the same.
What re-arrangements of a puzzle are possible?
Since the clue values are intrinsic to the puzzle, it is not usually possible to interchange the digits within a puzzle. This is in contrast to a Sudoku puzzle, which is essentially an algebraic problem where all values are interchangeable, even with non-numerical values such as "fruits".
It is however the case, that any single puzzle can be transformed in a number of ways without violating its integrity:
It is however the case, that any single puzzle can be transformed in a number of ways without violating its integrity:
- the clues for the rows and columns can be swapped
- the clues for the rows can be reversed
- the clues for the columns can be reversed
How many unique puzzles are there?
An analysis of all the puzzles that can be generated from a latin square (as outlined above) for grid sizes 3x3 to 5x5 gave the following results:
| Grid size | No. valid grid arrangements | No. solvable puzzles | No. unique puzzles |
|---|---|---|---|
| 3x3 | 12 | 8 | 1 |
| 4x4 | 576 | 304 | 19 |
| 5x5 | 161,280 | 83,712 | 4,256 |
For larger puzzles, the number of valid grid arrangements grows very fast, but it also becomes increasingly difficult to find arrangements that represent solvable puzzles. When 9x9 is reached, it would seem that only 1 in approx. 8 million grid arrangements represents a valid puzzle that can be solved from an empty state purely with (explainable!) logic.
What is the minimum number of clues needed to solve a puzzle?
When looking to omit values, it would seem that smaller puzzles have more redundancy than larger puzzles. The table below shows an analysis of all unique puzzles for grid sizes 3x3 to 5x5:
| Grid size | No. clues | Max. omitted | Min. remaining |
|---|---|---|---|
| 3x3 | 6 | 4 | 2 |
| 4x4 | 8 | 5 | 3 |
| 5x5 | 10 | 6 | 4 |
As can be seen above, 5x5 puzzles can sometimes be reduced to as few as 4 clues (that is, 6 clues can be omitted). Indeed, it was found that at least 2 clues can be omitted from every 5x5 puzzle. In contrast, many 8x8 puzzles have no redundancy.