List coloring based algorithm for the Futoshiki puzzle
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.
[1] Bobga, B., Goldwasser, J.L., Hilton A.J.W. & Johnson P.D. (2011). Completing partial latin squares: Cropper’s question. Australasian Jour- nal of Combinatorics, 49, 127-152.
[2] Goldwasser, J., Hilton A., Hoffman D.G. & Ozkan, S. (2015). Hall’s theorem and extending partial latinized rectangles. Journal of Combi- natorial Theory Series A, 130, 26-41. https: //doi.org/10.1016/j.jcta.2014.10.007
[3] Euler, R. (2010). On the completability of incom- plete Latin squares. European Journal of Combi- natorics, 31, 535-552. https://doi.org/10.101 6/j.ejc.2009.03.036
[4] Colbourn, C.J. (1984). The complexity of com- pleting partial latin squares. Discrete Applied Mathematics, 8, 25-30. https://doi.org/10.1 016/0166-218X(84)90075-1
[5] Haraguchi, K. & Ono, H. (2014). Approximabil- ity of Latin square completion type puzzles. In- ternational Conference on Fun with Algorithms, 218-229. https://doi.org/10.1007/978-3-319 -07890-8_19
[6] Donovan, D. (2010). The completion of partial latin squares. Australasian Journal of Combina- torics, 22, 247-264.
[7] 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
[8] Ivanyi, A. & Nemeth, Z. (2011). List coloring of Latin and Sudoku graphs. 8th Joint Conf. on Math. and Comp. Sci.
[9] Yato, T. & Seta, T. (2003). Complexity and com- pleteness of finding another solution and its ap- plication to puzzles. IEICE Transactions on Fun- damentals of Electronics, Communications and Computer Sciences, E86-A, 5, 1052-1060.
[10] Norvig, P. (2018). Solving every Sudoku puzzle. http://norvig.com/sudoku.html.
[11] 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
[12] Knuth, D.E. Dancing links. (2000). Millennial Perspectives in Computer Science. Proceedings of the 1999 Oxford-Microsoft Symposium, 187-214.
[13] 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
[14] Pacurib, J.A., Seno, G.M.M. & Yusiong, J.P.T.(2009). Solving Sudoku puzzles using improved artificial bee colony algorithm. In Fourth Interna- tional Conference on Innovative Computing, In- formation and Control (ICICIC), 885-888. http s://doi.org/10.1109/ICICIC.2009.334
[15] Moraglio, A., & Togelius, J. (2007). Geometric particle swarm optimization for the Sudoku puz- zle. In Proceedings of the 9th Annual Confer- ence on Genetic and Evolutionary Computation (GECCO), 118-125. https://doi.org/10.114 5/1276958.1276975
[16] Lloyd, H. & Amos, M. (2020). Solving sudoku with ant colony optimization, IEEE Transactions on Games, 12, 302-311. https://doi.org/10.1 109/TG.2019.2942773
[17] Musliu, N., & Winter, F. (2017). A Hybrid Ap- proach for the Sudoku Problem: Using Constraint Programming in Iterated Local Search, IEEE In- telligent Systems, 32 (2), 52-62. https://doi.or g/10.1109/MIS.2017.29
[18] Lastrina, M.A. (2012). List-coloring and sum-list coloring problems on graphs. PhD Thesis, Iawo University.
[19] Tuza, Z. (1997). Graph colorings with local con- straints - a survey. Discussiones Mathematicae Graph Theory, 17, 161-228. https://doi.org/ 10.7151/dmgt.1049
[20] Karp, R.M. (1972). Reducibility among Combi- natorial 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
[21] Kratochvil, J., & Tuza, Z. (1994). Algorith- mic complexity of list coloring. Discrete Applied Mathematics, 50(3), 297-302. https://doi.org/ 10.1016/0166-218X(94)90150-3
[22] Diestel, R. (2017). Graph Theory. Graduate Texts in Mathematics, Heidelberg: Springer-Verlag. ht tps://doi.org/10.1007/978-3-662-53622-3
[23] 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.
[24] Lov´asz, L. (1973). Coverings and coloring of hy- pergraphs. Proc. 4th Southeastern Conf. on Com- binatorics, Graph Theory and Computing, 3-12.
[25] Erdos, P. & Rubin, A.L., Taylor. (1979). Choos- ability in graphs. Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, 26, 125-157.
[26] Garey, M.R. & Johnson, D.S. Computers and Intractability, A guide to the theory of NP- Completeness. W. H. Freeman and Co., 1979.
[27] Mahmood, A.S. (2019). Design random number generator utilizing the Futoshiki puzzle. Jour- nal of Information Hiding and Multimedia Signal Processing, 10, 178-186.
[28] Haraguchi, K. (2013). The number of inequal- ity signs in the design of Futoshiki puzzle. Jour- nal of Information Processing, 21, 26-32. https: //doi.org/10.2197/ipsjjip.21.26
[29] 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.2498 282
[30] Bondy, J.A. & Murty, U.S.R. (2008). Graph The- ory, Graduate Texts in Mathematics. Springer, New York. https://doi.org/10.1007/978-1 -84628-970-5
[31] Orden, D., Marsa, M.I., Gimenez, G.J.M. & Hoz, E. (2017). Spectrum graph coloring and appli- cations to Wi-Fi channel assignment. Symmetry, 10(3), 65. https://doi.org/10.3390/sym10030 065
[32] Garg, N., Papatriantafilou M. & Tsigas, P. (1996). Distributed list coloring: how to dynami- cally allocate frequencies to mobile base stations. Eighth IEEE Symposium on Parallel and Dis- tributed Processing, 18-25. https://doi.org/ 10.1109/SPDP.1996.570312
[33] Zeitlhofer, T. & Wess, B. (2003). List-coloring of interval graphs with application to register assign- ment for heterogeneous register-set architectures. Signal Processing, 83 (7), 1411-1425. https: //doi.org/10.1016/S0165-1684(03)00089-6
[34] Denes, J. & Keedwell, AD. (1991). Latin Squares. New Developments in the Theory and Applica- tions, North Holland.
[35] Amos, M., Crossley, M. & Lloyd, H. (2019). Solving nurikabe with ant colony optimization. GECCO ’19: Proceedings of the Genetic and Evo- lutionary Computation Conference Companion, 129-130. https://doi.org/10.1145/331961 9.3338470
[36] Bektur, G. & Aslan, H.K. (2024). Artificial bee colony algorithm for operating room scheduling problem with dedicated/flexible resources and co- operative operations. An International Journal of Optimization and Control: Theories & Applica- tions (IJOCTA), 14(3), 193-207. https://doi. org/10.11121/ijocta.1466
[37] Kostyukova, O. & Tchemisova T. (2024). Explor- ing constraint qualification-free optimality con- ditions for linear second-order cone program- ming. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 14(3), 168-182. https://doi.org/10.11121/ijo cta.1421