SavedAdd your journal

Journals / Gazi University Journal of Science / 2025 / Volume: 38 Issue: 4

Ant Colony Optimization Algorithm for the Futoshiki Puzzle

Banu Baklan Sen(University of Applied Science Europe Amsterdam)0000-0003-4545-5044
Öznur Yaşar(KADİR HAS ÜNİVERSİTESİ)0000-0002-9271-2691
Pages
—
Publication Date
2025-12-01
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

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.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:Futoshiki is a computationally hard problem belonging to the Latin Square Completion-type Puzzles.
📊
Key Findings & Data: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.
💡
Conclusion & Impact: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.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Futoshiki · Metaheuristics · Ant Colony Optimization

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.

🔖

Cite This Article

Sen, B. B., Yaşar, Ö. (2025). Ant Colony Optimization Algorithm for the Futoshiki Puzzle. Gazi University Journal of Science, Volume: 38 Issue: 4. https://doi.org/10.35378/gujs.1406713

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (22)

  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).
  21. 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. 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