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 x 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.