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 exactly once in each row and in each column. The highest two numbers (n, n-1) then become the blocks.
This approach will always deliver a valid arrangement of blocks and numbers. However, a puzzle generated in this way will still need to be checked for solvability, 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.
When all possible arrangements of a latin square are considered for analysis purposes, a large number of the puzzles will be exact 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 will always deliver a valid arrangement of blocks and numbers. However, a puzzle generated in this way will still need to be checked for solvability, 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.
When all possible arrangements of a latin square are considered for analysis purposes, a large number of the puzzles will be exact 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 using pure logic (the puzzle can be solved without guessing a step).
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.