¿Los sudokus reales tienen una solución racional única?

Question

Esta es una pregunta en la intersección de las matemáticas y la sociología. Hay una forma estándar de codificar un rompecabezas de Sudoku como un problema de programación entera. El problema tiene una variable de valor 0-1 $a_{i,j,k}$ para cada triple $1 \le i,j,k \le 9$ , expresando que la entrada en la posición $(i,j)$ tiene valor $k$ . Las reglas del Sudoku dicen que cuatro tipos de conjuntos de 9 de las variables suman 1, para expresar que cada celda se llena exactamente con un número, y que cada número aparece exactamente una vez en cada fila, columna y $3 \times 3$ caja. Y en un rompecabezas de Sudoku, algunas de estas variables (tradicionalmente 27 de ellas) están preestablecidas en 1.

Se sabe que el Sudoku generalizado, al igual que la programación entera general, es NP-difícil. Sin embargo, ¿es ese el modelo correcto para el Sudoku en la práctica? Me he dado cuenta de que muchos Sudokus humanos pueden resolverse con ciertos trucos estándar, muchos de los cuales implican una única racional solución al problema de programación entera. Se pueden encontrar soluciones racionales con la programación lineal, y si la solución racional es única, ese tipo de problema de programación entera no es NP-duro, está en P. Tradicionalmente los rompecabezas Sudoku tienen una solución única. Todo lo que se quiere decir es una solución entera única, pero tal vez la comunidad de Sudoku no ha explorado las razones de la unicidad que no impliquen también una solución racional única.

¿Existen sudokus humanos publicados con una única solución, pero con más de una solución racional? ¿Hay alguna forma práctica de averiguarlo? Supongo que un experimento sería hacer un Sudoku de este tipo (aunque no sé lo difícil que es), y luego ver qué pasa cuando se lo das a la gente.

Answer 1

No pensaba responder aquí, pero ya que alguien mencionó mi artículo en el largo hilo de comentarios anterior, tal vez debería hacerlo de todos modos.

Cuando resuelvo problemas a mano, uno de los conjuntos de patrones que utilizo con frecuencia tiene que ver con la unicidad: algo no puede suceder porque llevaría a un rompecabezas con más de una solución, pero un rompecabezas de Sudoku bien planteado sólo tiene una solución, así que es seguro asumir que lo que sea no sucede. Por ejemplo, no es posible tener cuatro celdas inicialmente vacías en un rectángulo de las mismas dos filas, las mismas dos columnas y los mismos dos cuadrados de 3x3, y también que estas cuatro celdas contengan todas uno de los mismos dos valores, porque entonces los dos valores que contienen podrían colocarse de dos maneras diferentes y el resto del puzzle no notaría el cambio. Así que si sólo hay una manera de evitar que se forme un rectángulo como éste, entonces la solución tiene que utilizar esa única manera.

Tengo la sensación (aunque podría estar equivocado) de que este tipo de inferencia no implica una solución racional única. Pero, por supuesto, un rompecabezas podría tener una solución racional única de todos modos: mi solucionador informático también conoce estas reglas, pero las utiliza con menos frecuencia que yo a mano.

ETA: Parece ser cierto que estas reglas no implican soluciones racionales únicas. Con ellas, mi solucionador resuelve fácilmente el siguiente acertijo, que tiene una solución entera única pero no tiene una solución fraccionaria única. Sin ellas, mi solucionador todavía puede resolver el mismo puzzle, pero sólo utilizando reglas que son (en mi experiencia) mucho más difíciles de aplicar a mano.

 ----------------------------------- 
| 3   7   8 | 6   4   5 | 1   2   9 |
|           |           |           |
| 6   9   . | .   7   . | 4   8   5 |
|           |           |           |
| 4   .   5 | 9   .   8 | 3   7   6 |
|-----------------------------------|
| 7   .   9 | 5   3   . | 8   6   4 |
|           |           |           |
| 8   4   . | 7   .   . | 5   9   3 |
|           |           |           |
| 5   3   6 | 8   9   4 | 2   1   7 |
|-----------------------------------|
| 1   6   3 | 2   5   7 | 9   4   8 |
|           |           |           |
| 9   8   4 | .   .   . | 7   5   2 |
|           |           |           |
| 2   5   7 | 4   8   9 | 6   3   1 |
 ----------------------------------- 

O si quieres algo parecido a los rompecabezas que se publican, aquí tienes otro que utiliza el mismo mecanismo:

 ----------------------------------- 
| 1   .   . | 8   .   7 | 5   .   . |
|           |           |           |
| .   5   . | 6   .   . | 9   7   . |
|           |           |           |
| .   6   . | .   4   . | .   .   . |
|-----------------------------------|
| .   .   2 | .   .   . | .   6   . |
|           |           |           |
| 6   .   . | 4   .   3 | .   .   . |
|           |           |           |
| .   4   . | .   .   . | 1   .   . |
|-----------------------------------|
| .   .   . | .   1   . | .   5   . |
|           |           |           |
| .   1   3 | .   .   6 | .   9   . |
|           |           |           |
| .   .   7 | 5   .   4 | .   .   1 |
 -----------------------------------

Answer 2

Para una prueba débil de la existencia, revisaría la base de datos de Sudokus de Gordon Royle con un número mínimo de dados, y (programaría un ordenador para) comprobar si hay soluciones racionales múltiples en cualquiera de los rompecabezas. Si todos ellos tuvieran soluciones racionales únicas, yo tomaría eso como una fuerte evidencia de que todos los Sudokus adecuados tienen soluciones racionales únicas. Si Si uno de ellos tiene múltiples soluciones racionales, añada algunos datos hasta que tenga un rompecabezas máximo deseado, y publíquelo (o publíquelo). deseado, y publicarlo (o enviarlo a Nick Baxter et. al. para la respuesta sociológica).

Gerhard "Ask Me About System Design" Paseman, 2010.06.08

Answer 3

No es una respuesta, sólo quería señalar algunas referencias. David Eppstein tiene un artículo en arXiv sobre un ingenioso truco de "tipo humano", imagino que publicará algo para esta pregunta. También produjo rompecabezas al azar y contó el efecto de su método en la capacidad de resolver, y todavía había bastantes irresolubles al incluir su método. El método de Eppstein se incluyó en el libro de rompecabezas "Mensa Guide to solving Sudoku" de Peter Gordon y Frank Longo, uno de los pocos libros que encontré con rompecabezas difíciles. Sin embargo, el método por el que siento curiosidad, y guardé la edición, está en el A.M.S. Notices de abril de 2009, J. F. Crook, "A pencil-and-paper algorithm for solving sudoku puzzles", páginas 460-468, pdf en http://www.ams.org/notices/200904/index.html

Answer 4

Una buena explicación de cómo los humanos resuelven el sudoku está aquí -

http://onigame.livejournal.com/20626.html