Ant Colony Optimization Algorithm for the Futoshiki Puzzle

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. [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. [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. [3] Andersson, D., “Hashiwokakero is NP-complete’’, Inf. Processing Letters 109(19): 1145-1146, (2009). DOI: 10.1016/j.ipl.2009.07.017
4. [4] Kölker, J., “Kurodokora is NP-complete”, J. of Inf. Processing 20(3): 694-706, (2012). DOI: 10.1177/1073858411435128
5. [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. [6] Donovan, D. M., “The completion of partial latin squares”, Australas. J Comb., 22:247-264, (2000).
7. [7] Norvig, P., “Solving every sudoku puzzle,” http://norvig.com/sudoku.html, (2018).
8. [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. [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. [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. [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. [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. [13] Bishop, J. M., “Stochastic Searching Networks”, IEE Conf. Artificial Neural Networks, 329-331, (1989). 10.1007/978-94-011-2360-0_24
14. [14] Lastrina, M. A., “List-coloring and sum-list-coloring problems on graphs”, Graduate thesis and dissertations, Iawo University, (2012).
15. [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. [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. [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. [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. [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. [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).
21. [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
22. [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