List Coloring Based Algorithm for the Futoshiki Puzzle
No Thumbnail Available
Date
2024
Journal Title
Journal ISSN
Volume Title
Publisher
Ramazan Yaman
Open Access Color
OpenAIRE Downloads
OpenAIRE Views
Abstract
Given a graph G = ( V, E ) and a list of available colors L ( v ) for each vertex v is an element of V , where L ( v ) subset of {1,2, . . . , k }, LIST k-COLORING refers to the problem of assigning colors to the vertices of G so that each vertex receives a color from its own list and no two neighboring vertices receive the same color. The decision version of the problem, LIST k-COLORING, is NP-complete even for bipartite graphs. As an application of list coloring problem we are interested in the Futoshiki Problem. Futoshiki is an NP-complete Latin Square Completion Type Puzzle. Considering Futoshiki puzzle as a constraint satisfaction problem, we first give a list coloring based algorithm for it which is efficient for small boards of fixed size. To thoroughly investigate the efficiency of our algorithm in comparison with a proposed backtracking-based algorithm, we conducted a substantial number of computational experiments at different difficulty levels, considering varying numbers of inequality constraints and given values. Our results from the extensive range of experiments indicate that the list coloring-based algorithm is much more efficient.
Description
Keywords
List coloring, Precoloring extension, Latin square completion puzzle, Futoshiki puzzle, Personnel scheduling
Turkish CoHE Thesis Center URL
Fields of Science
Citation
WoS Q
Scopus Q
Q2
Source
Volume
14
Issue
4
Start Page
294
End Page
307