COSC 326
1-D Solitaire
One-dimensional solitaire is played on an infinite strip of ‘holes’ in which there are
initially some pegs. A move is a hop of one peg over another (adjacent) peg into a hole;
the peg that has been hopped over is removed. You win the game if you can remove all
pegs but one. Some games are winnable and some are not.
For instance, with 7 pegs (pegs denoted by •, and holes denoted by ◦)
◦ ◦ ◦ • • • ◦ • • • • ◦ ◦ ◦
can be won but
◦ ◦ ◦ • • • ◦ ◦ ◦ • • • • ◦ ◦ ◦
cannot.
Task
By hand work out the number of distinct winnable starting positions with 7 pegs. By
‘distinct’ we mean that we regard a position and its mirror image as being the same,
e.g. • • • ◦ • • • • is the same as • • • • ◦ • • •. Report on your methods and findings, and
list the winnable starting positions.
Then:
1. Write a program to find the number of distinct winnable starting positions with
20 pegs.
2. Print out the winnable starting positions in an easily understandable way.
Relates to Objectives
1.2 1.3 2.1 2.2 2.3 2.4 2.5 2.7 2.9 2.10 3.3 3.4 4.1 4.2 4.7 4.8
(2 points, Pair)
