How Do We Create Sudoku?

Because we want to create a Sudoku which has a difficulty in a particular target area, we use a Reductive method. We played around with a few methods, and we found that this was the best method for creating Sudoku – at least for us!

Our creator is actually a wrapped around our solver, so we work by trying lots of puzzles until we get to one which we can solve and fits the kind of puzzle that we want.

Here’s how it works:

1. We start off with a full and complete Sudoku grid

   

2. We shuffle around the rows and columns (you can swap any of the entire rows or columns passing within the same block and it’ll still be a valid ‘complete’ Sudoku.)

   

3. We select a cell at random, and its rotational counterpart, in order to maintain rotational symmetry, and blank them out.

   

4. Repeat again and again, each time with a different random cell and its counterpart…

   

   

   

5. Once we’ve taken out about 15-20 pairs, we start to test that the puzzle is still solvable using the range of logical techniques available.

   The very centre cell doesn’t have a pair, so it can be removed alone.

   

   At this stage the puzzle is likely to be completely solvable with simple single position and candidate tests (in fact, our solver is optimised to do all of the single position and candidate tests in a single rapid pass, which saves a lot of time!)

   Each time we remove another pair, we test for solvability again, and count up the total difficulty.

   Every extra pair removed adds at least an extra two items (often more!) to the totals of technique applications, so the total difficulty keeps on increasing.

6. The final puzzle!

   

   We carry on doing this until puzzle is within the target range of achievability. Perfect!

Sometimes we remove a pair and the puzzle goes from solvable to unsolvable in that one step. Rather than discard the entire puzzle and all of the work done so far, we just revert back to the previous state and pick a different pair to remove.

Sometimes the total difficulty jumps up by too much to be in the category we want, so again, the latest pair is put back and a different pair chosen.

We’ve used a recursive technique to step back up the tree and select different pairs until a good puzzle is found. However, we don’t carry on forever, if it can’t find a puzzle in the acceptable range after a few hundred step-backs, the whole puzzle is disgarded and the process begins again.

When we were originally making these puzzles for low-powered PDA devices (the original Palm PDAs we were writing for had 16MHz processors, far less than a thousandth of the processing power of a modern smartphone!) it was a challenge to be able to create puzzles on-demand quickly enough for a player eager for their next puzzle. Since each puzzle being created involved “solving” a puzzle many thousands of times over with small variations each time, we worked on optimising the solver quite some way, using things like bitwise logic to spot things like X-Wings and Subsets as quickly as possible. We did find that Forcing Chains was by far the slowest technique, and even now it’s likely to take a device several seconds to find a valid Fiendish or Diabolical puzzle that contains a forcing chain, but a Medium or easier usually only takes a few hundredths of a second to generate.

We have our Sudoku App keeping a reserve of puzzles stored, so as you’re solving a Fiendish puzzle, it’s working in the background to build another one ready for when you’re finished. Hopefully it can keep one step ahead of even the most expert human player!

For the more difficult puzzles, we try to select those that start of with an ‘easy run’ where you can make some progress with a few initial easy techniques, before requiring the advanced techniques. This helps to avoid the “This puzzle is simply impossible!” effect.

Lastly, when we’re choosing puzzles to go into books and magazines, we look for those that have interesting and aesthetically pleasing shapes – after all, if you’re going to be looking at the puzzle for quite some time, isn’t it better to have them be nice?

Is Each Sudoku Unique?

There are billions of possible Sudoku puzzles that are valid, but it turns out that they aren’t all as unique as you might think!

Some puzzles are logically equivalent, even though they don’t look exactly the same.

Here’s the same puzzle again:

Rotation

Here’s the same grid rotated clockwise by one quarter turn. It’s logically exactly the same, but it immediately looks different.

Mirroring

Here’s the puzzle again, but mirrored left-to-right

Transposition

And again; we can swap entire rows with each other, as long as they’re within the same block group, and the puzzle remains logically the same.

We have to do pairs of pairs, in order to maintain the symmetry of course.

Ciphering

Sudoku is not really about arithmetic at all, the numbers in each cell are just symbols. You could replace the symbol for a “7” with anything (as long as you did it throughout) and it would be just as valid a puzzle requiring exactly the same logical techniques. You could replace them with letters, fruit, different chess pieces, or even abstract shapes. Of course, it’s easier for us to stick to numbers!

Here’s an example with each value swapped to the next one up – 1 becomes 2, 2 becomes 3, etc., and 9 becomes 1.

There’s no reason to stick to such an easy switch-around, here it is again but the numbers are mapped in a random order!

So how many different Sudoku could be made from one original puzzle?

A lot more than you’d think!

For any given puzzle:

• There are 4 rotations possible.
• There are two options for mirroring (vertically or horizontally), each of which can be used or not, so that makes another multiple of 4.
• There are 6 ways to shuffle the top 3 rows (and the bottom three have to match to retain symmetry), and the middle block can be shuffled in 2 ways (the very central row can’t be moved), so that makes 12 row transposition options. Likewise, there are 12 column transposition options, so we have 12 × 12 = 144 variants we can make just with transpositions.
• Ciphering is what really multiplies it up though! There are 9! (9 factorial) ways to allocate the numbers, that’s 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 = 362880 different variations!

If you’re willing to apply all of these, that’s 4 × 4 × 144 × 362880 = 836,075,520 variants. Round it up (what’s a few million between friends!) and that’s a Billion different combinations, starting with the same puzzle, every one of which can be solved with exactly the same sequence of logical techniques in the same order.

We use this in our daily puzzles, so that each player gets their own variant of the puzzle, but we know they are all equivalent for when they submit times. This makes it rather more effort for a player to cheat by copying down the answers from the website (or the ‘solution’ on another device) to enter quickly so they can submit a mythical 1 minute time to solve a diabolical without using pencilmarks 😀