Resolva o quebra-cabeça de 14 pinos

Introdução

Um quebra-cabeça comum envolve uma placa triangular com 15 furos para tees / pegs, conforme mostrado na imagem abaixo:

Começando com todos os pinos no tabuleiro, com exceção de um buraco no topo, o objetivo do quebra-cabeça é pular pinos uns sobre os outros como damas, de modo a deixar exatamente um pino à esquerda. O único movimento válido é pular uma estaca sobre uma estaca adjacente em qualquer direção para um buraco vazio. O pino que foi pulado é então removido do tabuleiro. O jogo termina quando não houver jogadas válidas.

Spec

Seu trabalho é escrever um programa que encontre uma solução completa para o quebra-cabeça do pino, ou seja, um que deixe exatamente um pino à esquerda. Existem várias soluções possíveis, portanto, seu programa só precisa imprimir uma.

• Seu programa não receberá nenhuma entrada. Você não tem permissão para ler dados de nenhuma fonte externa.
• Imprima a lista de 13 movimentos que resultam em 1 peg restante usando este formato:

  Peg 1 jumps Peg 3 to Hole 6.

• Os furos / pinos são numerados de cima para baixo, da esquerda para a direita, de modo que o pino / furo superior seja 1, numerando até o canto inferior direito ser 15.
• Seu programa deve encontrar a solução em tempo de execução . Imprimir uma solução diretamente por qualquer outro meio que não seja resolvê-la no programa é uma desqualificação automática.
• Bônus : receba 10 pontos de bônus se puder gerar várias soluções exclusivas (basta imprimir separadas por linhas em branco).
• Bônus : receba 5 pontos de bônus se o número 15não aparecer em nenhum lugar no seu código-fonte.

Pontuação

Isso é código-golfe, então a solução mais curta (por contagem de bytes) que imprime uma resposta correta será a vencedora. Os pontos de bônus são subtraídos da sua contagem total de bytes. Forneça uma amostra de saída da execução do seu programa, bem como um link para ideonealgum site semelhante, se possível, demonstrando a execução do seu programa.

Ruby, pontuação 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]

Uma implementação simples de ruby ​​que imprime todas as soluções possíveis para esse quebra-cabeça (leva menos de um minuto no meu computador). As primeiras linhas de saída podem ser vistas aqui:

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.
...

E o exemplo online pode ser encontrado aqui .

Python, 324 caracteres, pontuação = 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]

O estado do peg é mantido como uma máscara de bits. Mcontém uma lista de estados de peg e as instruções para chegar a esse estado.

Eu também conseguia imprimir todas as soluções (existem 29760), mas custaria mais de 10 caracteres para fazê-lo.

Não posso publicá-lo no ideone, pois leva cerca de 90 segundos para ser executado.

Resultado:

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.

C, 386 caracteres, pontuação = 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]]);}

Imprime todas as soluções 29760, em menos de um segundo.

Esta versão assume (entre outras coisas) que o compilador permitirá a declaração implícita de printf (). Cerca de seis outros caracteres podem ser salvos usando o implit-int, mas esse recurso foi tecnicamente removido do C99.

Além disso, mais quatro bytes podem ser salvos substituindo as letras maiúsculas nas duas seqüências pelos caracteres de controle correspondentes. Não fiz isso aqui porque os compiladores não precisam permitir essas seqüências e isso torna o código-fonte já denso completamente ilegível.

Para maior clareza, eis o mesmo algoritmo sem as otimizações de tamanho mais ofuscantes:

#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 e t são a lista de saltos legais inicializados no primeiro loop. re formam a história que o programa usa para voltar atrás e explorar todos os jogos possíveis.

Tenho certeza que isso pode ser melhorado!