List coloring based algorithm for the Futoshiki puzzle
DOI:
https://doi.org/10.11121/ijocta.1432Keywords:
List Coloring, Precoloring Extension, Latin Square Completion Puzzle, Futoshiki Puzzle, Personnel SchedulingAbstract
Given a graph G=(V, E) and a list of available colors L(v) for each vertex v\in V, where L(v) \subseteq {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.
Downloads
References
Amos, M., Crossley, M. & Lloyd, H. (2019). Solving nurikabe with ant colony optimization. GECCO’19: Proceedings of the Genetic and Evolutionary Computation Conference Companion, 129-130. https://doi.org/10.1145/3319619.3338470
Bektur, G. & Aslan, H.K. (2024). Artificial bee colony algorithm for operating room scheduling problem with dedicated/flexible resources and cooperative operations. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 14(3), 193-207. https://doi.org/10.11121/ijocta.1466
Bobga, B., Goldwasser, J.L., Hilton A.J.W. & Johnson P.D. (2011). Completing partial latin squares: Cropper’s question. Australasian Journal of Combinatorics, 49, 127-152.
Bondy, J.A. & Murty, U.S.R. (2008). Graph Theory, Graduate Texts in Mathematics. Springer, New York. https://doi.org/10.1007/978-1-84628-970-5
Burke, E.K., De Causmaecker, P., Berghe, G.V. & Landeghem, H.V. (2004). The State of the Art of Nurse Rostering. Journal of Scheduling, 7, 441- 499. https://doi.org/10.1023/B:JOSH.0000046076.75950.0b
Colbourn, C.J. (1984). The complexity of completing partial latin squares. Discrete Applied Mathematics, 8, 25-30. https://doi.org/10.1016/0166-218X(84)90075-1
Crawford, B., Castro, C. & Monfroy, E. (2009). Solving sudoku with constraint programming. MCDM, CCIS Communications in Computer and Information Science, 35, 345-348. https://doi.org/10.1007/978-3-642-02298-2_52
Denes, J. & Keedwell, AD. (1991). Latin Squares. New Developments in the Theory and Applications, North Holland.
Diestel, R. (2017). Graph Theory. Graduate Texts in Mathematics, Heidelberg: Springer-Verlag. https://doi.org/10.1007/978-3-662-53622-3
Donovan, D. (2010). The completion of Partial Latin Squares. Australasian Journal of Combinatorics, 22, 247-264.
Erdos, P. & Rubin, A.L., Taylor. (1979). Choosability in graphs. Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, 26, 125-157.
Euler, R. (2010). On the completability of incomplete Latin squares. European Journal of Combinatorics, 31, 535-552. https://doi.org/10.1016/j.ejc.2009.03.036
Falcone, J.L. (2013). Scheduling 101: a method to the application of sudoku game theory to surgical rotation scheduling. The American Surgeon, 79(9), 958-960. https://doi.org/10.1177/000313481307900939
Galvin, F., Stephen, C.L., Kim, S.S. & Callan, D. (2001). A Generalization of Hall’s Theorem: 10701. The American Mathematical Monthly, 108, 79-80. https://doi.org/10.2307/2695691
Garey, M.R. & Johnson, D.S. Computers and Intractability, A guide to the theory of NP-Completeness. W. H. Freeman and Co., 1979.
Garg, N., Papatriantafilou M. & Tsigas, P. (1996). Distributed list coloring: how to dynamically allocate frequencies to mobile base stations. Eighth IEEE Symposium on Parallel and Distributed Processing, 18-25. https://doi.org/10.1109/SPDP.1996.570312
Glover, F.W. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533- 549. https://doi.org/10.1016/0305-0548(86)90048-1
Goldwasser, J., Hilton A., Hoffman D.G. & Ozkan, S. (2015). Hall’s theorem and extending partial latinized rectangles. Journal of Combinatorial Theory Series A, 130, 26-41. https://doi.org/10.1016/j.jcta.2014.10.007
Haraguchi, K. & Ono, H. (2014). Approximability of Latin square completion type puzzles. International Conference on Fun with Algorithms, 218-229. https://doi.org/10.1007/978-3-319-07890-8_19
Haraguchi, K. (2013). The number of inequality signs in the design of Futoshiki puzzle. Journal of Information Processing, 21, 26-32. https://doi.org/10.2197/ipsjjip.21.26
Ivanyi, A. & Nemeth, Z. (2011). List coloring of Latin and Sudoku graphs. 8th Joint Conf. on Math. and Comp. Sci.
Pacurib, J.A., Seno, G.M.M. & Yusiong, J.P.T. (2009). Solving Sudoku puzzles using improved artificial bee colony algorithm. In Fourth International Conference on Innovative Computing, In- formation and Control (ICICIC), 885-888. https://doi.org/10.1109/ICICIC.2009.334
Karp, R.M. (1972). Reducibility among Combinatorial Problems. In: Complexity of Computer Computations. The IBM Research Symposia Se- ries, Boston, MA, Springer. https://doi.org/10.1007/978-1-4684-2001-2_9
Knuth, D.E. Dancing links. (2000). Millennial Perspectives in Computer Science. Proceedings of the 1999 Oxford-Microsoft Symposium, 187-214.
Kostyukova, O. & Tchemisova T. (2024). Exploring constraint qualification-free optimality conditions for linear second-order cone programming. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 14(3), 168-182. https://doi.org/10.11121/ijocta.1421
Kratochvil, J., & Tuza, Z. (1994). Algorithmic Complexity of list coloring. Discrete Applied Mathematics, 50(3), 297-302. https://doi.org/10.1016/0166-218X(94)90150-3
Lastrina, M.A. (2012). List-coloring and sum-list coloring problems on graphs. PhD Thesis, Iawo University.
Laurent, B. & Hao, J.-K. (2009).List-graph colouring for multiple depot vehicle scheduling, International Journal of Mathematics in Operational Research, 2(1-2), 228-245. https://doi.org/10.1504/IJMOR.2009.022883
Lloyd, H. & Amos, M. (2020). Solving sudoku with ant colony optimization. IEEE Transactions on Games, 12, 302-311. https://doi.org/10.1109/TG.2019.2942773
Lovasz, L. (1973). Coverings and coloring of hypergraphs. Proc. 4th Southeastern Conf. on Combinatorics, Graph Theory and Computing, 3-12.
Mahmood, A.S. (2019). Design Random Number Generator Utilizing The Futoshiki Puzzle. Journal of Information Hiding and Multimedia Signal Processing, 10, 178-186.
Moraglio, A., & Togelius, J. (2007). Geometric particle swarm optimization for the Sudoku puzzle. In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (GECCO), 118-125. https://doi.org/10.1145/1276958.1276975
Musliu, N., & Winter, F. (2017). A Hybrid Approach for the Sudoku Problem: Using Constraint Programming in Iterated Local Search, IEEE Intelligent Systems, 32 (2), 52-62. https://doi.org/10.1109/MIS.2017.29
Norvig, P. (2018). Solving every Sudoku puzzle. http://norvig.com/sudoku.html.
Orden, D., Marsa, M.I., Gimenez, G.J.M. & Hoz, E. (2017). Spectrum graph coloring and applications to Wi-Fi channel assignment. Symmetry, 10(3), 65. https://doi.org/10.3390/sym10030065
Qu, R., Burke, K., McCollum, B., Merlot L.T. & Lee, S.Y. (2009). A survey of search methodologies and automated system development for examination timetabling. Journal of Scheduling, 12, 55-89. https://doi.org/10.1007/s10951-008-0077-5
Ramachandran, K., Belding, E., Almeroth, K. & Buddhikot, M. (2006). Interference-aware channel assignment in multi-radio wireless mesh networks. Proceedings IEEE INFOCOM 2006, 25TH IEEE International Conference on Computer Communications, 1-12. https://doi.org/10.1109/INFOCOM.2006.177
Sahu, H.S., Nayak, S.K. & Mishra, S. (2016). Maximizing the Power Generation of a Partially Shaded PV Array. IEEE Journal of Emerging and Selected Topics in Power Electronics, 4, 626-637. https://doi.org/10.1109/JESTPE.2015.2498282
Tuza, Z. (1997). Graph colorings with local constraints - a survey. Discussiones Mathematicae Graph Theory, 17, 161-228. https://doi.org/10.7151/dmgt.1049
Vizing, V.G. (1976). Coloring the vertices of a graph in prescribed colors. Diskret. Analiz., Metody Diskret. Anal. v. Teorii Kodov i Shem, 101, 3-10.
Yato, T. & Seta, T. (2003). Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A, 5, 1052-1060.
Zeitlhofer, T. & Wess, B. (2003). List-coloring of interval graphs with application to register assignment for heterogeneous register-set architectures. Signal Processing, 83 (7), 1411-1425. https://doi.org/10.1016/S0165-1684(03)00089-6
Zucchi, G., Iori, M. & Subramanian, A. (2021). Personnel scheduling during Covid-19 pandemic. Optimization Letters, 15, 1385-1396. https://doi.org/10.1007/s11590-020-01648-2
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Banu Baklan ?en, Oznur Yasar Diner
This work is licensed under a Creative Commons Attribution 4.0 International License.
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
