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  Compartir en Facebook  Tuitear

Microsiervos Selección


The Elements of Statistical Learning

EUR 50,92

Comprar


Wonderland: How Play Made the Modern World

EUR 7,16 (Reseña en Microsiervos)

Comprar


Amazon Associates

Los productos aquí enlazados están a la venta en Amazon. Incluyen un código de Afiliado Amazon Associates que nos cede un pequeño porcentaje de las ventas. Los productos están seleccionados por los autores del blog, pero ni Amazon ni los editores de los libros o fabricantes de los productos participan en dicha selección.

Más libros y productos en:

Microsiervos Selección