Using Constraint Programming to solve Sudoku puzzles

Broderick Crawford; Mary Aranda; Carlos Castro; Eric Monfroy

doi:10.1109/ICCIT.2008.154

Using Constraint Programming to solve Sudoku puzzles

Broderick Crawford, Mary Aranda, Carlos Castro, Eric Monfroy

SCHOOL OF COMPUTER ENGINEERING

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

13 Scopus citations

Abstract

In Constraint Programming, Enumeration Strategies are crucial for resolution performances. In this work, we model the known NP-complete problems Latin Square, Magic Square and Sudoku as a Constraint Satisfaction Problems. We solve them with Constraint Programming comparing the performance of different Variable and Value Selection Heuristics in its Enumeration phase.

Original language	English
Title of host publication	Proceedings - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008
Pages	926-931
Number of pages	6
DOIs	https://doi.org/10.1109/ICCIT.2008.154
State	Published - 2008
Event	3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008 - Busan, Korea, Republic of Duration: 11 Nov 2008 → 13 Nov 2008

Publication series

Name	Proceedings - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008
Volume	2

Conference

Conference	3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008
Country/Territory	Korea, Republic of
City	Busan
Period	11/11/08 → 13/11/08

Access to Document

10.1109/ICCIT.2008.154

Cite this

Crawford, B., Aranda, M., Castro, C., & Monfroy, E. (2008). Using Constraint Programming to solve Sudoku puzzles. In Proceedings - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008 (pp. 926-931). Article 4682365 (Proceedings - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008; Vol. 2). https://doi.org/10.1109/ICCIT.2008.154

@inproceedings{a0452eb6a6a74b77981fb9b347a374ad,

title = "Using Constraint Programming to solve Sudoku puzzles",

abstract = "In Constraint Programming, Enumeration Strategies are crucial for resolution performances. In this work, we model the known NP-complete problems Latin Square, Magic Square and Sudoku as a Constraint Satisfaction Problems. We solve them with Constraint Programming comparing the performance of different Variable and Value Selection Heuristics in its Enumeration phase.",

author = "Broderick Crawford and Mary Aranda and Carlos Castro and Eric Monfroy",

year = "2008",

doi = "10.1109/ICCIT.2008.154",

language = "English",

isbn = "9780769534077",

series = "Proceedings - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008",

pages = "926--931",

booktitle = "Proceedings - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008",

note = "3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008 ; Conference date: 11-11-2008 Through 13-11-2008",

}

Crawford, B, Aranda, M, Castro, C & Monfroy, E 2008, Using Constraint Programming to solve Sudoku puzzles. in Proceedings - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008., 4682365, Proceedings - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008, vol. 2, pp. 926-931, 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008, Busan, Korea, Republic of, 11/11/08. https://doi.org/10.1109/ICCIT.2008.154

Using Constraint Programming to solve Sudoku puzzles. / Crawford, Broderick; Aranda, Mary; Castro, Carlos et al.
Proceedings - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008. 2008. p. 926-931 4682365 (Proceedings - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008; Vol. 2).

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

TY - GEN

T1 - Using Constraint Programming to solve Sudoku puzzles

AU - Crawford, Broderick

AU - Aranda, Mary

AU - Castro, Carlos

AU - Monfroy, Eric

PY - 2008

Y1 - 2008

N2 - In Constraint Programming, Enumeration Strategies are crucial for resolution performances. In this work, we model the known NP-complete problems Latin Square, Magic Square and Sudoku as a Constraint Satisfaction Problems. We solve them with Constraint Programming comparing the performance of different Variable and Value Selection Heuristics in its Enumeration phase.

AB - In Constraint Programming, Enumeration Strategies are crucial for resolution performances. In this work, we model the known NP-complete problems Latin Square, Magic Square and Sudoku as a Constraint Satisfaction Problems. We solve them with Constraint Programming comparing the performance of different Variable and Value Selection Heuristics in its Enumeration phase.

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

U2 - 10.1109/ICCIT.2008.154

DO - 10.1109/ICCIT.2008.154

M3 - Conference contribution

AN - SCOPUS:57849140148

SN - 9780769534077

T3 - Proceedings - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008

SP - 926

EP - 931

BT - Proceedings - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008

T2 - 3rd International Conference on Convergence and Hybrid Information Technology, ICCIT 2008

Y2 - 11 November 2008 through 13 November 2008

ER -

Using Constraint Programming to solve Sudoku puzzles

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this