On the combination of constraint programming and stochastic search: the Sudoku case

Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X 2007. On the combination of constraint programming and stochastic search: the Sudoku case. Hybrid Metaheuristics, Lecture Notes in Computer Science, vol. 4771. Springer, pp. 96-107. (10.1007/978-3-540-75514-2_8)

Preview

PDF - Accepted Post-Print Version Download (182kB) | Preview

Abstract

Sudoku is a notorious logic-based puzzle that is popular with puzzle enthusiasts the world over. From a computational perspective, Sudoku is also a problem that belongs to the set of NP-complete problems, implying that we cannot hope to find a polynomially bounded algorithm for solving the problem in general. Considering this feature, in this paper we demonstrate how a metaheuristic-based method for solving Sudoku puzzles (which was reported by the same author in an earlier paper), can actually be significantly improved if it is coupled with Constraint Programming techniques. Our results, which have been gained through a large amount of empirical work, suggest that this combination of techniques results in a hybrid algorithm that is significantly more powerful than either of its constituent parts.

Item Type:	Book Section
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Additional Information:	Pdf uploaded in accordance with the publisher’s policy at http://www.sherpa.ac.uk/romeo/issn/0302-9743/ (accessed 07/08/2014)
Publisher:	Springer
Related URLs:	Publisher
Date of First Compliant Deposit:	30 March 2016
Last Modified:	08 Jan 2025 12:45
URI:	https://orca.cardiff.ac.uk/id/eprint/27751

Citation Data

Cited 4 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item