Solving sudokus via metaheuristics and AC3

Ricardo Soto; Broderick Crawford; Cristian Galleguillos; Sanjay Misra; Eduardo Olguin

doi:10.1109/ICASTECH.2014.7068127

Solving sudokus via metaheuristics and AC3

Ricardo Soto, Broderick Crawford, Cristian Galleguillos, Sanjay Misra, Eduardo Olguin

SCHOOL OF COMPUTER ENGINEERING

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

The Sudoku puzzle consists in filling a square matrix with 9 rows and 9 columns, divided into 9 3×3 regions, so that each column, row, and region contains different digits from 1 to 9. Such a puzzle belongs to the NP-complete class of problems, existing different exact and approximate methods able to solve it. This paper reports recent results for solving Sudokus achieved by combining metaheuristics and a filtering technique coming from the constraint programming domain named AC3.

Original language	English
Title of host publication	ICAST 2014 - 2014 IEEE 6th International Conference on Adaptive Science and Technology, Proceedings
Editors	Charles K. Ayo, Sanjay Misra, Nicholas Omoregbe, Adewole Adewumi, Babafemi Odusote
Publisher	IEEE Computer Society
ISBN (Electronic)	9781479949984
DOIs	https://doi.org/10.1109/ICASTECH.2014.7068127
State	Published - 25 Mar 2015
Event	2014 6th IEEE International Conference on Adaptive Science and Technology, ICAST 2014 - Ota, Nigeria Duration: 29 Oct 2014 → 31 Oct 2014

Publication series

Name	IEEE International Conference on Adaptive Science and Technology, ICAST
Volume	2015-January
ISSN (Print)	2326-9413
ISSN (Electronic)	2326-9448

Conference

Conference	2014 6th IEEE International Conference on Adaptive Science and Technology, ICAST 2014
Country/Territory	Nigeria
City	Ota
Period	29/10/14 → 31/10/14

Keywords

Arc-consistency
Constraint Satisfaction
Sudoku

Access to Document

10.1109/ICASTECH.2014.7068127

Cite this

Soto, R., Crawford, B., Galleguillos, C., Misra, S., & Olguin, E. (2015). Solving sudokus via metaheuristics and AC3. In C. K. Ayo, S. Misra, N. Omoregbe, A. Adewumi, & B. Odusote (Eds.), ICAST 2014 - 2014 IEEE 6th International Conference on Adaptive Science and Technology, Proceedings Article 7068127 (IEEE International Conference on Adaptive Science and Technology, ICAST; Vol. 2015-January). IEEE Computer Society. https://doi.org/10.1109/ICASTECH.2014.7068127

Soto, Ricardo ; Crawford, Broderick ; Galleguillos, Cristian et al. / Solving sudokus via metaheuristics and AC3. ICAST 2014 - 2014 IEEE 6th International Conference on Adaptive Science and Technology, Proceedings. editor / Charles K. Ayo ; Sanjay Misra ; Nicholas Omoregbe ; Adewole Adewumi ; Babafemi Odusote. IEEE Computer Society, 2015. (IEEE International Conference on Adaptive Science and Technology, ICAST).

@inproceedings{5f7fe4e5170549b1a86b0a57c65d09d4,

title = "Solving sudokus via metaheuristics and AC3",

abstract = "The Sudoku puzzle consists in filling a square matrix with 9 rows and 9 columns, divided into 9 3×3 regions, so that each column, row, and region contains different digits from 1 to 9. Such a puzzle belongs to the NP-complete class of problems, existing different exact and approximate methods able to solve it. This paper reports recent results for solving Sudokus achieved by combining metaheuristics and a filtering technique coming from the constraint programming domain named AC3.",

keywords = "Arc-consistency, Constraint Satisfaction, Sudoku",

author = "Ricardo Soto and Broderick Crawford and Cristian Galleguillos and Sanjay Misra and Eduardo Olguin",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 6th IEEE International Conference on Adaptive Science and Technology, ICAST 2014 ; Conference date: 29-10-2014 Through 31-10-2014",

year = "2015",

month = mar,

day = "25",

doi = "10.1109/ICASTECH.2014.7068127",

language = "English",

series = "IEEE International Conference on Adaptive Science and Technology, ICAST",

publisher = "IEEE Computer Society",

editor = "Ayo, {Charles K.} and Sanjay Misra and Nicholas Omoregbe and Adewole Adewumi and Babafemi Odusote",

booktitle = "ICAST 2014 - 2014 IEEE 6th International Conference on Adaptive Science and Technology, Proceedings",

}

Soto, R , Crawford, B, Galleguillos, C, Misra, S & Olguin, E 2015, Solving sudokus via metaheuristics and AC3. in CK Ayo, S Misra, N Omoregbe, A Adewumi & B Odusote (eds), ICAST 2014 - 2014 IEEE 6th International Conference on Adaptive Science and Technology, Proceedings., 7068127, IEEE International Conference on Adaptive Science and Technology, ICAST, vol. 2015-January, IEEE Computer Society, 2014 6th IEEE International Conference on Adaptive Science and Technology, ICAST 2014, Ota, Nigeria, 29/10/14. https://doi.org/10.1109/ICASTECH.2014.7068127

Solving sudokus via metaheuristics and AC3. / Soto, Ricardo ; Crawford, Broderick; Galleguillos, Cristian et al.
ICAST 2014 - 2014 IEEE 6th International Conference on Adaptive Science and Technology, Proceedings. ed. / Charles K. Ayo; Sanjay Misra; Nicholas Omoregbe; Adewole Adewumi; Babafemi Odusote. IEEE Computer Society, 2015. 7068127 (IEEE International Conference on Adaptive Science and Technology, ICAST; Vol. 2015-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Solving sudokus via metaheuristics and AC3

AU - Soto, Ricardo

AU - Crawford, Broderick

AU - Galleguillos, Cristian

AU - Misra, Sanjay

AU - Olguin, Eduardo

PY - 2015/3/25

Y1 - 2015/3/25

N2 - The Sudoku puzzle consists in filling a square matrix with 9 rows and 9 columns, divided into 9 3×3 regions, so that each column, row, and region contains different digits from 1 to 9. Such a puzzle belongs to the NP-complete class of problems, existing different exact and approximate methods able to solve it. This paper reports recent results for solving Sudokus achieved by combining metaheuristics and a filtering technique coming from the constraint programming domain named AC3.

AB - The Sudoku puzzle consists in filling a square matrix with 9 rows and 9 columns, divided into 9 3×3 regions, so that each column, row, and region contains different digits from 1 to 9. Such a puzzle belongs to the NP-complete class of problems, existing different exact and approximate methods able to solve it. This paper reports recent results for solving Sudokus achieved by combining metaheuristics and a filtering technique coming from the constraint programming domain named AC3.

KW - Arc-consistency

KW - Constraint Satisfaction

KW - Sudoku

UR - http://www.scopus.com/inward/record.url?scp=84940116875&partnerID=8YFLogxK

U2 - 10.1109/ICASTECH.2014.7068127

DO - 10.1109/ICASTECH.2014.7068127

M3 - Conference contribution

AN - SCOPUS:84940116875

T3 - IEEE International Conference on Adaptive Science and Technology, ICAST

BT - ICAST 2014 - 2014 IEEE 6th International Conference on Adaptive Science and Technology, Proceedings

A2 - Ayo, Charles K.

A2 - Misra, Sanjay

A2 - Omoregbe, Nicholas

A2 - Adewumi, Adewole

A2 - Odusote, Babafemi

PB - IEEE Computer Society

T2 - 2014 6th IEEE International Conference on Adaptive Science and Technology, ICAST 2014

Y2 - 29 October 2014 through 31 October 2014

ER -

Soto R , Crawford B, Galleguillos C, Misra S, Olguin E. Solving sudokus via metaheuristics and AC3. In Ayo CK, Misra S, Omoregbe N, Adewumi A, Odusote B, editors, ICAST 2014 - 2014 IEEE 6th International Conference on Adaptive Science and Technology, Proceedings. IEEE Computer Society. 2015. 7068127. (IEEE International Conference on Adaptive Science and Technology, ICAST). doi: 10.1109/ICASTECH.2014.7068127

Solving sudokus via metaheuristics and AC3

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this