Enigmatic Code
Programming Enigma Puzzles
Tantalizer 4: In the arena
Posted by on 29 March 2023
From New Scientist #553, 13th July 1967 [link]
One of the best loved sights of the Roman Arena was a duel to the death between a Gladiator and a Retiarius. The Gladiator, being in armour and carrying a sword, was slow in movement but lethal at close quarters. The Retiarius, having no armour but carrying a net and trident, was most deadly at a distance.
Those who wish to test where the odds lay for themselves will, in these softer days, have to make do with a diagram.
Let us suppose that Gladiator starts at 32 and Retiarius at 1 and that they move in turn. Gladiator moves three circles at each turn and Retiarius four. Both must always move along the lines but can change direction or double back during their move. The duel is won by whoever first lands on top of his opponent at the end of a turn.
Can either player be sure of winning? If so, who?
In the book Tantalizers (1970) a reworded version of this puzzle appears under the title: “The Lion and The Unicorn”.
[tantalizer4]
Enigmatic Code 
It is not clear from the puzzle text who moves first, so this code checks for both scenarios.
We can identify the players by the number of steps they take (+3 and +4). I look at games with an increasing number of moves, as defensive play could continue indefinitely, with the players just moving back and forth between two positions.
This Python program runs in 61ms. (Internal runtime is 768µs).
Run: [ @replit ]
from enigma import (grid_adjacency, irange, inf, union, cache, printf) # we can construct the adjacency matrix from the following grid: # # [00] [01] [02] 03 04 [05] [06] [07] # [08] [09] 10 11 12 13 [14] [15] # [16] 17 18 19 20 21 22 [23] # 24 25 26 27 28 29 30 31 # [32] 33 34 35 36 37 38 [39] # [40] [41] 42 43 44 45 [46] [47] # [48] [49] [50] 51 52 [53] [54] [55] # # the original positions 1 and 32 become 24 and 31 (p1, p32) = (24, 31) xs = {0, 1, 2, 5, 6, 7, 8, 9, 14, 15, 16, 23, 32, 39, 40, 41, 46, 47, 48, 49, 50, 53, 54, 55} adj = dict((k, vs.difference(xs)) for (k, vs) in enumerate(grid_adjacency(8, 7, fn=set)) if k not in xs) # find nodes that can be reached in <k> moves from <src> @cache def move(k, src): if k == 0: return {src} if k > 0: return union(adj[x] for x in move(k - 1, src)) # play a game of (up to) n moves; p1, p2 = position 1, 2; k1, k2 = moves 1, 2 def play(n, p1, p2, k1, k2): if n == 0: return 0 # moves for player 1 p1s = move(k1, p1) # can p1 land on p2? if p2 in p1s: return k1 # consider up to n-1 more moves r = k2 # worst case is a loss for p in p1s: x = play(n - 1, p2, p, k2, k1) if x == k1: return k1 # a win is best if x == 0: r = 0 # then a draw return r # look for a number of moves that guarantee a win for one of the players def check(p1, p2, k1, k2): for n in irange(1, inf): r = play(n, p1, p2, k1, k2) if r != 0: printf("({k1:+}, {k2:+}) -> win for {r:+}") break # Gladiator (32, +3) vs Retiarius (1, +4) check(p32, p1, +3, +4) # Gladiator moves first check(p1, p32, +4, +3) # Retiarius moves firstSolution: Whichever player takes the first turn can guarantee a win.
If +4 moves first from 1 to 12 (or 14), then +3 can only move from 32 to one of (20, 25, 27, 30), and all of these are +4 moves from 12.
And if +3 moves first from 32 to 25 (or 27) and then to 13, then the squares reachable from 13 in +3 moves are exactly those squares reachable from 1 in +8 moves (and 25 is not reachable from 1 in +4 moves).