4
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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)
Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Weather Vane
    May 23, 2020 at 18:45
  • $\begingroup$ 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. $\endgroup$
    – blah
    May 23, 2020 at 18:59
  • $\begingroup$ 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. $\endgroup$
    – Weather Vane
    May 23, 2020 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.