Generating Sudokus with pencilmarks only

Ruud · Site Admin

I recently adapted my DLX code to generate Sudokus that do not have any given numbers, but only a pencilmark grid. The normal Sudoku rule applies, but it should be possible to perform the same trick for variants with additional constraints.

As programmers, we know that the only data needed to solve a Sudoku is the candidate space. Each given number can theoretically eliminate 28 candidates, but overlaps are unavoidable.

I did some random checks in Gordon's collection of 17-clue Sudokus. The theoretical maximum eliminations: 17*28 = 476, leaving 253 candidates. Because there are 17 solved cells, there could be 236 unbound candidates. On average, there are 70 redundant eliminations for 17 clues, so we're looking at 300-310 candidates that we can use to solve the puzzle. If we can find a way to increase this number, the resulting Sudokus should be more difficult than those with fewer candidates.

Because the candidates are always eliminated in fixed patterns (row+column+box), we are missing the cases where only a few candidates in a house are eliminated, without the spot being occupied with another digit. I tried to fill this gap by eliminating individual candidates.

Elimination of individual candidates gives us a new definition of minimal. A puzzle is truly minimal when each extra candidate would lead to multiple solutions. No need to say that this is more precise than removing a clue.

I am using the following method:

- Assign a random number to each candidate and sort the list.
- For each candidate in the list:
- - When all constraints that the candidate belongs to have a size > 2
- - - Disable the candidate
- - - Solve with DLX
- - - Enable the candidate when solutioncount = 0
- - - Finish when solutioncount = 1

To speed things up, I do not invoke the solver before I eliminated 200 candidates. When the first solving attempt fails, the process is restarted.

It is possible to fine-tune this process by altering the constraint size limit. A minimum size of 3 also works fine. I've already experimented with size 4 and it gave me a puzzle that requires a guess as the first move.

It is clear that Sudokus can be made much harder this way. Some of the puzzles I made score 3 times the rating of the hardest Sudokus with clues. Line-box interactions are always required, empty rectangles occur more frequent than in regular Sudokus and I've already seen a significant increase in naked and hidden quads. There are ALS-xz steps that use 2 Almost Locked Sets of size 8.

If you want to try some puzzles:

An easy puzzle can be found on my special page.
I posted 3 incredibly tough puzzles (including the size-4) on the Players forum.

Here is a relatively easy puzzle that requires a hidden quad (in the 3rd step):

daj95376 · Posted: Fri Oct 13, 2006 4:15 pm Post subject:

Why don't you provide a PM Sudoku to the guy whose looking to place a Sudoku in his collection of puzzles for a contest! It should be just the right variant for his needs.

Ruud · Site Admin

Excellent idea daj, I will send him a PM.

elliot · Posted: Mon Oct 30, 2006 11:18 pm Post subject:

well done