Ant Colony Optimization Algorithm for the Futoshiki Puzzle

Year 2025, Volume: 38 Issue: 4, 1754 - 1768, 01.12.2025

Banu Baklan Sen , Öznur Yaşar

https://doi.org/10.35378/gujs.1406713

Abstract

Futoshiki is a computationally hard problem belonging to the Latin Square Completion-type Puzzles. It is played on a partially filled n×n grid that may include inequality constraints between cells. The objective is to complete the grid such that each row and column contains the integers from 1 to n exactly once, while also satisfying all inequality constraints. In this work, we propose FutoshikiACO, an Ant Colony Optimization-based algorithm to solve Futoshiki instances of fixed size. We evaluate the performance of this stochastic method through computational experiments. Compared to existing deterministic approaches, FutoshikiACO explores a significantly reduced search space. Our results not only demonstrate the inherent complexity of the Futoshiki problem but also highlight the types of instances where ant colony-based metaheuristics are particularly effective in solving such constraint satisfaction problems.

Keywords

Futoshiki , Metaheuristics , Ant Colony Optimization , Bio-inspired Algorithms

References

• [1] Colbourn, C. J., “The complexity of completing partial latin squares”, Discret. Appl. Math., 8 (1): 25-30, (1984). DOI: https://doi.org/10.1016/0166-218X(84)90075-1
• [2] Garey, J. D., M. R., “Computers and intractability”, A Guide to the Theory of Np-completeness. 338: 79-80, (1979). DOI: https://doi.org/10.1137/1024022
• [3] Andersson, D., “Hashiwokakero is NP-complete’’, Inf. Processing Letters 109(19): 1145-1146, (2009). DOI: 10.1016/j.ipl.2009.07.017
• [4] Kölker, J., “Kurodokora is NP-complete”, J. of Inf. Processing 20(3): 694-706, (2012). DOI: 10.1177/1073858411435128
• [5] Haraguchi, K., Ono, H., “Approximability of latin square completion-type puzzles,” in Fun with Algorithms - 7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Proceedings, 8496, (2014). DOI: 10.1007/978-3-319-07890-8_19
• [6] Donovan, D. M., “The completion of partial latin squares”, Australas. J Comb., 22:247-264, (2000).
• [7] Norvig, P., “Solving every sudoku puzzle,” http://norvig.com/sudoku.html, (2018).
• [8] Dorigo, M., Birattari, M., Stützle, T., “Ant colony optimization,” IEEE Comput. Intell. Mag., 1(4):28-39, (2006). DOI: 10.1109/MCI.2006.329691
• [9] Solnon, C., Khichane M., Albert P., “Strong combination of ant colony optimization with constraint programming optimization,” Integration of AI and or Techniques in Constraint Programming for Combinatorial Optimization Problems, 7th International Conference, CPAIOR 2010, Bologna, Italy, June 14-18, (2010). DOI: 10.1007/978-3-642-13520-26
• [10] Lloyd, H., Amos, M., “Solving sudoku with ant colony optimization,” IEEE Trans. Games, 12(3):302-311, (2020). DOI: https://doi.org/10.1109/tg.2019.2942773
• [11] Knuth, D. E., Davies, J., Roscoe, B., Woodcock, J., “Millennial perspectives in computerscience,” Proceedings of the 1999 Oxford-Microsoft Symposium, 187-214, (2000). DOI: 10.1145/2576802.2576832
• [12] Şen, B. B., Diner, Ö. Y., “List coloring based algorithm for the Futoshiki puzzle,” An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 14(4): 294–307, (2024). DOI: 10.11121/ijocta.1432
• [13] Bishop, J. M., “Stochastic Searching Networks”, IEE Conf. Artificial Neural Networks, 329-331, (1989). 10.1007/978-94-011-2360-0_24
• [14] Lastrina, M. A., “List-coloring and sum-list-coloring problems on graphs”, Graduate thesis and dissertations, Iawo University, (2012).
• [15] Tuza, Z., “Graph colorings with local restrictions - a survey,” Discussiones Mathematicae Graph Theory, 17: 161-228, (1997). DOI: doi.org/10.7151/dmgt.1049
• [16] Vizing, V., “Coloring the vertices of a graph in prescribed colors,” Metody Diskret. Anal. v. Teorii Kodov i Shem, 101(29):3-10, (1976).
• [17] Beni, G., Wang, J., ‘‘Swarm intelligence in cellular robotic systems’’, Robots and Biological Systems: Towards a New Bionics, 102: 703-712, (1993). DOI: 10.1007/978-3-642-58069-7_38
• [18] Kennedy, J., Eberhart, R., “Particle swarm optimization”, Proceedings of International Conference on Neural Networks (ICNN'95), Perth, WA, Australia, 1942-1948, (1995). DOI: http://dx.doi.org/10.1109/ICNN.1995.488968
• [19] Musliu, N., Winter, F., “A hybrid approach for the sudoku problem: Using constraint programming in iterated local search,” IEEE Intell. Syst., 32(2):52-62, (2017). DOI: 10.1109/MIS.2017.29
• [20] Amos, M., Crossley, M., Llyod H., “Solving nurikabe with ant colony optimization,” the Genetic and Evolutionary Computation Conference Companion, 129-130, (2019). DOI: https://doi.org/10.1145/3319619.3338470 [21] Pillay, N., “Finding solutions to sudoku puzzles using human intuitive heuristics,” South Afr. Comput. J., 49:25-34, (2012).
• [22] Li, S., Wei, Y., Liu, X., Zhu, H., Yu, Z., “A New Fast Ant Colony Optimization Algorithm: The Saltatory Evolution Ant Colony Optimization Algorithm.” Mathematics, 10, 925, (2022). DOI: 10.3390/math10060925
• [23] Wang, C., Sun, B., Du, K.J., Li, J.Y., Zhan, Z.H., Jeon, S.W., Wang, H., Zhang, J., “A novel evolutionary algorithm with column and sub-block local search for sudoku puzzles”, IEEE Transactions on Game, 1-11, (2023). DOI: 10.1109/TG.2023.3236490