Resolver un sudoku de colores

$5$pistas es el mínimo para forzar una solución única en un$5 \times 5$junta. Mostró que, de hecho, hay una manera de forzar una solución única con$5$pistas, y debajo hay una prueba de que no puede forzar una solución única con menos de$5$pistas

Si usted tiene$4$pistas, y dos de las pistas están en la misma fila (o columna), entonces habrá dos filas (o dos columnas) que no tienen pistas, y esas filas (columnas) pueden intercambiarse por cualquier solución para obtener otra solución. Entonces, si pudieras hacerlo con solo$4$pistas, definitivamente quieres que todas las pistas estén en diferentes filas y columnas.

Del mismo modo, si tiene dos pistas con el mismo número (o color), entonces habrá dos números (o colores) que no se usan en ninguna de las pistas y, por lo tanto, puede intercambiar esos números (colores) para obtener cualquier solución. otra solución. Entonces, si pudieras hacerlo con solo$4$pistas, definitivamente quieres que todas las pistas sean de todos los números diferentes y de todos los colores diferentes.

Sin pérdida de generalización, podemos decir que las pistas son$1A$,$B2$,$C3$, y$D4$, y también sin pérdida de generalización, podemos suponer que las pistas se colocan de la siguiente manera (recuerde que con las pistas en todas las filas y columnas diferentes, podemos seguir intercambiando dos filas y columnas cualesquiera para terminar en esta configuración):

$$\begin{array}{|c|c|c|c|c|} \hline A1&.&.&.&.\\ \hline .&B2&.&.&.\\ \hline .&.&C3&.&.\\ \hline .&.&.&D4&.\\ \hline .&.&.&.&.\\ \hline \end{array}$$

Entonces, si podemos encontrar dos soluciones a este rompecabezas, entonces sabemos que$4$las pistas nunca pueden forzar una solución única. Y de hecho hay dos soluciones:

$$\begin{array}{|c|c|c|c|c|} \hline A1&E3&D2&B5&C4\\ \hline E4&B2&A5&C1&D3\\ \hline D5&A4&C3&E2&B1\\ \hline B3&C5&E1&D4&A2\\ \hline C2&D1&B4&A3&E5\\ \hline \end{array}$$

$$\begin{array}{|c|c|c|c|c|} \hline A1&E4&D5&B3&C2\\ \hline E3&B2&A4&C5&D1\\ \hline D2&A5&C3&E1&B4\\ \hline B5&C1&E2&D4&A3\\ \hline C4&D3&B1&A2&E5\\ \hline \end{array}$$

Tenga en cuenta que la segunda solución es la primera solución reflejada a lo largo de la diagonal con las pistas (que a su vez se puede lograr mediante una sola rotación junto con una duplicación vertical u horizontal, es decir, intercambiando filas o columnas). De hecho, no tuve que proporcionar dos soluciones en absoluto para señalar que el$4$las pistas como se indica no pueden forzar una solución única, ya que dado que todas las pistas están en la diagonal, entonces si tiene alguna solución, entonces también tiene una solución especular.

Esta última observación también responde parcialmente a su tercera pregunta: el argumento que di anteriormente se generaliza claramente para mostrar que cada$n \times n$rompecabezas de este tipo requerirá al menos$n$pistas para forzar una solución única: con$n-1$pistas, tienen que estar, sin pérdida de generalización, a lo largo de la diagonal, y por lo tanto si hay alguna solución, siempre habrá otra.

Está bien, pero ¿puedes forzar siempre una solución única con exactamente$n$pistas? Esa es todavía una pregunta abierta ... sabemos que funciona para$n=5$, pero francamente dudo que puedas hacerlo por$n>5$.

En lo que respecta a su segunda pregunta, encontré cuatro tableros válidos que no se pueden obtener entre sí intercambiando colores, números, filas, columnas o haciendo cualquier rotación o duplicación:

$$\begin{array}{|c|c|c|c|c|} \hline A1&B3&C4&D5&E2\\ \hline D4&A2&B5&E3&C1\\ \hline E5&D1&A3&C2&B4\\ \hline B2&C5&E1&A4&D3\\ \hline C3&E4&D2&B1&A5\\ \hline \end{array}$$

$$\begin{array}{|c|c|c|c|c|} \hline A1&B3&C4&D5&E2\\ \hline D3&A2&E5&C1&B4\\ \hline E4&C5&A3&B2&D1\\ \hline B5&E1&D2&A4&C3\\ \hline C2&D4&B1&E3&A5\\ \hline \end{array}$$

$$\begin{array}{|c|c|c|c|c|} \hline A1&B3&C2&D5&E4\\ \hline C4&A2&E5&B1&D3\\ \hline B5&D4&A3&E2&C1\\ \hline E3&C5&D1&A4&B2\\ \hline D2&E1&B4&C3&A5\\ \hline \end{array}$$

$$\begin{array}{|c|c|c|c|c|} \hline A1&B3&C2&D5&E4\\ \hline C5&A2&D4&E3&B1\\ \hline B4&E5&A3&C1&D2\\ \hline E2&D1&B5&A4&C3\\ \hline D3&C4&E1&B2&A5\\ \hline \end{array}$$

Estoy bastante seguro de que todos los demás tableros válidos se pueden transformar en uno de estos$4$mediante el intercambio de colores, números, filas, columnas, o haciendo cualquier rotación o reflejo. Por ejemplo, se puede ver que los dos primeros tableros son del tercer tipo poniendo todos los$A$'s a lo largo de la diagonal en orden, seguido de un reflejo diagonal. Entonces, estoy bastante seguro de que la respuesta a su segunda pregunta es$4$.