Por @Alvy — 22 de Noviembre de 2017

Sudoku constraint propagation

Aunque los populares sudokus se pueden resolver de muchas formas, que lo haga un ordenador no siempre es tan fácil como parece. En How To Win Sudoku Grant Bartel explica cómo funciona un método «típico de la inteligencia artificial» para hacerlo – lo cual aunque suene grandioso en realidad está al alcance de muchos programadores. Se trata de un algoritmo de propagación con restricciones, una técnica que se suele utilizar en problemas combinatorios.

Se trata de un método que permite dirigir el programa hacia una solución probable («propagar») mientras sigue las reglas de un cierto espacio y los valores posibles a utilizar por ciertas variables en dicho espacio («restricciones»).

El artículo explica el procedimiento paso a paso y cita el trabajo de Peter Norvig Solving Every Sudoku Puzzle que fue el primero que describió cómo utilizar esta técnica para resolver sudokus mediante propagación con restricciones con búsqueda en profundidad en un árbol binario de búsqueda.

Pero esta no es la única forma de resolver un sudoku. Hay muchos otros métodos para resolver sudokus, en especial los algoritmos de vuelta atrás (backtracking), los de búsqueda estocástica (rellenando las casillas al azar, contando los errores y reduciendo el número de errores hasta llegar a cero) o mediante un algoritmo de cobertura exacto.

Compartir en Flipboard Publicar / Tuitear