Introduction to the “prisoners and guards” game.
Eugen J. Ionaşcu, T. A. Howard · CSU ePress (Columbus State University) · 2009
We study the half-dependent problem for the king graph Kn. We give proofs to establish the values h(Kn) for n ∈ {1, 2, 3, 4, 5, 6} and an upper bound for h(Kn) in general. These proofs are independent of computer assisted results. Also, we introduce a two-player game whose winning strategy is tightly related with the values h(Kn). This strategy is analyzed here for n = 3 and some facts are given for the case n = 4. Although the rules of the game are very simple, the winning strategy is highly complex even for n = 4.