Resuelve el rompecabezas de 14 clavijas

Introducción

Un rompecabezas común consiste en un tablero triangular con 15 agujeros para tees / clavijas como se muestra en la imagen a continuación:

Comenzando con todas las clavijas en el tablero, excepto por un agujero en la parte superior, el objetivo del rompecabezas es saltar las clavijas una sobre la otra como fichas, de tal manera que quede exactamente una clavija a la izquierda. El único movimiento válido es saltar una clavija sobre una clavija adyacente en cualquier dirección hacia un agujero vacío. La clavija que se saltó se retira del tablero. El juego termina cuando no quedan movimientos válidos.

Especificaciones

Su trabajo es escribir un programa que pueda encontrar una solución completa para el rompecabezas de clavijas, es decir, una que deje exactamente una clavija restante. Existen múltiples soluciones posibles, por lo que su programa solo necesita imprimir una.

• Su programa no recibirá ninguna entrada. No tiene permiso para leer datos de ninguna fuente externa.
• Imprima la lista de 13 movimientos que dan el resultado de 1 clavija restante usando este formato:

  Peg 1 jumps Peg 3 to Hole 6.

• Los agujeros / clavijas están numerados de arriba a abajo, de izquierda a derecha, de modo que la clavija / agujero superior sea 1, numerando hasta que la esquina inferior derecha sea 15.
• Su programa debe encontrar la solución en tiempo de ejecución . Imprimir una solución directamente por cualquier otro medio que no sea resolverla en el programa es una descalificación automática.
• Bonificación : reciba 10 puntos de bonificación si puede generar múltiples soluciones únicas (solo puede imprimir separadas por líneas en blanco).
• Bonificación : recibe 5 puntos de bonificación si el número 15no aparece en ninguna parte de tu código fuente.

Puntuación

Este es el código de golf, por lo que la solución más corta (por byte) que imprima una respuesta correcta será la ganadora. Los puntos de bonificación se restan de su recuento total de bytes. Proporcione una salida de muestra para ejecutar su programa, así como un enlace ideoneo algún sitio similar si es posible, demostrando la ejecución de su programa.

Ruby, anotar 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]

Una implementación simple de ruby ​​que imprime todas las soluciones posibles para este rompecabezas (toma menos de un minuto en mi computadora). Las primeras líneas de salida se pueden ver aquí:

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

Y el ejemplo en línea se puede encontrar aquí .

Python, 324 caracteres, puntuación = 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]

El estado de clavija se mantiene como una máscara de bits. Mcontiene una lista de estados de clavijas y las instrucciones para llegar a ese estado.

Podría hacer que imprima todas las soluciones también (hay 29760 de ellas), pero costaría más de 10 caracteres hacerlo.

No puedo publicarlo en ideone ya que tarda unos 90 segundos en ejecutarse.

Salida:

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, puntaje = 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 las soluciones 29760, en menos de un segundo.

Esta versión supone (entre otras cosas) que el compilador permitirá la declaración implícita de printf (). Se podrían guardar unos seis caracteres más utilizando implícita-int, pero esa característica se eliminó técnicamente de C99.

Además, se pueden guardar cuatro bytes más reemplazando las letras mayúsculas en las dos cadenas con los caracteres de control correspondientes. No hice eso aquí porque los compiladores no están obligados a permitir tales cadenas, y hace que el código fuente ya denso sea completamente ilegible.

Para mayor claridad, aquí está el mismo algoritmo sin las optimizaciones de tamaño más ofuscadoras:

#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, yt son la lista de saltos legales inicializados en el primer bucle. R y yo formamos el historial que el programa utiliza para dar marcha atrás y explorar todos los juegos posibles.

Estoy seguro de que esto se puede mejorar!