The state set is {-, F, p, q, b, c, r, s, 0, 1, 2, 3, 4, 5, 6, 7}, the quiescent state is -, the excited state is p, and the firing state is F.
The transition function is listed below, in the form of a sequence of lines, each of which contains the previous state of the machine on the left, our previous state, the previous state of the machine on the right, and our next state, in that order. ? denotes any state. If two lines conflict, use the line which comes first in the sequence. Soldiers at the end should pretend they have a neighbor in state X beyond the end.
Waksman's solution appears to be buggy, and only works when the number of soldiers is three, six times a power of two, or one less than six times times a power of two. However, it does illustrate an approach to a minimal-time solution.
- - 0 1 - - 1 0 - - 4 5 - - 5 4 - - 2 r - - 3 - - - 6 - - - 7 - b - 0 1 c - 0 1 b - 1 0 c - 1 0 b - 4 5 c - 4 5 b - 5 4 c - 5 4 b - 2 r c - 2 r b - 3 - c - 3 - b - 6 - c - 6 - b - 7 - c - 7 - r - 0 1 r - 1 0 r - 4 5 r - 5 4 r - 2 - r - 3 - r - 6 - r - 7 - s - 0 1 s - 1 0 s - 4 5 s - 5 4 p - 3 b q - 6 b X - 0 p X - 1 q X - 4 p X - 5 q 0 - - s 0 - b s 0 - c s 1 - - - 1 - b - 1 - c - 1 - s - 1 - p b 4 - - - 4 - b - 4 - c - 5 - - - 5 - b - 5 - c - 2 - - 3 2 - b 3 2 - c 3 2 - X p 3 - - 2 3 - b 2 3 - c 2 3 - X q 6 - - 7 6 - b 7 6 - c 7 6 - X p 7 - - 6 7 - b 6 7 - c 6 7 - X q - - - - - - b - - - c - - - r r - - s - - - p 0 - - q 4 - - X - b - - - c - - - b - b - b - c - c - b - c - c - b - r r c - r r b - s - c - s - b - p - c - p - b - q - c - q - r - - - r - b - r - c - r - p 0 s - - s s - b s s - c s s - p s s - q s p - - 2 p - b - p - c - p - r r p - s - p - p p p - q p q - - 6 q - b - q - c - q - r r q - s - q - p p q - q p X - - - p b p p p b q p q b p p q b q p p b r r q b r r p c p p p c q p q c p p q c q p p p p F p p q F q p p F q p q F p p X F q p X F X p p F X p q F p q p F p q q F q q p F q q q F p q X F q q X F X q p F X q q F ? - p 0 r - ? - ? b p b ? b q b ? b 0 p ? b 4 q ? b 1 q ? b 5 p ? b r r p b ? b q b ? b 2 b ? p 6 b ? q 3 b ? q 7 b ? p s b ? s ? c 0 p ? c 4 q ? c 1 q ? c 5 p ? c r - 2 c ? p 6 c ? q 3 c ? q 7 c ? p s c ? - b r ? c c r ? b p r ? b q r ? b ? s b c ? s c b ? s p b ? s q b ? p p p ? p q p ? p X p p p ? p q p ? p X p ? p ? q p q ? q q q ? q X q p q ? q q q ? q X q ? q ? 0 p b b 4 ? q c 4 ? q b 5 ? p c 5 ? p p 2 ? b ? 6 b q ? 6 c q ? 7 b p ? 7 c p ? b ? b ? c ? c ? r ? - ? s ? - ? p ? p ? q ? q ? 0 ? - ? 1 ? - ? 4 ? s ? 5 ? - ? 2 ? - ? 3 ? - ? 6 ? r ? 7 ? -
Back to the firing squad solution page
David Moews ( dmoews@fastmail.fm )
Last significant update 20-IX-2004