Conway’s Soldiers was invented by John Conway in 1961.
The structure and rules of the game are quite simple:
- You have an infinite checkerboard and infinite ‘soldiers’.
- The board is divided by an infinite horizontal line.
- A valid move consists of jumping over one neighboring soldier vertically or horizontally (diagonal movement is not allowed).
- A soldier that was jumped over is removed from the board.
The goal of the game is to place a soldier as far as possible from the horizontal line.
With infinite board and infinite soldiers, you might think that it is very possible to reach any distance, but it might be hard to come up with the correct sequence of moves but shockingly enough, you can reach just a few lines above the horizontal lines, let’s explore.
Cracking The Possible Levels
Disclaimer: I am not associated with these online interactive games in a way.
Well, the time has come, let’s play.
Level one is fairly easy, requires only two soldiers and one move.
Simply get the blue soldier and jump over the red one to reach the green marked spot and that’s it, level one is done.
Moving over to level two, we will need 4 soldiers and 3 moves.
Moving red soldier over the blue one, then yellow over black, and finally yellow over red. the yellow soldier got to the green spot, well done.
To complete level three we will need 8 soldiers and 7 moves.
Since imagining 7 moves in your head might be challenging I will only show you the setup so you could play around with it in the online tool I mentioned above or with a checkerboard for example.
Note that in the above setup, the soldiers marked as ‘B’ can be replaced with the ones marked with ‘A’ (both setups will get you to level 3).
To complete level 4, we need 20 soldiers and 19 moves.
Same as before, 19 is just too much to imagine (or is it just me?), so here’s the setup.
Believe it or not, no matter how hard you try you won’t succeed in completing level 5, no matter how many soldiers you have.
To those of you who are getting triggered by me saying it’s impossible and want to prove me wrong, proceed with caution, it might be time-consuming.
Conway proved that, regardless of the strategy used, there is no finite sequence of moves that will allow a soldier to advance more than four rows above the horizontal line.
The outline of the proof can be found on Wikipedia.
A few years later, Simon Tatham and Gareth Taylor showed that it is possible to reach the 5th line with a sequence of infinite moves.
At the beginning of their paper, they give a good intuition about how Conway proved his argument:
Aside from their paper, they create a web page containing the proof and cool visualizations.