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) {
all ::= rotate(all.head)
}
//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)