¿Puede una computadora resolver sudoku sin simplemente sustituir números y verificar?

Soduko no tiene nada que ver con los números. En lugar de usar el número 1..9, las reglas podrían haber usado “A”, “B”, “C” … “H” o “rojo”, azul, “verde” … “turquesa”.

Tiene que ver con la combinatoria. El hecho de que estén representados como números es irrelevante.

Ahora, al resolver Soduko, un programador puede decidir usar un tipo de número, tratando los valores como números del 1 al 9. O tal vez no. Lo que sea más fácil para ellos. El único requisito es que sean 9 cosas diferentes, los números 1..9 son solo una de las infinitas formas de etiquetar los valores en cada cuadrado,

Pasando a la segunda parte de su pregunta, “sustituir números y verificar” es la única manera si puede determinar si la respuesta es correcta (o incorrecta, para el caso). Así que es difícil ver cómo se puede evitar.

Sí, como otros han sugerido, puedes intentar imitar las habilidades de razonamiento humano en un solucionador de Sudoku.

Uno de los profesores de mi laboratorio escribió un programa para generar buenos rompecabezas de Sudoku para sí mismo. Como él escribe:

Un acertijo de Sudoku adecuado debe tener una solución única, y debería ser posible llegar a esa solución mediante una secuencia de deducciones lógicas sin prueba y error. En la medida de lo posible, nos esforzamos por mantener la misma ética en nuestro solucionador automatizado, imitando el razonamiento basado en reglas humanas, en lugar de
recurriendo a la búsqueda de retroceso de fuerza bruta.

Puede consultar su código (escrito en Python) aquí: https://www.ics.uci.edu/~eppstei …

Sí, aunque ningún algoritmo conocido es generalmente más rápido que adivinar y verificar por más que factores constantes. Vea ¿Cuáles son los algoritmos de programación más eficientes para resolver acertijos sudoku?

El enfoque más conocido está basado en restricciones, usualmente usando la implementación de “enlaces danzantes” de Knuth de “Algoritmo X” – descrita aquí: Enlaces de Baile – Wikipedia

En resumen, es un problema resuelto en el dominio CS.

Sin embargo, no puedo responder completamente a su pregunta, me temo:

Sudoku es un juego donde es fácil programar las estrategias necesarias para llegar rápidamente a la lógica de nivel humano superior, y cuando lo combinas con una memoria y velocidad mucho mejores y más escalables, se vuelve bastante sencillo construir un juego de sudoku que es sobrehumano

Esto me hace pensar que es poco probable que las personas estén dedicando una investigación seria para ver si pueden hacer un robot sudoku mucho mejor de la forma en que lo hacen (¿lo hicieron?) Con el ajedrez, ahora lo hacen con eficacia y pronto prosperarán contra otros juegos particularmente complicados.

Tampoco sé si podría construir uno mejor que la forma basada en reglas. En un espacio más complejo, una IA puede encontrar patrones que le otorguen una ventaja sobre los humanos (y viceversa, por supuesto, dependiendo del espacio), pero la estructura del sudoku es tan definitiva que es posible que ya hayamos descubierto la forma óptima de abordar el juego. con lo que hay entre nuestros oídos.

Sí. Hay una variedad de técnicas que pueden usarse para calcular la respuesta, lo mismo que hacen los jugadores humanos.

Dicho esto, dada la velocidad a la que una computadora puede implementar un sistema de conjetura y verificación, es una forma perfectamente razonable de diseñar un solucionador de Sudoku. La cantidad de permutaciones que necesita para el rompecabezas es bastante manejable en comparación con algunas.