Problem Description
Place a coin on any unoccupied star point connected to
another unoccupied star point and move it to the other end. Can you do
this 6 more times so that 7 of the star points are occupied?
Source: The Master Book of Mathematical Recreations, Fred
Schuh, Dover Pubs., 1968
Background & Techniques
Dec 17,2001 Addendum: Posted a revised
version today that allows user play  and mildly insults you when you lose!
If you want the program and are not interested in the
program logic, just scroll down to the bottom of the page to
download the executable.
This program could be solved by the "bruteforce"
method, trying all possible configurations since there are only 7X6X5X4X3X2
(7!) possible arrangements. What I call bruteforce, real mathematicians call
"exhaustive search".
However in this case, as in the Knight's Tour puzzle, there is a
selection rule that can "prune" the search tree. In fact, this
rule is probably provable  strong enough that we don't have to worry about
backtracking or retracting bad choices. The rule is to select the unoccupied
star point (vertex) with the fewest free lines
coming into it, where a free line is defined as a line with no coin at
either end.
The first problem is internally representing the
graph. I decided to create a TVertex record for each star point containing it's
display coordinates, whether or not it is occupied, and the number of free lines
coming into that vertex. An array, Vertex, containing 8 of
these records describes the vertices. A second doubly dimensioned array, Lines, contains 8 X2 entries  each of the
eight
1st level indices represents a line and the two 2nd level entries contain the indices of the
endpoint vertices. An alternative, and probably better, structure would have each vertex record contain the indices of the two
vertices at the other ends of the lines emanating from it. (e.g. the first
vertex entry would contain the integers 4 and 6 indicating the connected
points). Implementing this change would simplify the code, but
is left as an exercise for you guys.
(Addendum:(Dec. 17, 2001): In
the course of modifying the program to allow user play, I implemented the
above change. So the Lines array no longer exists, but fields C1
and C2 in each Vertex record contain the index values of the
two connected points. This also eliminated the need for the freelines
variable described below. C1 and C2 point directly to the
connecting line ends, so it's an easy matter to see if they are occupied.)
I created a TCoinBoard object, descended from TPaintbox, to
contain board information. The Paint method redraws the board
from Vertex and Lines information as required. There were a couple of
interesting subproblems in implementing Seven Coins. How do we determine the
number of free lines coming into a vertex? I solved this by initializing
the freelines variable to 2 for each vertex, then finding and reducing freelines
each time a coin was placed, both for the vertex containing the new coin and
those connected to it (if they are unoccupied) .
In order to generate the vertex locations, we divide the 2Pi
radians in a circle by 8 to get the angular displacement from vertex to
vertex, then further rotate the first point by 1/16 of a circle. The
radius is set at some fraction
The other interesting problem was placing the coin. I
decided to animate the placement by displaying the new coin at the center of a free
line and moving it to the vertex location. A TShape defined as a
circle is a simple way to do
this, however I learned that a cannot be the parent of a
control. There are good reasons for this, Windows manages it's real
windows including all Delphi components descended from TWinControl. Since
there are a limited number of of Windows resources available, Delphi has another class,
TGraphicControl, for visual components that require a canvas but not other
window properties.
To make a long story short, by making TCoinBoard the parent of the Coin
TShape, it will automatically be released when TCoinBoard is
freed.
Running/Exploring the Program
Suggestions for further exploration

Make the changes
in data structure described in the Techniques section above. I.E.
eliminate the Lines array entirely and add index values pointing to the 2
adjacent vertices to each TVertex record. (Done
12/17/01) 

Add the ability
accept user moves. TPaintbox (and therefore the TCoinBoard descendant) has an Onclick event exit. The
biggest problem would be to determine if the click was on or near a
vertex. If so, I would set the occupied field to false if it were true
(don't forget to increase the freelines count for the clicked vertex
and for the unoccupied ones that are connected to it.) If the
clicked vertex is unoccupied, we would have to determine if a line to it is free,
then mark it as occupied and decrease the freelines field for it and the
vertices that are connected to it. (Done
12/1701) 
