This thesis studies the lions and contamination problem on triangular grids:
lions move along a graph and clean contamination, which simultaneously
spreads to every unoccupied neighbouring vertex. We ask for the smallest
number of lions needed to clean the grid Pn. We implement a simulation
core and four movement models (strip, polite, caffeinated and monotone)
and, through exhaustive search for n from 3 to 8, determine the minimum
number of lions and compare it with bounds from the literature. The strip,
polite and monotone models require n lions, whereas the caffeinated model
cleans P5 with four and P6 with five lions; fewer than n. We presented the
results in an interactive web application.
|
