14
$\begingroup$

Inspired by this question, consider hints on a Sudoku board. A regular puzzle has a unique solution. It is clear that there are puzzles with 2 or 3 solutions, and therefore, I guess, puzzles with say 4, and 6 solutions.

Now, what is the smallest integer $k$ such that there is no set of Sudoku clues resulting in exactly $k$ solutions?

$\endgroup$
3
  • $\begingroup$ Related question: If you're making the puzzle, how do you know you've given enough information for the solver to solve it (short of trying to do the puzzle)? I've been wondering how they make kenken puzzles. $\endgroup$ – Jeff Jun 7 '14 at 14:55
  • 3
    $\begingroup$ @Jeff: General Sudoku ($n^2 \times n^2$ board) is NP-complete. The and the 9x9-board can be reduced to a SAT-problem, so it depends on your efficiency of the SAT-solver. However, this is equivalent to trying to solve the puzzle, I would say. If there was a quick way for 9x9-then most likely, this generalizes to all sizes, and you would become famous/assassinated by CIA. $\endgroup$ – Per Alexandersson Jun 7 '14 at 14:59
  • $\begingroup$ Yes, maybe do a computer search... that would be a fun computer exercise! $\endgroup$ – Per Alexandersson Aug 22 '15 at 14:13
3
+100
$\begingroup$

Like it usually happens with these conjectures, if the solution is not k=7 or k=11, it may be really hard to find. Of course, there exists a solution, for there is a maximum (huge) number of solutions that a blank sudoku allows. A property that may help to construct solutions is that for small values, if we have a sudoku that allows a solutions and another that allows b solutions, we can probably find a sudoku that allows a·b solutions. For example:

This allows k=4 fillings: $$ 2,9,6|3,1,8|5,7,4\\5,8,4|9,7,2|6,1,3\\7,1,3|6,4,5|2,8,9\\6,2,?|?,9,7|3,4,1\\9,3,1|4,2,6|8,5,7\\4,7,?|?,3,1|9,2,6\\1,?,7|2,?,3|4,9,8\\8,?,9|7,?,4|1,3,2\\3,4,2|1,8,9|7,6,5 $$

And this allows k=3 fillings: $$ 2,9,6|3,1,8|5,7,4\\5,?,4|9,7,2|6,?,3\\7,?,3|6,4,5|2,?,?\\6,2,5|8,9,7|3,4,1\\9,3,1|4,2,6|8,5,7\\4,7,8|5,3,1|9,2,6\\1,6,7|2,5,3|4,?,?\\8,5,9|7,6,4|1,3,2\\3,4,2|1,8,9|7,6,5 $$

From this, we can easily see that this: $$ 2,9,6|3,1,8|5,7,4\\5,?,4|9,7,2|6,?,3\\7,?,3|6,4,5|2,?,?\\6,2,?|?,9,7|3,4,1\\9,3,1|4,2,6|8,5,7\\4,7,?|?,3,1|9,2,6\\1,?,7|2,?,3|4,?,?\\8,?,9|7,?,4|1,3,2\\3,4,2|1,8,9|7,6,5 $$

allows k = 4·3 = 12 fillings.

Although it is hard to generalize, probably the number you are looking for is prime, because if it was to be a composite number, its factors (smaller than the number) would have to be a number of fillings for some sudoku, and then this non-rigorous multiplication rule would fail.

$\endgroup$
2
  • $\begingroup$ according to wikipedia, the blank sudoku allows 6,670,903,752,021,072,936,960 number of solutions, so the number we seek is less than that :P. Also, I guess this implies that there is no sudoku that admits exactly 6,670,903,752,021,072,936,959 solutions :D $\endgroup$ – Per Alexandersson Aug 28 '15 at 22:58
  • $\begingroup$ Sorry, you're right, I just changed that. $\endgroup$ – gonthalo Aug 28 '15 at 23:46
2
$\begingroup$

This is just a partial answer, which can perhaps be turned into a community wiki, where examples of partial fillings that allow $n$ complete valid fillings.

This admits $k=2$ solutions: \begin{array}{ccccccccc} . & . & . & . & 5 & 1 & 8 & 7 & 6 \\ . & 7 & . & 6 & . & 9 & . & . & 3 \\ 6 & . & 8 & . & . & 2 & . & 9 & . \\ . & 4 & . & 1 & . & . & . & 8 & . \\ . & . & 1 & . & 3 & . & . & . & 4 \\ 8 & . & . & . & . & 7 & 1 & . & . \\ 2 & . & . & 5 & 6 & . & . & 3 & . \\ . & . & . & . & 1 & . & 9 & . & 8 \\ 3 & . & . & . & . & 4 & . & . & . \\ \end{array}

This allows $k=3$ fillings: \begin{array}{ccccccccc} . & . & . & . & . & 1 & 8 & 7 & 6 \\ . & 7 & . & 6 & . & 9 & . & . & 3 \\ 6 & . & 8 & . & . & 2 & . & 9 & . \\ . & 4 & . & 1 & . & . & . & 8 & . \\ . & . & . & . & 3 & . & . & . & 4 \\ 8 & . & . & 9 & . & 7 & 1 & . & . \\ 2 & . & . & 5 & 6 & . & . & 3 & . \\ . & 6 & . & . & 1 & . & 9 & . & 8 \\ 3 & 8 & 7 & . & . & . & . & . & . \\ \end{array}

If my calculations are correct, this allows $k=5$ complete fillings: \begin{array}{ccccccccc} . & . & . & . & 5 & 1 & 8 & 7 & 6 \\ . & 7 & . & 6 & . & 9 & . & . & 3 \\ 6 & . & 8 & . & . & 2 & . & 9 & . \\ . & 4 & . & 1 & . & . & . & 8 & . \\ . & . & 1 & . & 3 & . & . & . & 4 \\ 8 & . & . & . & . & 7 & 1 & . & . \\ 2 & . & . & 5 & 6 & . & . & 3 & . \\ 5 & . & . & . & 1 & . & . & . & 8 \\ 3 & . & . & . & 9 & . & . & . & . \\ \end{array}

Currently, $k=7$ is still unknown.

This is the mathematica code I use to solve Sudokus. It is just basic recursion, and can most likely be optimized a lot.

(* Returns true iff we can place n at r,c in the filling. *)

IsValidQ[partFil_, n_, {r_, c_}] := Module[{sr, sc},
   (* Check row, col, sub-box for already existing. *)
   Catch[
    If[MemberQ[partFil[[r, All]], n], Throw[False]];
    If[MemberQ[partFil[[All, c]], n], Throw[False]];
    sr = Floor[(r - 1)/3]; sc = Floor[(c - 1)/3];
    If[MemberQ[
      Join @@ partFil[[3 sr + 1 ;; 3 sr + 3, 3 sc + 1 ;; 3 sc + 3]], 
      n], Throw[False]];
    True
    ]
   ];

SolveSudoku[partialFilling_List] := Module[{recSolve, sols = {}},
   recSolve[pFil_List] := Module[{nFil},
     Catch[
      Do[
       If[pFil[[r, c]] == 0,

        (* Try all 9 numbers. *)

        Do[If[IsValidQ[pFil, n, {r, c}],
          recSolve[ReplacePart[pFil, {r, c} -> n]]]
         , {n, 9}];

        (* We tried all 9 numbers here. Now abort. *)

        Throw[False]
        ]
       , {r, 9}, {c, 9}];
      AppendTo[sols, pFil];
      (*Print["NSOLS: ",sols//Length];*)
      True
      ]
     ];

   recSolve[partialFilling];
   sols
   ];
$\endgroup$
3
  • $\begingroup$ Care to share your program? $\endgroup$ – Lynn Aug 28 '15 at 17:49
  • $\begingroup$ @Mauris: Sure, i added it now. its pretty basic, but less complicated means fewer bugs usually. $\endgroup$ – Per Alexandersson Aug 28 '15 at 18:52
  • $\begingroup$ I can confirm that the sudoku posted for k=5 does, indeed, have exactly 5 solutions. $\endgroup$ – Jonathan Allan Apr 27 '16 at 22:36
2
$\begingroup$

Here is an example for $k=7$:

\begin{array}{ccccccccc} . & . & . & . & . & . & 7 & . & .\\ 9 & . & 7 & 1 & 2 & 3 & . & 5 & 6\\ 4 & . & 6 & . & 7 & . & . & . & 3\\ 3 & 1 & 2 & 8 & . & 5 & . & 6 & .\\ . & . & . & 3 & . & . & . & 4 & 5\\ 8 & 4 & . & 7 & . & 9 & . & . & .\\ . & . & . & . & 9 & . & 6 & 7 & 8\\ . & . & 8 & . & . & . & 5 & . & .\\ . & . & 4 & . & 8 & . & . & 3 & 1\\ \end{array}

Which resolves to:

\begin{array}{ccccccccc} . & . & . & . & 5 & . & 7 & 8 & 9\\ 9 & 8 & 7 & 1 & 2 & 3 & 4 & 5 & 6\\ 4 & 5 & 6 & 9 & 7 & 8 & 1 & 2 & 3\\ 3 & 1 & 2 & 8 & 4 & 5 & 9 & 6 & 7\\ . & . & 9 & 3 & 1 & 2 & 8 & 4 & 5\\ 8 & 4 & 5 & 7 & 6 & 9 & 3 & 1 & 2\\ . & . & . & . & 9 & . & 6 & 7 & 8\\ . & . & 8 & . & 3 & . & 5 & 9 & 4\\ . & 9 & 4 & . & 8 & . & 2 & 3 & 1\\ \end{array}

Here I extend the prime list of $k$ to the first $142$ primes ($2$ to $821$).

To do so I implemented Knuth's dancing links for Algorithm X, iterated through solves of an empty sudoku, randomly removed between 20 and 53 clues and counted solutions. The first of each prime count was then added to a dictionary. I left it running for about half an hour. Progress had not slowed all that much after the initial burst to around $37$. It discovered another $173$ larger prime solution counts, ranging from $827$ to $17,137$ solutions.

To avoid this post being ridiculously long each is in single line form, and all are in a code block:

  2: 1...5678..8..2345...6..8..331..4.967..7.128.....9....223157469...8.3157..74.89.31
  3: 12...67..78.1234..45.....2.3.2.45..7.673.29...458...1.2.15..6..6...3157.....98.31
  5: ..3.5...9.8......64....9.23.12.....7..73.294.9...6..12231.9.67....2.1594....7.231
  7: ......7..9.7123.564.6.7...33128.5.6....3...4584.7.9.......9.678..8...5....4.8..31
 11: .2...6.8.7.8123456....891233.26..89....3.264...5...3..2.1.....8.7.231.64...8....1
 13: 1.3.5.7...98...4.6.569.81.331.8.5......3.28..8.....3..2315......7..3.5.45.....2..
 17: 1..4.67.99.......6.5..87.2..12....67.693.2.4..4576.3.2.3...4.7...82...9..9.6...3.
 19: ....5.7.98.7..34..4.6......31.....9.9....26.5.4..7931.....6...87..23...45....723.
 23: .2..5..9..7.12..5.456.79.2.31..4...99......456.59....2231...9..7.8.3.5..5.4.9....
 29: 1...5...9..9.....6....8.1233....5....98.126.....89731.2.1.6....9...315.4..4.7.2..
 31: .2.4.689.798.........7.81.........78..9.12.4.64.87....2.15..78..872.1...5.498....
 37: ..3456....9....45..5....123.12.45...9..3....5.......1.2..5...9..8...15..5..9.7.3.
 41: ...45.7.99.812....4..78..2..12.45.9...7312.....59....2........8....31..45..89.2..
 43: ........8897....5.4.6..8...3....5.7....3...45.45.8.3.2.......8797.231.64.64.9.2..
 47: .2..........123.56456.89...3..6.58...7..126....5........1..4.7.79..3........78...
 53: .2.4.6...97.1..4..45...8.23..2..59.......2.45645.7.31....5.4...7.9..1........72..
 59: .......7.97..23456....78.2..........76.3.28...45.693.2...59....6....1....94....3.
 61: ...456.98.87....56...89...3.1.64.....9.3..64...57..3...3.5.......9....645..97...1
 67: .2..5.8......2....45..9..23312.......9..1264..4...9..2..1...9..9..2..5..56..78..1
 71: ..3.....8.8.1234...5...8..3..2...8.696..12.45...8....2..1....8....23.5745749.6.31
 73: .....68.978912.45...68...2.3........86.312945..5...3..2....4........1.945...8..3.
 79: 1.345.......1.34..4..9....3.12.45967.7...284.84..9...22..5...9.9.7.3.............
 83: .23...87..79......45.7.8..3...6......98..2...64598...223..........2.15.4..48.9...
 89: ..345.......1.......6..8......64.8.7...3....564587...223.5.4.6......1..45..9....1
 97: 123.5..8.8.7...4....96...2.....4..6..8...2..........12.315.467.6...31.....4...23.
101: 1...5...896.1.34.7....9...33....58..89..1..........3.22..5..6..6..23157....96823.
103: .2.4.7.68.....345.4....6..331.7..896.........74...8.1..31584...9.....5....4.79.3.
107: 1..4.....79.1..4....6.8.123.1.6......87.....5.4.798....315.......92..5.4.64.7.2..
109: 1..4.679...9..3.......9....31.945.6.768..2.4..456......31..46.9...231..45.4..9...
113: .....67....7..3.5..5.7....3.....5...769...845.4.9...1223...49...9.....7.5746..23.
127: ...459......1.34..4.....1..31.9.5...7..31.....4.678....3.59.87....2..5.4.9..67...
131: .2...7....8.......4...8.12...2.4.......3.2.4..4.89631223.5.4968........45.4.6...1
137: .2.4578.......345.45.....23..2..5........2.4..45..93....1...6899.8.3.5.4.........
139: .234.687.8....3..6..687.1.....64..877.93.2.....5..7..............8..1...56...82..
149: ...45...........5.4...681.3....457...6...2......8...1.....94.8.68723...4....8723.
151: 123..7869..912345.....96.2...27..9....63...............31..4..8..8...5.4.7..6.2..
157: ...4.786...81.3.5.4......2.31..45...8693...4.7.5.96.1....5..69.....3..7........3.
163: .234.6....98.2...6..6...1......4.........2....4....3..2.1.64.78...2.15....49.8.31
167: .2.....8...........5698..2331..4..9....3..74.74..69.12.31...8..6..........4698..1
173: 1.34...796........45..76..3.1..4..67......8...4.769.....1...7.6.96...5.......7.31
179: .2.....8.8691.345745..6.1.3.12..5.6.67......5945..8.1......4.7........9..9.....3.
181: ..34..7......2.4..4.8.7.1.3........7...3.284.84.96.31....5.497....2.15...8.796.31
191: .2.4...9..8.1...5.4........3....5.89...31.64.6459.8...2...64.7.87.2...64..4......
193: ..3..6.....7.2.4...56.9......2....6.....12.....5.78..2231..4.7..7.....8.5.47.92..
197: .....98.78.712..5....76......2.459.........4....8.....2....479.7..23..84..4...2.1
199: ..345...8.97.2..5.4..78..2........87.783.2..5..5..8.....1......78..3.5..5.....23.
211: ...4....66.7.....94......2..1....9...76.1..45845...3....1.9.....6...15...94.8..31
223: 1...5.8.686..2...7....8...3...7......98..274......8...2..57....9.62..57..7..962.1
227: 1...5..69...1.345.4.....12...2.45.......1.....45.9..1.2...7.......23.5.45746...3.
229: .2.....89..9...4...5....123.....56.7...3...4..4...73..231564..897......4.6....23.
233: .2.456.8...........5.7...2.31..45.......12.4.6....9...2.1...97.7.....5.4564...2..
239: ....5.869..8..34.745..9.1.......598.8....2..5...689.....1...6...8.2.1....7...8...
241: ...4...96...12......7...12331.7........312745....983..2.15.....8..2..5.......9...
251: ..34.......61234....96.8.2.3...456.8..8.1.9..9...8....2..86....5.7...8....4......
257: 12.4598.68..12...94.9..6..3..2..5..8.8....945........2...5.....6.8.31.........2..
263: ..........76...45.458....2...284........1284...567..1......4.......3.5845..96.2..
269: ..3.5.69.....2..5.....8.1.331.....86.8......5.4..9.3......7..69...2..57..7486....
271: ...4.6...7.8123..6..6...1...12.4..7....3.....64..............8.9872..5.4564....31
277: 1234..6.....12....4.879...33..8....6.........8..96.....3.5.4.676....15.....6.9.3.
281: .23.58769.6..23..8.......2...28.569.6..3.2.4.84.......2......7...62.1.....4..6.3.
283: 12.45.6...7....45....76......2...98..8....5..6..89..1.....7.....682..794...6...3.
293: 1.34..89..78...4...5...7.233.....7.9..73......45....12.3..6.9....9....64.......3.
307: ....5.8.98.912....4.7..8....1.....9...8..2...6...79.1.2.....97...6.31.8..8.....31
311: .2.4.....6.9.23.58..89..1.3...84...7.673...4......7...2.1..........31.84.8...9...
313: ..3..8.....9...45......9..3..26..789.973..645...9...1........96.8....5..57...62..
317: 12.4.6.......2..5.4........3.254..8.6873....5.4.68......186...9.7......4.6...5...
331: ..3.....8876..........671..3..9.56.77.83.....9....83.2......8766.72..5..5.4...2..
337: .23457.6.9.8.23457..796812....6.5...........56.5.........5....678..31.945.47.62..
347: 12....967....2.......97612.3..8.5.9...9.1...5.........23.....7.7..2.1.....4.9.2.1
349: .23.5.7..97..2.4......79.....264.8....9..26..64..98...2...64..7.9.....64....8..3.
353: ..3..9..7..6....5...9...12....9.5.7.7683....5..56..31.....9.78..872...9..9.7..2..
359: 1.34.....87912.4....69...2.3.....9.....3..64..4....3..2......9..9.2...6.76...923.
367: 12.....98.........4...9..2.31274....9...1.....4..6831..31574..68...3.5........2..
373: .23..6.........4.....8...23.12.45.7.9......4.......31.23.5.47.9.89.....456....2..
379: ..3.5....7.9.....64.6.98.233..9..8...6....9...45..73.......4..96982..5..........1
383: ...4.......6...45.4.8..61...1...9.8..8.....4664...7..22...6.....952..8..8.4...2.1
389: 1.3...7697..1.3.58..86.91....2............8.....9.....2.1..46..967..15.45.47.....
397: 123.......98.......5....12....9...7...63..94...567.3.2.3....7.9..9...5..5.....231
401: .2.....7...6....5.4.......3..25.7....69..2.4.5.7...3..2..68...5.9........8.795231
409: 1.3.5.7............56..9..3.....5...8.....64...5.8.3.2...5.4.7......1564.6.79..31
419: 1........9..12.4..4.....1...126.9..5..531..4964.8..3..2.15.4..7..723.5.45..9.....
421: 12.457.9698.123......6..12......8..9........88..97631.2.1.6.....9.....7.....9..3.
431: 12.......6.7.2.......6.7.2331.9.......6..2..5.457.......159....7.8231...5....6.3.
433: 1.3......7961.....4...7..2..12.49..76...1..49.4..6.............5.9..18.4.6479....
439: 1..458.....6....5....9.61.33.264.........2...64.78..1.2......6...7......89..672..
443: .2...8.79..71.3.58.586.7..33...4.....8..12..5.....63...31.6.............5..8...3.
449: ...4......7...34594.97.6.....2...6.7.....29...4.....1.2..594.6..86....9..9.6.8...
457: ....5.98.9.7...4..4..9..1.....548679.....28....8......23...4....652.....7...652..
461: ....5.9...7.12..5.45...7...3.274.....9.31.74.7...89312.3....8...8.....6.......2..
463: 1.3...6..67.....5.45..7..2.3.......689.31..4..47...3...3........6523..8....7....1
467: 1...........1...7....9..123.12.4...97.5312....46.9..12231.8.5...79...8...........
479: .....6978....2...64..8..12.3.2...78....312..56..78.3...31......9.82..5...........
487: ...45....6...2....4..6...233..9.5..6..6..29.....786.12.31..4..9..523......4.6....
491: 12.4.8......1......58.7612...2.49.6.86..1..4.74.....1.2.1......5.7.......8.5...3.
499: 1...576..6..12.......6..1.3.........796.....5.489...1...1....6..6..3..94.7..6..31
503: ..3...89..9.123....56.9...3..25....8.6.31.....45.........6..98.5....1......9.5.31
509: ......8....7..3.5.4.6.8....3127..69.........8.4..9.3..2....498.8.9...5..5..8.9.3.
521: .234.7....691.34.745796.1.33..5.6..9.7....6......89..2...6..........1....9.......
523: ...4......6.1..4.7..7.69...3.29.5..67....29.594..78.......94...6..2.1..4....86...
541: 12.4598..8..1....9..........1.745....6...27.5....6..1..3.5.4.8...7.315..........1
547: 12.4.867.76912..5.....67123.1......6.8...2.....7.......3...4.6..7..3...4.94...23.
557: 12.4.8.7....12..58....6..2.3.2..5.9......2..5......3...3...4...679231.8.....9.2..
563: 12345........2....4...781...1..4....8...1.....4..8.3...31594.876.....5.45....723.
569: ..3.579.6....2.45...7...12.3.2..5.79..8....4........1....7.....5...3.7.4..4.8.231
571: 123.......7......6..6.7.12..1...........1..4.6..7...122....47...8..31.64.6.9.723.
577: 12.4.6....89......4.69..1..3.2..5...69.3.2......76..1....694...8..........4.7.23.
587: .2....976..6...4.5......1.3.12.4..5.5.7.1..4..49.8531..3.....6.....3.8.....56....
593: ...4.7.86.89....5..57.8.12...2....9.9...12.4....89......1....6989.2.1.......6....
599: .....87..7....3458.......2......6.85...3.26.7.475.931....87459....2..8..8...6....
601: ....59...7...2.........61.33.25..9....73....5...9......31.9.58....2317949.4685..1
607: ..345.....7..23.5.4.6..71.33.2.4.....95.12......569.12..........672............31
613: 1.34....66...2..57....89..3.12.4.7......1........9..1...1..4...8.6.3.5.4.5.9..2..
617: ....56.......23.5.4......2....5..76..693......4.679.......9.6.....231..498.76..3.
619: ...45......9123....5....1...1......76.7.128..5.8.6......1.94.....5.3....9.4..523.
631: 1.3....9..9.1..4..4..89.1...12..9...78..1..4.6.....3.2.3.....6.5682..97..........
641: 1.345....7..1..4.6..6......31.8..9...6.3.....847.........584.97..9......5.4..9.3.
643: 12..5.6.8.6.123.5.....8612.....4..6..7..129....56...122.....7..................31
647: ..3.5.....9...3.....7..6.23.12.49.75..5..2..9....7.31..3....56.....31......56823.
653: ....587.9..9......45.7..12......59.6.9631.84.8.596..1..3................5..6.9...
659: 1....76.9.......7....8...23312......6..3..7........31223.....6.9.....8.4..4.7.231
661: .2.4..6.9.9............9...3.2..8....6931.5..5.8..6.1...1....566.5.3..9......5.31
673: 12.4..7...9..23..8...9.7123.....96...6.......5...7...2.....4....5623..74......2.1
677: 1...59......1....9..9.8.123.....8.7.69......8........2.3.8..7.5..5.3.89498...5.3.
683: ..3..9.....8.2.459..96..1.33.2.....69.....5..5.....3..2.1...8..87..3.6946....8..1
691: .2...9....86.....9....76..3.1...8....75..2..86.8.95.12.3...4..........84894.6.231
701: ...45....79.12.4.....89.123..2.........3...............315..8.7..7231..4.547892..
709: .23.5....9..1.3.574579..1..31....6......1.84..4.76..1....6.4......2.176..........
719: .....9..7......4..4....81......46....8..12..6.4.9..3....17.4.8..9..31.7..74.95..1
727: 1.34569..7891...6...67....3...9.75....5..........6.3.2..16.48.7.78........4......
733: 1.345.6.7....2....45.....2..1..469.57..3..84.84.....1.23....5..5.............5.3.
739: 12.........91.34...5.9....3....4.8.998.3...45.4.7.9....3.89.......2.1..4.9..6....
743: ..3...7.9.6.1.3...4..7..1..31.8......9.3..84....9..3...3...49......3..7457468....
751: ..345.7..7......5.4..76.1..31..4....87.........587.3...3...4..7597...8....4...2..
757: ...4.6.98.8...3....5........1..4.8....8.1.6......7......18...6.5.7231.8.8.4.67231
761: 12.4....9......4..457..9..3...........5.12648....7.31...17.4..65.92...8...4......
769: .23...7.687612.4...5...6.2..125....7.....25.85....73.2.31...8...8......4......231
773: 1...........12.....5....1........7.8......645.....9..223189.576.652.1.84..4..6...
787: ..3.5...88....3.57......1..3.2..9........2...9.8675.1.23...4..668.23..9.........1
797: ...45.798.98.........7981.........6.867.....5....8.3...3.8..579..92......8..7..3.
809: .....87......2....4...7.123.1.84...696....84.84576.....3...4.........584.....7.3.
811: 1....86.9.........4..7.....3..5...8.8..31..45547.893....1....97..5.....4.84..52..
821: ..3....696...23.......96.2...2..7..69....25..54..69....3.98...57..23.8.....6.....

Which resolve to:

  2: 123456789789123456456798123312845967..7312845845967312231574698..8231574574689231
  3: 12.4567..78.12345.45.78912.3129458678673129459458673122315746..698231574574698231
  5: .23.5..89.89.23.56456.89.23312945867867312945945.6.312231594678678231594594.7.231
  7: ....5.789987123456456978123312845967..9312845845769312....9.678..8.3.594.94.8.231
 11: 123..6789798123456...7891233126..897987312645..59783122.1.6.9.8879231564...89.2.1
 13: 12345679879812345645697812331.8.5...9..3.28..8.....3..231584...679231584584...231
 17: 1.34.67.99.7...4.6.5.987123312.4.967769312.4.845769312.3..94.7..782...9..9.67..3.
 19: ....5.7898.7..34..4.67....3312.4.897978312645645879312....6..787..23...45....723.
 23: 123.5..9.87912..5.456.79.2.31..4...998.....456459....2231...9..798.3.5..56479.2..
 29: 123.56..98.9123.56....8.123312645...798312645...8973122.1.6....9..2315.4..4.782.1
 31: 123456897798123...4567981..31.64..78879312.4.64.87....2.15.47899872.1...5.4987...
 37: 123456....9.123456.5....123.12.45...9..31...5..5....1.2..5.4.9..892.15..5..9.7.3.
 41: ...45.78997812....45.789.2..12645.97.97312....45978..2....6...8.8..31..45..89.2..
 43: ........8897.23.5.4.6..8...3....5.7...93.2.45.45.8.3.2......9879782315645648972..
 47: 123456789987123456456789...3..6.58.787.3126.5..58.7....31.64.78798.31.64....78...
 53: .2.456...97.12345.45.798.23..2.459...97.12.456458793122..5.4...7.92.15.45.49.72..
 59: .......78978123456.5..78.23...8.....76.3.28..845769312...59....6...31...594.8..31
 61: .2.456798987...456.5.897123.1.64.....9.3..64...57..31..3.56.....79...5645..97..31
 67: .2..5.8......2.45.45.89.123312...7...9.3126456457893122.1...9..9..2.15..564978231
 71: ..3.....8689123457.57..8..3..2...8.6968.12.45..586...2..1...689896231574574986231
 73: .....68.9789123456.568...233....5...8673129459.5..83..2....4...6.8..1.945...8..3.
 79: 1.345....7..1.34..4..9....3312845967.793.284.84..9...22..5...9.9.7.3.........9...
 83: 123...87.879......4567.8..3.126......98..2...64598...2231......9872.15.45648.9...
 89: ..345.......1.......6..8..3312645897...312645645879..2231584769.....1..45.49....1
 97: 12345..8686712.4....96..12..12.45.6..86.12.....5....12231594678678231.....4...231
101: 1...5.9.896.1.34.7....9.1.33....589689.31.745.....93122..5..68.6..23157....96823.
103: .234.7.68.....345.4....6..331.74.896.......4.74...8.1..31584...9.....584..4.79.3.
107: 12.4.....79.1..4..456987123.126......873...45.45798.122315.....8792..5.456487.2.1
109: 1.34.679...9..3.......9....3129458677683129459456......31..46.9.9.2315.45.4.69...
113: ....567.9..7..3.56.5.7....3.....5.97769...845.459.7.1223.57496..9....5745746..23.
127: ...459......1.34..4..7.61..31.945...7..312.4..4.678....3.594876...231594594867...
131: .2...7....8.......45..8.12.3.274.......3.2.4.745896312231574968........45.4.68.31
137: .2.4578......2345.45.....23..2.45..8.....2.45.45..93.22315746899.823.5.45.4...23.
139: .234.687.8....3..64.687.1.....64..877.93.2...6.5..7........4..8..8..1...5647.82..
149: ...45..7..7.12.45.4..768123....4576.76..12.4....876.1....594687687231594...687231
151: 123457869..9123457...896.2...27.59.6..63........6......31.74698..8.31574.7..682..
157: ...4.786...81.3.5.4......2.312745986869312.4.745896.1....5..69.....3..7........3.
163: .234.6....98.2...64.6...123....4.........2....4....3..2.1.64978...2.1564..49.8231
167: .2.....8...........56987.2331.74..9..6.3..74.745869312.31...8..6.........74698.31
173: 1.34..67967....4..45..76..3.1..4..67.67...8...4.769....31...7.6796...5....46.7.31
179: 123..7.8.869123457457869123312..5.6.678....459456.8.12.....4.7........9..9.....3.
181: ..34..7......234..4.867.1.3....4.6.7...3.284.84.96731....5.497....2.15.4584796231
191: .2.4...9.98.1..45.4........312645789798312645645978...2...64.7.87.2...64.64......
193: .23..6.....7.2.4.6.56.97.2...2....6...8.12.....5.78..2231..46796792315845847692..
197: ...4598.78.7123.5....768.....2.459.........4....8.....2....479.7..23..84..4...2.1
199: ..345.7.8897.2..5.45678..2........87.783.2..5..5.78..2..1...87.78..3.5..5..8.723.
211: 1..4....66.71..4.94.....123.1....96.976.1..45845...31...1.9.....6...159..94.8..31
223: 1...5.8.686..2...7...68...3...7.5....98..2745...9.8..22..57....9.62..57..7.896231
227: 12.45..69...12345.45.96.12..12.45.......1..45.45.9..1.23.574......23.57457468..3.
229: .2..5.789..9...456.5....123.....56.7...3..84..4...73..231564978978...564.6....231
233: .2.456.8...........5.7...2.31..45.......12.4.64..79...2.15.497.7.....5.4564..72..
239: ....5.869..81234574578961.......59868....2..5...689.....1...6.8.8.2.1....7...8...
241: 12.4..896...12.457..798.1233127........312745...6983122.15.....8..2.15.....8.92.1
251: .234.......61234....96.8.2.3.29456.8..8.1.9..9.5.8....2.186....5.72..8....45.....
257: 1234598768..123459459..6123..2..5..8.8...2945........22..5.....6.823159.......2..
263: ...4......76...45.458.9..2...284........1284.84567..12.....4.......3.5845.496.2..
269: .23.5.69.....2..5.....8.12331..4..86.8.....45.4..98312....7..69...2..57..7486.231
271: ...4.6...7.8123..64.6...1..312.4..7.87.3.....64............4.8.987231564564...231
277: 123458679...123...458796..33..8....6...3.....8..96.3...3.584.676..2315.....679.3.
281: .23.58769.6..23..8.......2...284569.6..3.284.84.......2......76..62.1.8...4..6.3.
283: 12.45.67..76...45....76..2...2...98..8....54.6..89..1.....7..6..682..794...6...3.
293: 1.34..897.78...45..5...7.233.....7.9.973......45...312.3..6.97...9....64.......3.
307: 1.3.5.8.98.912....4.7..81...1.....9...8.12...64..79.1.231...97...6.31.8..84....31
311: .2.4.8...6.9.23458..89..123...84...7.673...4......7...2.1.84.......31.84.8...9...
313: ..3..89....9...45......9..3..26..789.973..645...9..312.......96986...57.57..9623.
317: 12.4.6.9.7...2.45.4........31254..8.6873...45.4.68......1864..9.7......4.64..5...
331: ..3...768876.........8671..3..9.56877.83.....9....83.2......8766.72..5..5.4...2..
337: 123457.6.968123457457968123...6.5.........6.56.5.........5....67862315945.47.62..
347: 12....9679..12.......97612.31.8.5.9...9.12..5.....9.1.231....7979.2.1.....4.972.1
349: .23.5.7..97..2.4......79.....264.8....9..264.64..98...2...64.87.9.....64....8..3.
353: ..3..9.67..6....59..9...123...9.567.7683..9459.56..31.....9.78..872..59..9.7..23.
359: 1234....98791234564569..1233.....9..9..3..64.64..9.3..23....59.59.23..6.76...923.
367: 12..5..98....2....4...9..2.31274.86.9...1.....4..6831.2315749868...3.5......8.2..
373: 1234.68..8.....4.....8..1233126459789......4.......31.2315.47.9789.....4564...2.1
379: ..3.56.98789....56456.98.233..9..8..86....9..945..73.2.....4..96982..5....4..9..1
383: ...4..6....6...45.4.8..61...12649.8..8.....4664...7.122...6.....952..86.864...2.1
389: 123...7697961234584586791....2........9...8....59.....2.1..46..967..15.45.47.....
397: 123....9..98....5..5....12.3..9...7...63..94.9.567.312.3....7.9..9...5.45.....231
401: .2..5..7...6....5.45..7...3..25.7....69..25475.7...3..2..68..95.95......684795231
409: 1.3.5.7.........5..56..9..3.....5..78.....645..5.8.3.2...564.7......1564564798231
419: 1..4.....9..12.4..4..7..1..312649..57853126496498..3..2.15.4..78.723.5.45.49.....
421: 123457896986123..7...689123.....8..9..9.....88..97631.2.1.6.98..9.....7.....9..3.
431: 1234.....6.7.2....4.96.7.233129......76..2..5.457.....231594...768231...594876.3.
433: 123......7961.....4...7..2..12.49..76...1..4994..6......1......5.9..18.4.6479....
439: 1..458.....6....5....9.61.33.264.........2...64.78..122......6..67......89..672..
443: .23458.79..71.3.58.586.7..33...4.....8.312..5....863...31.6........3....5..87..3.
449: ...4.9..667...34594.97.6.....2...6.7.6...29...4..6..1.2..594.6..86....94.946.8...
457: ...45.98.9.7...4..4..9..1.....548679.....28....8......23...4...8652.....7...652..
461: .2..5.9...7.12..5.45...7.2.31274.....9.31274.7...89312.3....8...8.....6.......2..
463: 123...6..67.....5.45..7..2.312.....689631..4.547...31..31....6..65231.8..847...31
467: 1.....9..9..1...7....9..123.12.4..59795312....46.9..12231.8.5...79...8........2..
479: .....6978....2.4564..8..1233.2...78....3126.56..78.3.2.31......9.82..5...........
487: ...45....6...2....4..69..233..9.5..6..63.29..549786312.31.74..9.6523......4.6..3.
491: 12.4.8....7.1......58.7612.312.49.6.86..1..4.74.....1.2.1......5.7.......8.5...3.
499: 1...576..6..12.......6..1.3.1.......796.1...5.4897..1...1....6..6..31.94.7..6..31
503: ..3.5689..9.123....56.9...3..25....8.6.31.....45........16..9855.9..1...6..9.5.31
509: ..3...8...87..3.5.4.698...33127.869..95.....8.48.9.3..2.1..498.8.9...5..5.48.9.3.
521: 123457...8691234574579681233.25.6..997....6......89..2...6..........1....9.......
523: ...4.7....6.1.34.74.7869...3.29.5..67.63.29.5945678.......94...6..231..4..4.86...
541: 12.4598..8..1....9......1...1.745....6..127.5....6..1..315.4.8...7.315..........1
547: 123458679769123458...967123.1......6.8...2.....7.....2.3...4.6..7..3...4.94...23.
557: 12.458.7....12..58....6..2.3.2..5.9....3.2..5......3.223...4...679231584....9.23.
563: 12345........2....4...781..31..4....8...1.....4..8.3..2315946876...3.5.45.4.6723.
569: .23.57986....2.457.57...1233.2..5.79..8....4...5....1.23.7.....58..3.7.4..458.231
571: 123.......7.1....6..6.7.12..1...........1..4.6..7...1223...47...8.231.64.6.9.723.
577: 12.4.6...789......4.69.71..3.28.5...69.3.2...5487693122..694...8........9.4.7823.
587: .23.5.976..6...4.5.5....1.3312.4..58587.1..49649.8531..3....56..65.3.89....56..3.
593: ..3457986.8912..5..57.8.12...2....9.9.8.12.4....89......1....698962.1.......6....
599: .....87..7....3458.....712....746985...312647647589312...87459....23.8..8..96.2..
601: ..3.59...7...23..9..9..61.33.25..9...973....5...9.....231.9.586...231794974685..1
607: ..345.....7..23.5.456..7123312748...695312...7..569312.3........6723...........31
613: 1.34....66...2..57...6891.3.12.4.7......1........9..1...1..4...8.6.3.5.4.5.9..2.1
617: ....56.......23.5.4...87.2....54.76976931.....4.679......89.6.....231..498.76..3.
619: 1..45......9123....5....1...1..4...76.7.128..5.8.6..12..1.94.....5.31...9.4..5231
631: 1.3....9.89.1..4..4..89.1..312..9...785312649649...312.3.....6.5682..97..7.......
641: 1.3456...7.81..4.64.6..8...31.8..9..96.3.....847.......31584.97..9......5.4..9.3.
643: 123.5.678.6.123459...786123.12.4..67.7..129....56...122.....7..................31
647: ..3.5.....9...3.5...7..6.23.12.49.75..5..2..9....75312.3....56.....31......56823.
653: ...4587.9..9......45.79612......5976.9631.8458.596..1..3................5..6.9...
659: 1....76.9.......7....8...233127....66..3..7........31223....9679.....854..4.7.231
661: .2.45.6.9.9......5.5...9...3125.8.6..6931.5..5.8..6.1..31....566.5.3..9......5.31
673: 1234..7...9.123..8...9.7123.....96...6...2...5...7...2.....4....56231.74......2.1
677: 1...59..7...1....9..9.8.123.....8.7.69......8........2.3.89.7.5..5.3.89498...523.
683: ..3..9.6..68.2.459..96..1.33.2...9.69.....5..5.....3..2.1...8.5875.3.6946.4..8..1
691: .2...9....86.....9.5..76..3.1...8....75..2..8648.95.12.3...4....6.....84894567231
701: 12.45....79.12.4.....897123..2.........3..............231564897987231..4654789231
709: 123.57..69..1.3.574579.61..31....67....31.84..4.76..1....6.4......2.176..........
719: ...4.9..7...1.34..4....81......46....8..12.46.4.9873....17.4.8..9..31.74.74.95..1
727: 1234569787891..465..67....3..29.75....5...7....7.6.3.2..16.48.7.78........4.7....
733: 12345.6.7....2..5.45.....2.3128469757.53..84.84.5...1.23....5..5.............5.3.
739: 123........91.34...5.9....3.1..4.8.998.31..45.4.789....3.89.......231..4.9..6....
743: 1.34..7.9.6.1.34..4..7..1..31.84..9..9.3..84..4.9..3...31.749......31.745746892..
751: ..345.7..7......5.45.76.1..31..4..7887........4587.3...3...4..7597...8....4..72..
757: ...4.6.98.8...3....5..89....1..4.8....8.1.6......78.....1894.6.567231.8.894567231
761: 12.4....9......4..457..9..3.1..4......5.12648.4..7.31...17.4..65.92...84..4......
769: 123...7868761234...5...6123.125....7.....25.85.8..73.2.31...8...8...1..4......231
773: 1...........12.....5....1........798......645.....9312231894576765231984..4..6231
787: ..3.5...88....3.57......1..3.2..9......3.2..9948675.1.23...4..668.23..9.........1
797: ...45.798798....5....79812.......86.867...9.5....8.3...3.8..579.792...8..8..7.23.
809: ...4.87......2.4.84...7.123.1.84...696....84.84576..1..3...4.........584..4..7.3.
811: 1..4.86.9......4..4..7..1..31.5...8.8..31..45547.893....18..597..5...8.4.84..52..
821: .23..8.696...23.5.....96.2.3.2..7..69....25..54..69...23.98.6757..23.8.....67....
$\endgroup$
3
  • $\begingroup$ Wow, that is impressive! What if you store sudokus with composite number of solutions as well? It may well be that the smallest non-constructible one is actually composite... $\endgroup$ – Per Alexandersson Apr 28 '16 at 2:40
  • 1
    $\begingroup$ It may be composite, but regardless this method is only finding random examples; if it finds examples for all $n \in [1, j]$ plus some above $j+1$ it does not prove that $k=j$ - and since the space is so vast it is an infeasible approach for the problem at hand (it will never find all 6.x * 10^21); thus a proof is necessary. FWIW I ran it for a couple of hours and it found 4,109 unique solve counts: 1-836 and the rest between 838 and 169,767 (missing 837, 869, 870, 887, 899, 1051, 1056, ....) $\endgroup$ – Jonathan Allan Apr 28 '16 at 22:24
  • $\begingroup$ That's impressive! $\endgroup$ – Per Alexandersson Apr 28 '16 at 23:14
1
$\begingroup$

Consider the process of randomly generating single solution puzzles and randomly dropping one or more clues as shown in the pseudo-code below:

GenerateValidNotNecessarilyMinimalSudoku() {
  clues := {}
  consequences := {}
  for literal in RandomPermutation(Range(729)) {
    if literal not in consequences {
      switch (CountSolutions(clues U {literal}, limit=2)) {
       case 0:
         continue
       case 1:
         return clues U {literal}
       case 2:
         clues := clues U {literal}
         consequences := UnitPropagate(clues)
      }
    }
  }
}

samples = []
for _ in Range(NumSamples) {
  clues := GenerateValidNotNecessarilyMinimalSudoku()
  relaxed := clues - PickRandomElements(clues, NumToDrop)
  samples += [CountSolutions(relaxed, limit=10000)]
}

Interestingly, though maybe not surprisingly, this process gives rise to an approximately lognormal distribution of solution counts. Here's a chart showing the empirical distribution (black) of solution counts from a sample of 15 million random puzzles with 1 dropped clue vs. the fitted lognormal model (green).


And here's the same chart for another 15 million random puzzles, this time dropping 4 clues:


This behavior suggests an absence of the kinds of pattern in solution count probability that might conspire to produce a "low" k. Maybe it also hints at a way to at least guess at the order of magnitude of k. (e.g., choose a useful way to partition the space of possible puzzles, estimate the number of distinct non-equivalent puzzles in each partition, find a way to sample from these puzzles uniformly, fit lognormal models for each partition, given lognormal model and size of sample space, ask in what range does it become likely that some count is zero).

$\endgroup$
1
  • $\begingroup$ This is a nice observation, maybe it can be proved rigorously. Would be a nice paper on arxiv. $\endgroup$ – Per Alexandersson Jan 27 '20 at 7:38

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.