Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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)

[thumbnail of LEWIS on the combination of constraint programming and the stochasitc search the sudoku case.pdf]
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:
Date of First Compliant Deposit: 30 March 2016
Last Modified: 07 Nov 2023 05:41
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 Edit Item

Downloads

Downloads per month over past year

View more statistics