Solve the 14-Pegs puzzle

Question

Introduction

A common puzzle involves a triangular board with 15 holes for tees/pegs as shown in the image below:

Starting with all the pegs in the board except for a hole at the top, the point of the puzzle is to jump pegs over one another like checkers in such a way to leave exactly one peg left. The only valid move is to jump one peg over an adjacent peg in any direction into an empty hole. The peg that was jumped is then removed from the board. Play finishes when there remain no valid moves.

Spec

Your job is to write a program that can find a complete solution to the peg puzzle, i.e., one that leaves exactly one peg left. There are multiple possible solutions, so your program just needs to print one.

• Your program will receive no input. You are not allowed to read data from any outside source.
• Print out the list of 13 moves that gives a result of 1 peg remaining using this format:

  Peg 1 jumps Peg 3 to Hole 6.

• The holes/pegs are numbered from top to bottom, left to right, so that the top peg/hole is 1, numbering until the bottom-right is 15.
• Your program must find the solution at runtime. Printing out a solution directly by any means other than solving it in the program is an automatic disqualification.
• Bonus: receive 10 bonus points if you can output multiple unique solutions (can just print separated by blank lines).
• Bonus: receive 5 bonus points if the number 15 appears nowhere in your source code.

Scoring

This is code-golf, so the shortest solution (by byte count) that prints out a correct answer will be the winner. Bonus points are subtracted from your total byte count. Please provide a sample output of running your program as well as a link to ideone or some similar site if possible demonstrating the execution of your program.

Answer 1

Ruby, score 240 238 234 = 249 - 10 - 5

s=->t,r,c{c>0?(t+t.reverse).gsub(/[A-O]{2}[a-o]/){|j|s[t.tr(j,j.swapcase),r+"Peg #{j[0].ord-64} jumps Peg #{j[1].ord-64} to Hole #{j[2].ord-96}.\n",c-1]}:$><<r+"\n"}
s["aBD,BDG,DGK,CEH,EHL,FIM,aCF,CFJ,FJO,BEI,EIN,DHM,DEF,GHI,HIJ,KLM,LMN,MNO,","",13]

A plain ruby implementation which prints all possible solutions to this puzzle (takes less than a minute on my computer). The first lines of output can be seen here:

Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 7 jumps Peg 8 to Hole 9.
Peg 12 jumps Peg 13 to Hole 14.
Peg 10 jumps Peg 6 to Hole 3.
Peg 4 jumps Peg 5 to Hole 6.
Peg 3 jumps Peg 6 to Hole 10.
Peg 15 jumps Peg 10 to Hole 6.
Peg 6 jumps Peg 9 to Hole 13.
Peg 14 jumps Peg 13 to Hole 12.
Peg 11 jumps Peg 12 to Hole 13.

Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 7 jumps Peg 8 to Hole 9.
...

And the online example can be found here.

Answer 2

Python, 324 chars, score = 319

f=0xf
x=0x12413624725935836a45647b48d58c59e69d6af78989abcdcdedef
Z=[(x>>12*i&f,x>>12*i+4&f,x>>12*i+8&f)for i in range(18)]
M=[[65532,'']]
for i in' '*13:
 Q=[]
 for p,m in M:
  for a,b,c in[x[::-1]for x in Z]+Z:
   if p>>a&p>>b&~p>>c&1:Q+=[[p^2**a^2**b^2**c,m+"Peg %d jumps Peg %d to Hole %d.\n"%(a,b,c)]]
 M=Q
print M[0][1]

The peg state is kept as a bitmask. M contains a list of peg states and the instructions to get to that state.

I could make it print out all of the solutions as well (there are 29760 of them), but it would cost more than 10 characters to do it.

I can't post it on ideone as it takes about 90 seconds to run.

Output:

Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 12 jumps Peg 13 to Hole 14.
Peg 7 jumps Peg 8 to Hole 9.
Peg 10 jumps Peg 6 to Hole 3.
Peg 4 jumps Peg 5 to Hole 6.
Peg 3 jumps Peg 6 to Hole 10.
Peg 15 jumps Peg 10 to Hole 6.
Peg 6 jumps Peg 9 to Hole 13.
Peg 14 jumps Peg 13 to Hole 12.
Peg 11 jumps Peg 12 to Hole 13.

Answer 3

C, 386 chars, score = 371

int f[37],o[36],t[36],r[14],i[14],m=1,s=~3,j=18;main(){while(j--)o[j]=o[18+j]=(f[j]=t[18+j]="AABBCCDDDEEFFGHKLM"[j]-64)+(t[j]=f[18+j]="DFGIHJKMFLNMOIJMNO"[j]-64)>>1;while(m)if(!f[++j])s=r[--m],j=i[m];else if(s>>f[j]&s>>o[j]&~s>>t[j]&1)if(r[m]=s,s^=1<<f[j]|1<<o[j]|1<<t[i[m]=j],j=-1,++m>13)for(m=printf("\n");m<14;++m)printf("Peg %d jumps Peg %d to Hole %d.\n",f[i[m]],o[i[m]],t[i[m]]);}

Prints out all 29760 solutions, in well under a second.

This version assumes (among other things) that the compiler will permit the implicit declaration of printf(). About six more characters could be saved by making use of implicit-int, but that feature was technically removed from C99.

Also, four more bytes can be saved by replacing the capital letters in the two strings with the corresponding control characters. I didn't do that here because compilers aren't required to permit such strings, and it makes already-dense source code completely illegible.

For clarity, here's the same algorithm without the more obfuscatory size-optimizations:

#include <stdio.h>
int f[37], o[36], t[36], r[14], i[14], m, j, s = ~3;
int main(void)
{
    for (j = 0 ; j < 18 ; ++j) {
        f[j] = t[18+j] = "AABBCCDDDEEFFGHKLM"[j] - 64;
        t[j] = f[18+j] = "DFGIHJKMFLNMOIJMNO"[j] - 64;
        o[j] = o[18+j] = (f[j] + t[j]) >> 1;
    }
    j = 0;
    for (m = 1 ; m ; ++j) {
        if (!f[j]) {
            --m;
            s = r[m];
            j = i[m];
        } else if ((s >> f[j]) & (s >> o[j]) & (~s >> t[j]) & 1) {
            r[m] = s;
            i[m] = j;
            s ^= (1 << f[j]) | (1 << o[j]) | (1 << t[j]);
            j = -1;
            ++m;
            if (m > 13) {
                printf("\n");
                for (m = 1 ; m < 14 ; ++m)
                    printf("Peg %d jumps Peg %d to Hole %d.\n",
                           f[i[m]], o[i[m]], t[i[m]]);
            }
        }
    }
    return 0;
}

f, o, and t are the list of legal jumps initialized in the first loop. r and i form the history that the program uses to backtrack and explore all possible games.

I'm sure this can be improved!