• £1,000 in the first year of study in the Computer Science Department at RHUL.

• renewable at the rate of £500 in years two and three.

Please read the Rules of the Challenge.

---

This page describes the program that you must write as part of your scholarship entry.

The Program.

You must submit a plain text file with the source code of your program. PERL, Java, C#, Python, ANSI C++, ANSI C, and Visual Basic are acceptable languages. If you want to use another language then please contact us before submitting.

---

You have been asked to solve a problem for an old gameplayer. She has purchased a new game. It is a sort of Solitaire. This suits the old gameplayer as she has no friends so a game played alone is ideal. The game is played on a triangular grid. That is there are 7 rows of holes. The bottom row consists of just one hole and the top row of seven holes. Every hole has a red peg in it except the bottom hole. A move in this game consists of a red peg jumping over one of its neighbours into an empty hole beyond, and then removing the peg jumped over (like taking in draughts). In this game a peg has up to six neighbours. The diagram shows a stylised board with red squares indicating pegs. The black square indicates a missing peg. The six pegs which could jump into the vacant space (according to the rules) are marked with yellow circles. The idea is to make move after move until there is just one peg left. Ideally it should be in one of the three corners and best yet it should be in the bottom corner. However, as a good gameplayer she wants to generalise the game she's bought. She wants to know for which sizes of boards the game can be completed leaving just one peg standing. She also wants to know when the last remaining peg can be left in a corner, and when it can be left in the bottom corner. You are to write the program which gives her these answers.

 

---

Your Program

Your program should prompt for the size (number of rows, up to eight) of the board.

You should output one of the sentences:

• This game cannot be completed.
• This game can be completed but not with the last remaining peg in a corner.
• This game can be completed leaving a peg in a corner, but not in the bottom corner
• This game can be completed leaving the last peg in the bottom corner.

Elegance of programming will be a key grading criterion. Efficiency of the algorithm will also be important.