What is the quickest solution of the game Hi-Q (also called Solitaire)?

competition/games/hi-q Added material

Problem

What is the quickest solution of the game Hi-Q (also called Solitaire)?

For those of you who aren't sure what the game looks like:

32 movable pegs ("+") are arranged on the following board such that
only the middle position is empty ("-"). Just to be complete: the board
consists of only these 33 positions.

          1 2 3 4 5 6 7
        1     + + +
        2     + + +
        3 + + + + + + +
        4 + + + - + + +
        5 + + + + + + +
        6     + + +
        7     + + +

A piece moves on this board by jumping over one of its immediate
neighbor (horizontally or vertically) into an empty space opposite.
The peg that was jumped over, is hit and removed from the board.  A
move can contain multiple hits if you use the same peg to make the
hits.

You have to end with one peg exactly in the middle position (44).

Show solution

1:        46*44
2:        65*45
3:        57*55
4:        54*56
5:        52*54
6:        73*53
7:        43*63
8:        75*73*53
9:        35*55
10:        15*35
11:        23*43*63*65*45*25
12:        37*57*55*53
13:        31*33
14:        34*32
15:        51*31*33
16:        13*15*35
17:        36*34*32*52*54*34
18:        24*44

Found by Ernest Bergholt in 1912 and was proved to be minimal by John Beasley
in 1964.

see also entry "peg.solitaire"

References (out of print, unfortunately):
        The Ins and Outs of Peg Solitaire
        John D Beasley
        Oxford U press, 1985
        ISBN 0-19-853203-2

        Winning Ways, Vol. 2, Ch. 23
        Berlekamp, E.R.
        Academic Press, 1982
        ISBN 01-12-091102-7

Additional material

[ Editor: Winning Ways (vol. 2) solves the standard board by "packages"
and "purges", as excerpted on Alexander Bogomolny's Peg Solitaire page.
The figures are not reproduced; figure letters such as (a) are removed
below. ]

It's nice to be able to know the effect of a whole collection of moves
before you make them, so let us sell you some of our instant packages.
When a package is used to clear all the pegs from a region, we call it
a purge.

The Figure shows the handy little 3-purge, our most popular package.
When three pegs-the tail, the body and the head - are adjacent in line,
this will remove them all, provided the head has an additional peg on
one side of it, and an empty space on the other, as in the figure.
Move 1 of the package jumps the additional peg over the head; move 2
jumps tail over body into head; and move 3 jumps over the head, back to its original
position.  Since the peg and the space on either side of the head are
essential to the package, but are restored to their original state, we
call them the catalyst.

In most of the purges there are two catalyst moves in opposite
directions over the same position (which may be a peg or an empty
space) and the remaining moves form one or two packages which deliver
pegs to that place.  For the 3-purge, one peg was already in place and
the second is delivered by a single jump which we might call the
"2-package".  The 6-purge is usually accomplished using a 2-package to
deliver the first peg and a 4-package for the second.  The L-purge and
L-package are very useful indeed.  The first peg for the L-purge is
already in place and an L-package supplies the second.

[Editor: omitted here are the original's key to the figure symbols,
two sentences on the 2-purge and an alternative 6-purge catalyst that
refer only to the figure, and the line "Plenty of problems are
performed with panache by people who purchase our packages."]

Below we can see at a glance a solution to the Peg Solitaire,
consisting of two 3-purges (1 and 2) followed by three 6-purges (3,4
and 5) and an L-purge, leaving only for the final jump to be made.  You should check that every
purge has a catalyst it needs.

[ Editor: the diagrams showing where each purge is applied are not
reproduced here; see Winning Ways, vol. 2, ch. 23. ]

[ Editor: a pointer from a September 1998 thread, in reply to a request
for help with the 33-hole board and the central finish. ]

The following URL contains an excerpt from a book that gives a
thorough method to solving Hi-Q:

        http://www.cut-the-knot.com/proofs/pegsolitaire.html

The page also contains a java applet so you can try the solution method
on simpler puzzles with less starting pegs:
A cross of 6 pegs.
A plus of 9 pegs.
A block of 11 pegs.
32 pegs with the hole not in the center, and several others.
If you want a general method, and not just one optimal solution, it's
an excellent place to go.  IMO, the rest of the site is just as
interesting.

-- Ernest <Ernesto@above.ISP.is.correct> [Editor: address deliberately
   disguised in the original]