John Horton Conway, an English Mathematician, is popular for his contributions to numerous fields of mathematics including recreational mathematics. The Conway's Soldiers game is one of the most notable inventions.
Conway's Soldiers consists of a board which extends finitely in all directions. There is a dividing line and the upper part is filled with light coloured squares while the lower part with dark coloured squares.
The game can also be played using a chess/checkers board with checkers behind the dividing line.
Each checker can be used to move horizontally or vertically over another checker only.
Diagonal movement or moving over multiple checkers is not allowed.
The goal of the game is to bring a soldier(checker) to the highest row possible above the dividing line and to determine the minimal number of soldiers at the beginning and the configuration necessary to achieve this row.
For example, it is possible to get to the first line in just 1 move using 2 soldiers.
The Red line is the diving line. The soldier in the last row vertically jumps over the next soldier and reaches the first line.
As the line number increases, the problem gets harder and harder.
Reaching the 2nd line is fairly easy, but you start having problems getting to the 3rd and 4th line with limited soldiers.
To reach the 4th line, 20 soldiers and 19 moves are required.
I would encourage you to try finding configurations for the first 4 lines and even try for the 5th line, I will include the link to play online and to check the solutions at the end.
The real problem arises in getting the soldier to line 5. After checking the solution for line 4, one might think more and more soldiers are needed. Luckily, the board extends finitely and you have finitely as many as soldiers as you require.
If it is possible to reach line 4 with just 20 soldiers, line 5 can surely be reached with a large number of soldiers, right?
Unfortunately, that is not the case. It has been proved that line 5 is impossible to reach with any finite number of soldiers.
There is a rigorous mathematic proof where each square is labelled as x^n where n is the number of squares away from the target square. The target square(T) itself is x^0 or The proof includes evaluating each possible move.
Their are 3 possible moves:
1) Positive jump: a jump that gets the soldier closer to T.
2) Neutral jump: a jump that maintains the same distance from T.
3) Negative jump: a jump that puts the soldier further away from T.
A score is assigned based on the sum of the values under each soldier. A value of x is found which ensures that the total score never increases with each move.
The total sum is found for a target square in each line.
The proof shows that the maximum possible original sum for a target square in line 5 is 1 which can only be obtained using infinite soldiers. The sum will always be less than 1 for all finite number of soldiers.
A sum of 1 means that the soldier must be on the target square itself.
Since the sum will always be less than 1 for finite soldiers, line 5 may never be reached.
{The proof is not included in the blog, but you can access the link at the end}
The Conway's soldier problem does not have any patterns or repeated steps that can be followed to obtain the desired result. Each level requires one to think and make logical steps.
This solo game has easy first few levels and suddenly becomes extremely hard to solve.
The game is often used as a metaphor for expertise and hope.
Conway's Soldiers game represents how everything starts off easy and gets hard as you move deeper into it. The solution for reaching line 5 was found by Simon Tatham and Gareth Taylor through creativity by using infinite soldiers.
The first 4 levels have clever and comprehensible solutions and I recommend you to try to find them.
Resources:
Solutions for levels 1 through 4 - https://www.youtube.com/watch?v=pcjjyXTSmhE.
Solution and proof for level 5 - https://tartarus.org/gareth/maths/stuff/solarmy.pdf.
Video proof for the same - https://www.youtube.com/watch?v=Or0uWM9bT5w&t=14s.