This is a variant of a classic two-player pursuit-evasion game. Several of our examples are taken from a 1984 paper by Aigner and Fromme (although that paper considers a model where all villagers can move during the same time step). A presentation of more recent results, discusses some computer proofs by Baird and Bonato from 2012. For those really interested, there is a 2011 book by Bonato and Nowakowski published by AMS.
The judge's tests in leprechaun.in are comprised of a series of individual test cases that can be found separately within the cases/ directory.
Case 1: cycle7-1 (same as in example input)
Cycle of 7 nodes is unsolvable with 1 villager
Case 2: cycle7-2 (same as in example input)
Cycle of 7 nodes with two villagers.
Case 3: house1 (same as in example input)
What makes this case interesting is that outcome depends upon
the rule that Leprechaun is allowed to remain still. If
Leprechaun had to move on each turn, one villager can capture it
by starting at C (in which case Leprechaun starts at D), moving
to A (after which Leprechaun moves to E), then moving to B
(after which Leprechuan must move to either C or D).
Case 4: house2 (same as in example input)
Case 5: peterson2 (same as in example input)
This is the Peterson graph. It is the smallest graph for which 3
villagers suffices but 2 does not.
(Presentation about similar game in which villagers can move in parallel)
Case 6: peterson3 (same as in example input)
Peterson graph. 3 villagers easily win the game by selecting
initial position (e.g., BEF) that effectively covers the graph.
Case 7: components3 (same as in example input)
Graphs is comprised of four separate connected components, each
a line. With only 3 villagers, Leprechaun can hide forever in
other component.
Case 8: components4 (same as in example input)
Same graph as previous case. 4 villagers should each start in
separate component, and then the one that ends up with
Leprechaun can begin the chase on the line.
Case 9: line3-1
line of 3 nodes. Single villager wins in 1 move by starting at center.
Case 10: line4-1
line of 4 nodes. Single villager wins in 2 moves by starting at
either B or C.
Case 11: line4-2
line of 4 nodes. Two villagers win in 1 move by starting with
any combination other than AB or CD.
Case 12: line5-1
line of 5 nodes. One villager wins in 2 by starting at center.
Case 13: line5-2
line of 5 nodes. Two villagers win in 1 move by starting at B
and D.
Case 14: line6-1
line of 6 nodes. One villager wins in 3 moves by starting at C
or D, and chasing down Leprechaun.
Case 15: line6-2
line of 6 nodes. Two villagers win in 1 move by starting at B
and E.
Case 16: line15-1
line of 15 nodes. One villager wins in 7 moves.
Case 17: line15-2
line of 15 nodes. Two villagers wins in 4 moves.
Case 18: line15-3
line of 15 nodes. Three villagers wins in 3 moves.
Case 19: line15-4
line of 15 nodes. Four villagers wins in 2 moves.
Case 20: line15-5
line of 15 nodes. Five villagers win in 1 move by starting at BEHKN.
Case 21: cycle4-1
cycle of 4 nodes. One villager cannot win
Case 22: cycle15-1
cycle of 15 nodes. One villager cannot win
Case 23: cycle15-2
cycle of 15 nodes. Two villagers win in 6 moves.
Case 24: hex.in
Seven node graph that is a hexagon with a central node connected
to all. One villager wins in one move by picking the center (A).
Case 25: star.in
Expansion of the hex example with 2-move win for single villager
Case 26: octa1.in
Edge graph of an octahedron. One villager cannot win.
Case 27: octa2.in
Edge graph of an octahedron. Two villagers win in 1 by starting
at the two poles.
Case 28: grid1.in
5x3 grid. Single villager cannot win.
Case 29: grid2.in
5x3 grid. Two villagers win in four moves by starting at top and
bottom of middle column of 3, and then sweeping to the side with
the leprechaun.
Case 30: large3.in
15 node graph with one isolated node (I) that forces spending
one villager. In all, 3 villagers do not suffice.
Case 31: large4.in
same as previous, but with 4 villagers winning in 2 (for
example, if starting at FGIO).