Más pequeño número entero $k$ para que ninguna rejilla de Sudoku tiene exactamente $k$ soluciones

Question

Inspirado por esta pregunta, considere consejos sobre un tablero de Sudoku. Un rompecabezas regular tiene una solución única. Está claro que hay acertijos con soluciones 2 o 3, y por lo tanto, supongo, decir acertijos con soluciones 4 y 6.

Ahora, ¿cuál es el más pequeño número entero $k$ tales que no hay ningún conjunto de pistas de Sudoku en exactamente $k$ soluciones?

Answer 1

Como suele ocurrir con estas conjeturas, si la solución no es k=7 o k=11, puede ser realmente difícil de encontrar. Por supuesto, existe una solución, porque no hay un máximo de (gran) número de soluciones que un espacio en blanco sudoku permite. Una propiedad que puede ayudar a construir soluciones es que para valores pequeños, si tenemos un sudoku, que permite que una de las soluciones y otra que permite la b de soluciones, probablemente podemos encontrar un sudoku, que permite a·b soluciones. Por ejemplo:

Esto permite que k=4rellenos: $$ 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 $$

Y esto permite que k=3rellenos: $$ 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 $$

A partir de esto, podemos ver fácilmente que este: $$ 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 $$

permite k = 4·3 = 12 rellenos.

Aunque es difícil generalizar, es probable que el número que usted está buscando es primo, porque si iba a ser un número compuesto, sus factores (menor que el número) tendría que ser un número de rellenos para algunos sudoku, y, a continuación, esto no rigurosa regla de la multiplicación sería un fracaso.

Answer 2

Esto es sólo una respuesta parcial, que puede ser, tal vez, se convirtió en una wiki de la comunidad, donde los ejemplos de parcial rellenos que permiten a $n$ válidos y completos rellenos.

Este admite $k=2$ soluciones de: \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}

Esto permite a $k=3$ rellenos: \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}

Si mis cálculos son correctos, esto permite a $k=5$ rellenos: \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}

En la actualidad, $k=7$ es aún desconocido.

Este es el código de mathematica puedo usar para resolver Sudokus. Es solo lo básico de la repetición, y es muy probable que pueda ser optimizado mucho.

(* 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
   ];