A marriage theorem based-algorithm for solving sudoku

RICARDO JAVIER SOTO DE GIORGIS, BRODERICK CRAWFORD LABRIN, Cristian Galleguillos, Francisca C. Venegasy, Fernando Paredes

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationProceedings - 14th Mexican International Conference on Artificial Intelligence
Subtitle of host publicationAdvances in Artificial Intelligence, MICAI 2015
EditorsGustavo Arroyo Figueroa, Grigori Sidorov, Sofia N. Galicia Haro, Oscar Herrera Alcantara, Obdulia Pichardo Lagunas
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages117-121
Number of pages5
ISBN (Electronic)9781509003235
DOIs
StatePublished - 8 Mar 2016
Event14th Mexican International Conference on Artificial Intelligence, MICAI 2015 - Cuernavaca, Morelos, Mexico
Duration: 25 Oct 201531 Oct 2015

Publication series

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

Conference

Conference14th Mexican International Conference on Artificial Intelligence, MICAI 2015
CountryMexico
CityCuernavaca, Morelos
Period25/10/1531/10/15

Keywords

  • Bipartite graph
  • Marriage Theorem
  • Sudoku
  • System of Distinct Representatives

Fingerprint Dive into the research topics of 'A marriage theorem based-algorithm for solving sudoku'. Together they form a unique fingerprint.

Cite this