Prisoners and Guards on Rectangular Boards
Grady Bullington, Linda Eroh, and Steven J. Winters
University of Wisconsin, Oshkosh
800 Algoma Blvd.
Oshkosh, WI 54901
Woolbright introduced the "Prisoners and Guards" game
as a two-player game
on an n × n checkerboard. At the
beginning of the game, every square of the board has a guard. At each
stage in the game, for each prisoner, there must be at least as many
guards as prisoners on adjacent squares. The players take turns
either replacing a guard with a prisoner in their color or replacing
one prisoner (of either color) with a guard, then replacing two guards
with prisoners in their color, subject to the rule above. When
neither player can adjust the board any further, the player with more
prisoners in their color wins. Howard, Ionascu, and Woolbright gave
formulas for the maximum number of prisoners on
n × n boards.
In this paper, we give formulas for the number of prisoners in the
maximum configurations of n × m boards,
where 2 ≤ n < m,
for n = 2, 3, and 5, upper and lower bounds that differ by less
than 2 when n = 4, and a lower bound for n = 6.
Full version: pdf,
Received September 17 2013;
revised version received January 24 2014; June 3 2014; July 16 2014.
Published in Journal of Integer Sequences, July 18 2014.
Revised, July 17 2015; July 30 2015.
Journal of Integer Sequences home page