Conway’s Soldiers
The one player game, Conway’s Soldiers (sometimes known as Solitaire Army), is similar to peg
solitaire. For this exercise, Conway’s board is a 7£8 board with tiles on it. The lower half of the
board is entirely filled with tiles (pegs), and the upper half is completely empty. A tile can move
by jumping another tile, either horizontally or vertically (but never diagonally) onto an empty
square. The jumped tile is then removed from the board.
The user enters the location of an empty square they’d like to get a tile into, and the program
outputs the list of moves that enables the tile to reach there (or warns them it’s impossible). To
do this you will use a list of boards. The initial board is put into this list. Each board in the list
is, in turn, read from the list and all possible moves from that board added into the list. The next
board is taken, and all its resulting boards are added, and so on. However, one problem with is
that repeated boards may be put into the queue and cycles occur. This soon creates an explosively
large number of boards (several million). You can solve this by only adding a board into the list
if an identical one has never been put into the list before. A linear search is acceptable for this
task. Each structure in the list will contain (amongst other things) a board and a record of its
parent board, i.e. the board that it was created from.
Write a program that:
² Inputs a target location for a tile to reach (x in argv[1], y in argv[2]).
² Prints out the correct solution (reverse order is fine) and the number of moves required.
Note that it is perfectly acceptable to use a (very large) array for this list - it doesn’t have to be a
linked list.
The Basic Assignment (75%)
This assignment is to be done individually, not in groups. The assessment includes checking for:
1. No major errors; no unused variables/parameters, variables used before being set etc.
2. Proper use of #includes, #defines used to eliminate constants.
3. Correct type for functions, non-void functions actually return values, return values of
fopen(), scanf() checked.
4. Correct input parsing.
5. Self-Documentation e.g. comments, sensible variable names, functions kept short, consis-
tent indentation.
6. User-Friendliness.
17. Graceful exit after errors - with a useful message.
8. Correct use of 2D arrays (if used).
9. Full testing of code.
Extras (25%)
The basic assignment, as detailed above, is worth a maximum of 75%. Most people will attempt
only this. If you wish to extend the program, here are a few ideas:
² The linear search of board nodes is done using a faster search method.
² The algorithm sorts the list of boards so that better boards are higher in the list.
² Some other extension of your choosing.
If you do attempt an extension, discuss it in a brief plain ascii text file (1 page max) called
report.txt (or report.pdf if you’d prefer) and submit it in the usual manner.
2