4
$\begingroup$

A Sudoku puzzle with order $n$ has $n^2 \times n^2$ squares and $n^2$ regions.

For example, a Sudoku puzzle of order $n = 3$ has $9 \times 9$ squares and $9$ regions.

A minimal Sudoku is one with the fewest number of starting clues.

For 1x1 Sudoku of order n=1, the minimum number of starting clues is 1.

For 4x4 Sudoku of order n=2, the minimum number of starting clues is 4.

For 9x9 Sudoku of order n=3, the minimum number of starting clues is 17.

What is the minimum number of starting clues for 16x16 Sudoku of order n=4?

Furthermore, if possible, what is the expression for the relationship between the minimum number of starting clues and order n?

$\endgroup$
5
$\begingroup$

Given that the solution of the minimal $9 \times 9$ sudoku took the equivalent of 7.1 million core hours on a supercomputer over 11 calendar months, I suspect that the minimum number for a $16 \times 16$ sudoku will not be solved in the next several decades, even allowing for Moore's Law. Forget $25 \times 25$.

$\endgroup$
  • $\begingroup$ That does not mean we can't try to solve it mathematically instead! Humanity shall prevail. $\endgroup$ – CarolineRudolph Mar 4 '17 at 13:21
  • 1
    $\begingroup$ @CarolineRudolph: I admire your confidence in "humanity" but as a former professor in both mathematics and computer science (and a former Sudoku addict), I must say that the "rock star" problem of minimal number of constraints just smacks of computation, not math. Related problems (magic squares) have resisted math attacks for millennia. Incidentally, I highly recommend the book "Taking Sudoku seriously" by Jason Rosenhouse and Laura Taalman. Also search YouTube for my TEDx (StanleyPark) talk on sudoku. $\endgroup$ – David G. Stork Mar 4 '17 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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