On Miracle Sudoku

May 11, 2020

The Miracle Sudoku was introduced by Mitchell Lee, who gave a board containing only two given digits, a 1 and a 2.

I was introduced to this Sudoku variant (and Lee’s board) by Simon Anthony of Cracking the Cryptic: https://www.youtube.com/watch?v=yKf9aUIxdb4.

Sudoku and Chess Sudoku constraints are purely combinatorial, meaning a board with fewer than 8 given digits cannot be uniquely solvable. The consecutive constraint, however, allows for a dramatic reduction in the number of given digits.

I decided to explore solutions to Miracle Sudoku by viewing them as an exact cover problem, solved in Python using Donald Knuth’s “dancing links” implementation of Algorithm X. I hope to write up my implementation in a future programming post.

Rules of the game:

A Miracle Sudoku is a variant Sudoku with the following additional constraints:

Two “Chess Sudoku” constraints:
Cells which are separated by a Chess King’s move cannot contain the same digit.
Cells which are separated by a Chess Knight’s move cannot contain the same digit.
A consecutive constraint:
No two orthogonally adjacent cells may contain consecutive digits.

Any fully-filled Sudoku board can be rotated or reflected to obtain another fully-filled Sudoku board, logically equivalent to the original. It is not hard to see that each fully-filled Miracle Sudoku board corresponds to a full set of 8 distinct equivalent versions of itself via such dihedral symmetries.

In a variant Sudoku with a purely combinatorial ruleset, any of the 9!=326,880 permutations of the label set preserves the ruleset, but there is only one permutation of the labels on a Miracle Sudoku which will preserves the adjacency constraint: inverting the labels of the digits 1 through 9 (relabelling each 9 as a 1, 8 as a 2, etc).

Theorems:

There are exactly 72 fully-filled Miracle Sudoku boards.
There are a total of 72/8 = 9 essentially unique fully-filled Miracle Sudoku boards up to rotations and mirroring, one for each choice of the center digit as 1 through 9.
Including both mirroring and inverting the labels 1 through 9, there are only 5 essentially unique fully-filled Miracle Sudoku boards, one for each choice of the center digit as 1 through 5.
Any fully-filled Miracle Sudoku board can be obtained as the unique solution to a Miracle Sudoku puzzle with only two givens.
There is no uniquely-solvable Miracle Sudoku puzzle with only one given.
In fact, the givens in any uniquely solvable Miracle Sudoku puzzle must bear at least two distinct numerals (in distinct rows and columns).
There are 174,816 ways to set two givens such that the resulting Miracle Sudoku puzzle is uniquely solvable.
This gives 174,816/8 = 21,852 essentially unique Miracle Sudoku puzzles bearing two givens (although many of these will quickly converge on each other when solving).
A random choice of two distinct givens will result in a valid, uniquely solvable Miracle Sudoku puzzle just under 75% of the time.
A table of the 5 essentially unique Miracle Sudoku solutions is presented below, along with a table of all the full 72.

Table of Miracle Sudoku boards

I’ve included a table below of the five essentially-unique Miracle Sudoku boards up to dihedral symmetries and relabeling. You can spot some remarkable symetries in the layout of digits.

Click to expand ...

Here are a couple constructed Miracle Sudoku puzzles:

Click to expand ...

---
4........
.........
.........
.........
.........
.........
.........
..1......
.........
---
.........
.........
..5......
.........
.........
.........
1........
.........
.........

tagged in sudoku exact cover project