TY - GEN
T1 - A marriage theorem based-algorithm for solving sudoku
AU - Soto, Ricardo
AU - Crawford, Broderick
AU - Galleguillos, Cristian
AU - Venegasy, Francisca C.
AU - Paredes, Fernando
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2016/3/8
Y1 - 2016/3/8
N2 - 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.
AB - 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.
KW - Bipartite graph
KW - Marriage Theorem
KW - Sudoku
KW - System of Distinct Representatives
UR - http://www.scopus.com/inward/record.url?scp=84987815263&partnerID=8YFLogxK
U2 - 10.1109/MICAI.2015.24
DO - 10.1109/MICAI.2015.24
M3 - Conference contribution
AN - SCOPUS:84987815263
T3 - Proceedings - 14th Mexican International Conference on Artificial Intelligence: Advances in Artificial Intelligence, MICAI 2015
SP - 117
EP - 121
BT - Proceedings - 14th Mexican International Conference on Artificial Intelligence
A2 - Figueroa, Gustavo Arroyo
A2 - Sidorov, Grigori
A2 - Galicia Haro, Sofia N.
A2 - Alcantara, Oscar Herrera
A2 - Lagunas, Obdulia Pichardo
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 14th Mexican International Conference on Artificial Intelligence, MICAI 2015
Y2 - 25 October 2015 through 31 October 2015
ER -