# How many unique "miracle sudokus" are there?

The following "Miracle Sudoku" puzzle contains only two starting numbers, plus some additional rules that end up revealing the whole board: https://www.youtube.com/watch?v=yKf9aUIxdb4

(or Sudoku variation: Using various chess moves, solve the grid from just two numbers for the same thing on this site)

Repeating the rules here:

Starting information:

... ... ...
... ... ...
... ... ...

... ... ...
..1 ... ...
... ... 2..

... ... ...
... ... ...
... ... ...

Placement rules:

• Normal Sudoku rules apply.
• Any two cells separated by a knight's move or a king's move (in chess) cannot contain the same digit.
• Any two orthogonally adjacent cells cannot contain consecutive digits.

Solving the puzzle, it's fascinating how that little bit of starting information reveals the whole solution, and the final solution contains significant symmetry. That led me to wonder, how many distinct solutions meet the placement rules, starting with an empty grid? If there's many distinct solutions, can we at least concisely enumerate them all (e.g. along the lines of "all permutations of XYZ").

Clearly, any solution can be rotated or mirrored, as with normal Sudoku. Also, any solution can have the numbers 1-9 inverted. I wonder if the result ends up similar to how there is exactly one 3x3 magic square up to symmetry.

I'm hoping for an elegant way to reason through this, or any general mathematical results similar to https://en.wikipedia.org/wiki/Mathematics_of_Sudoku, rather than an un-enlightening brute force search.

An un-enlightening brute force computer search yielded the following 5 solutions, excluding rotation, reflection, and inversion. Inspecting these solutions, it turns out that 1 and 9 are never adjacent. Thus, in addition to inverting 1-9, we can also shift them (i.e. 123...789 -> 234...891). After deduplicating shifts, it turns out there's only one "miracle sudoku"!

It is not clear to me if there's a deeper reason why this is the answer.

159 483 726
726 159 483
483 726 159

615 948 372
372 615 948
948 372 615

261 594 837
837 261 594
594 837 261
159 483 726
483 726 159
726 159 483

594 837 261
837 261 594
261 594 837

948 372 615
372 615 948
615 948 372
615 948 372
948 372 615
372 615 948

159 483 726
483 726 159
726 159 483

594 837 261
837 261 594
261 594 837
726 159 483
159 483 726
483 726 159

261 594 837
594 837 261
837 261 594

615 948 372
948 372 615
372 615 948
594 837 261
261 594 837
837 261 594

159 483 726
726 159 483
483 726 159

615 948 372
372 615 948
948 372 615

Scala:

import java.util.Arrays

def bitMask(digit: Int): Int = 1 << (digit - 1)

def clearRowCol(possible: Array[Int], digit: Int, r: Int, c: Int): Unit = {
for (i <- 0 until 9) {
possible(i * 9 + c) &= ~bitMask(digit)
possible(r * 9 + i) &= ~bitMask(digit)
}
}

def clearCell(possible: Array[Int], digit: Int, R: Int, C: Int): Unit = {
for (i <- 0 until 3) {
for (j <- 0 until 3) {
possible((R * 3 + i) * 9 + (C * 3 + j)) &= ~bitMask(digit)
}
}
}

def tryClear(possible: Array[Int], digit: Int, r: Int, c: Int): Unit = {
if (r >= 0 && r < 9 && c >= 0 && c < 9) {
possible(r * 9 + c) &= ~bitMask(digit)
}
}

def clearKingKnight(possible: Array[Int], digit: Int, r: Int, c: Int): Unit = {
// king corners
tryClear(possible, digit, r - 1, c - 1)
tryClear(possible, digit, r - 1, c + 1)
tryClear(possible, digit, r + 1, c - 1)
tryClear(possible, digit, r + 1, c + 1)

// knight
tryClear(possible, digit, r - 1, c - 2)
tryClear(possible, digit, r - 1, c + 2)
tryClear(possible, digit, r + 1, c - 2)
tryClear(possible, digit, r + 1, c + 2)
tryClear(possible, digit, r - 2, c - 1)
tryClear(possible, digit, r - 2, c + 1)
tryClear(possible, digit, r + 2, c - 1)
tryClear(possible, digit, r + 2, c + 1)
}

def clearOrthogonal(possible: Array[Int], digit: Int, r: Int, c: Int): Unit = {
if (digit >= 1 && digit <= 9) {
tryClear(possible, digit, r + 1, c)
tryClear(possible, digit, r - 1, c)
tryClear(possible, digit, r, c + 1)
tryClear(possible, digit, r, c - 1)
}
}

def place(possible: Array[Int], digit: Int, r: Int, c: Int): Unit = {
assert((possible(r * 9 + c) & bitMask(digit)) != 0)

clearRowCol(possible, digit, r, c)
clearCell(possible, digit, r / 3, c / 3)
clearKingKnight(possible, digit, r, c)
clearOrthogonal(possible, digit - 1, r, c)
clearOrthogonal(possible, digit + 1, r, c)

possible(r * 9 + c) = bitMask(digit)
}

def placeDigitInRow(possible: Array[Int], digit: Int, r: Int, depth: Int): Unit = {
//System.err.println(" " * depth + f"Placing $$digit in row=$$r")
if (digit == 10) {
if (isCanonical(possible)) {
println(dump(possible, 0, false))
println()
println("-" * 11)
println()
}
} else if (r == 9) {
// successfully placed digit in all rows
// move on to next digit
placeDigitInRow(possible, digit + 1, 0, depth)
} else {
for (c <- 0 until 9) {
if ((possible(r * 9 + c) & bitMask(digit)) != 0) {
val clone = possible.clone
//System.err.println(" " * depth + f"Placing $$digit in row=$$r, col=$c") place(clone, digit, r, c) //System.err.println(dump(clone, depth, true)) placeDigitInRow(clone, digit, r + 1, depth + 2) } } } } /** turns out this search is a few seconds slower */ def placeInIndex(possible: Array[Int], i: Int, depth: Int): Unit = { val (r, c) = (i / 9, i % 9) //System.err.println(" " * 2 * depth + f"Placing in row=$$r, col=$$c") if (i == possible.length) { if (isCanonical(possible)) { println(dump(possible, 0, false)) println() println("-" * 11) println() } } else { for (digit <- 1 to 9) { if ((possible(i) & bitMask(digit)) != 0) { val clone = possible.clone //System.err.println(" " * 2 * depth + f"Placing $$digit in row=$$r, col=$c")
place(clone, digit, r, c)
//System.err.println(dump(clone, depth * 2, true))
placeInIndex(clone, i + 1, depth + 1)
}
}
}
}

/** define canonical one to be the lexicographically first */
def isCanonical(possible: Array[Int]) = {
var all = List(possible)
for (i <- 1 to 3) {
}
//val a = all.map(sortKey).toSet.size
all ++= all.map(flip)
//val b = all.map(sortKey).toSet.size
all ++= all.map(invert)
//val c = all.map(sortKey).toSet.size
val min = all.minBy(sortKey)
//System.err.println((all.length, a, b, c))
Arrays.equals(possible, min)
}
def sortKey(possible: Array[Int]) = {
val s = dump(possible, 0, false)
val idx = s.indexOf("159")
(if (idx == -1) Int.MaxValue else idx, s)
}
def rotate(possible: Array[Int]): Array[Int] = {
val rotated = new Array[Int](possible.length)
for (r <- 0 until 9) {
for (c <- 0 until 9) {
val r2 = c
val c2 = 8 - r
rotated(r2 * 9 + c2) = possible(r * 9 + c)
}
}
//System.err.println(dump(rotated, 0, false))
rotated
}
def flip(possible: Array[Int]): Array[Int] = {
val flipped = new Array[Int](possible.length)
for (r <- 0 until 9) {
for (c <- 0 until 9) {
val c2 = 8 - c
flipped(r * 9 + c2) = possible(r * 9 + c)
}
}
//System.err.println(dump(flipped, 0, false))
flipped
}
def invert(possible: Array[Int]): Array[Int] = {
possible.map(x => Integer.reverse(x) >>> (32 - 9))
}

def dumpBitSet(set: Int): String = {
(1 to 9).map(d =>
if ((set & bitMask(d)) == 0)
" "
else
d.toString
).mkString("[", "", "]")
}

def dump(possible: Array[Int], indent: Int, verbose: Boolean): String = {
val output = new StringBuilder
for (r <- 0 until 9) {
output.append(" " * indent)
for (c <- 0 until 9) {
val set = possible(r * 9 + c)
if (verbose) {
output.append(dumpBitSet(set))
} else {
if (set == 0) {
output.append(' ')
} else if (Integer.bitCount(set) == 1) {
val digit = Integer.numberOfTrailingZeros(set) + 1
output.append(digit)
} else {
output.append('.')
}
}
if (c % 3 == 2 && c < 8) {
output.append(' ')
}
}
if (r < 8) {
output.append('\n')
if (r % 3 == 2) {
output.append('\n')
}
}
}
output.toString
}

val startingPossible = Array.fill[Int](81)((1 << 9) - 1)
//place(startingPossible, 1, 4, 2)
//place(startingPossible, 2, 5, 6)
//System.err.println(dump(startingPossible, 0, true))
placeDigitInRow(startingPossible, 1, 0, 0)
//placeInIndex(startingPossible, 0, 0)
• It's an interesting problem, but I don't understand why the two seed numbers shown in "Starting information" are not in those places in your solutions. What am I missing? Commented May 23, 2020 at 18:45
• I've removed rotations/reflections/inversions. The solution to the original puzzle is the same as the first one here, after inverting 1-9 and flipping left/right.
– blah
Commented May 23, 2020 at 18:59
• Oh I get it. My bruteforce/canny code finds 72 solutions for the "empty grid" in about 1 second, without looking at any kind of duplication. It finds a single solution to the two-seed problem posted above, as in the earlier question. Commented May 23, 2020 at 20:42