Algoritmos para resolver sudokus

Your ads will be inserted here by

Easy AdSense.

Please go to the plugin admin page to paste your ad code.

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.

# Enlace Permanente

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

*