A marriage theorem based-algorithm for solving sudoku

Ricardo Soto, Broderick Crawford, Cristian Galleguillos, Francisca C. Venegasy, Fernando Paredes

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

Resumen

Millions of people around the world are solving a complex constraint satisfaction problem although they do not know. This problem is a famous game known as Sudoku puzzle and it consists in filling a n2 × n2 grid, composed by n columns, n rows and n sub-grids, each one containing different digits from 1 to n2. In this paper, we propose an exact algorithm based on Hall's marriage theorem in order to solve it. After applied our proposed method, we have noticed that some instances with particular features are possible to solve. The algorithm is quite simple to code it and good results are reached solving some instances. The unresolved ones as result of the application of the algorithm is generated an equivalent problem to the original one, but more easiest to solve. We illustrate the experimental evaluation comparing with another complete methods.

Idioma originalInglés
Título de la publicación alojadaProceedings - 14th Mexican International Conference on Artificial Intelligence
Subtítulo de la publicación alojadaAdvances in Artificial Intelligence, MICAI 2015
EditoresGustavo Arroyo Figueroa, Grigori Sidorov, Sofia N. Galicia Haro, Oscar Herrera Alcantara, Obdulia Pichardo Lagunas
EditorialInstitute of Electrical and Electronics Engineers Inc.
Páginas117-121
Número de páginas5
ISBN (versión digital)9781509003235
DOI
EstadoPublicada - 8 mar 2016
Publicado de forma externa
Evento14th Mexican International Conference on Artificial Intelligence, MICAI 2015 - Cuernavaca, Morelos, México
Duración: 25 oct 201531 oct 2015

Serie de la publicación

NombreProceedings - 14th Mexican International Conference on Artificial Intelligence: Advances in Artificial Intelligence, MICAI 2015

Conferencia

Conferencia14th Mexican International Conference on Artificial Intelligence, MICAI 2015
País/TerritorioMéxico
CiudadCuernavaca, Morelos
Período25/10/1531/10/15

Huella

Profundice en los temas de investigación de 'A marriage theorem based-algorithm for solving sudoku'. En conjunto forman una huella única.

Citar esto