¿Número mínimo de pistas para especificar completamente cualquier sudoku?

Sabemos por este documento que no existe un rompecabezas que pueda resolverse comenzando con 16 o menos pistas, pero implica que existe un rompecabezas que puede resolverse a partir de 17 pistas. ¿Se pueden especificar todos los rompecabezas de sudoku válidos en 17 pistas? Si no, ¿cuál es el número mínimo de pistas que pueden especificar completamente cada rompecabezas válido? Más formalmente, ¿existe un rompecabezas de sudoku válido (o, supongo que sería un conjunto de rompecabezas) que no se puede resolver de manera única a partir de solo 17 pistas? Si es así, ¿cuál es el número mínimo de pistas, , de modo que cada rompecabezas de sudoku válido pueda especificarse de manera única en o menos pistas?$C$$C$

Dado que la permutación de dos filas dentro de un solo bloque de un sudoku completo válido produce otro sudoku completo válido, puede tomar cualquier tablero completo (81 pistas) y eliminar las dos primeras filas (81-18 = 63 pistas), lo que le dará Un sudoku incompleto con dos soluciones. Tenga en cuenta que incluso si elimina todos menos uno de los 18 números allí, la solución se determina inmediatamente de manera única (ya que no puede repetirse ningún número en la misma columna).

Otra operación que produce otro sudoku completado es aplicar una permutación de . Si toma una permutación que es una transposición (permuta dos elementos, manteniendo el otro fijo), nuevamente, como antes, puede eliminar todas las apariencias de esos dos elementos y tiene un sudoku incompleto con dos posibles soluciones y 63 pistas. Nuevamente, si no elimina los 18 números, la solución será única.$\{1,\ldots,9\}$

De las seis operaciones elementales que producen un sudoku completo (ver aquí ), estas dos son las que pueden involucrar la menor cantidad de elementos, por lo que diría que es un límite superior para lo que está buscando. Sé que esto no responde exactamente a su pregunta, pero la idea general de eliminar conjuntos de posiciones que producen dos soluciones diferentes podría ser un buen punto de partida.$C=63$

La menor cantidad de pistas requeridas para un Sudoku adecuado es 17, pero no todas las cuadrículas completas se pueden reducir a un Sudoku de 17 pistas adecuado. Se han encontrado alrededor de 49,000 Sudokus únicos (no equivalentes) con 17 pistas. (Un Sudoku adecuado solo tiene una solución).

Se cree que la mayoría de las pistas en un Sudoku mínimo son 40 (se sabe que existen dos), pero no se ha demostrado si este es el máximo. (mínimo significa que si se elimina alguna pista, el Sudoku tendría más de una solución y, por lo tanto, no sería un Sudoku adecuado)

(Esta información es de Wikipedia, de la cual estas declaraciones están bien referenciadas).

Este Sudoku tiene 77 pistas y, sin embargo, tiene múltiples soluciones (2). Puede usar 7-4 en la fila superior y 4-7 en la otra o usando 4-7 en la parte superior y 7-4 en la parte inferior. Este rompecabezas de Sudoku en particular necesita 78 pistas para tener una solución única.