PROBLEM STATEMENT
In the game of Peg Solitaire, you are given a arrangement of pegs that fit into
a line of equally-spaced holes. In order to win the game, you must reduce the
number of pegs to one, by using a series of jumps. Each jump occurs according
to the following rules:
- A peg may only jump over those immediately adjacent to it on the left or right.
- A jumping peg must jump exactly one other peg, no more, no less.
- Once the jump is completed, the peg that was jumped over is removed.
For example, given the configuration of pegs and holes
...1234.5....
where a period represents an empty hole, and where a digit represents a peg,
the legal moves are as follows:
...12..35.... [peg 3 jumped over peg 4, which was then removed]
or
..2..34.5.... [peg 2 jumped over peg 1, which was then removed]
These are the only two legal moves on that configuration.
A position is defined as "winnable" if, through a series of jumps, it can be
reduced to one peg. For example, the above position is winnable, since it can
be reduced to one peg by the following set of jumps:
...1234.5.... [initial]
...12..35.... [peg 3 jumped over peg 4]
.....1.35.... [peg 1 jumped over peg 2]
.....15...... [peg 5 jumped over peg 3]
....5........ [peg 5 jumped over peg 1]
Given a number N of pegs, write a method solutions in a class PegSolitaire that
returns the number of winnable positions that consist of N pegs.
DEFINITION
Class: PegSolitaire
Method: solutions
Parameter: int
Returns: int
Method signature (be sure your method is public): int solutions(int size);
NOTES
- When considering whether two positions are identical, disregard excess empty
holes on the left and right side.
- Note that there is no "edge" of the playing field; there are essentially
infinitely many empty holes.
TopCoder will ensure the validity of the input. An input is valid if the
following criterion is met:
- size will be an integer between 2 and 35, inclusive
Test cases:
Input: 2
Output: 1
There is only one winnable case with 2 pegs; when they are adjacent.
Input: 4
Output: 3
The patterns containing 4 pegs are
..12.3.4..
..12..34..
..1.2.34..
Input: 8
Output: 23