In this thesis, we address the flood-fill problem, known in the literature as the
game Flood-It, where the objective is to unify the color of a grid of squares in
the minimum number of moves. The problem is formally defined on a discrete
grid and generalized to arbitrary connected graphs. In the theoretical section,
we present a proof of the problem’s NP-hardness via a polynomial reduction
from the Shortest Common Supersequence (SCS) problem.
To find optimal solutions, we transform the problem into a Boolean Sat
isfiability (SAT) problem in Conjunctive Normal Form (CNF). Using state
of-the-art SAT solvers, we analyze the limits of solvability and find that
exact methods are effective primarily for small and medium-sized instances.
Through regression analysis on generated graphs, we identify key topolog
ical metrics, such as average path length and the number of colors, which
correlate strongly with the problem’s complexity.
Due to the exponential time complexity of exact methods, the final part
of the thesis involves the development and evaluation of several heuristic
algorithms. The results indicate that a global heuristic, which minimizes
the sum of distances to unvisited nodes, achieves results close to theoretical
optimal values even on large grids with dimensions up to 300 × 300.
|
