Peg Solitaire , Solo Noble , Solo Goli , Marble Solitaire o simplemente Solitaire es un juego de mesa para un jugador que implica el movimiento de clavijas en un tablero con agujeros. Algunos juegos usan canicas en un tablero con muescas. El juego se conoce como solitario en Gran Bretaña y como solitario peg en los EE. UU., donde "solitario" es ahora el nombre común para la paciencia .
Los primeros testimonios del juego se remontan a la corte de Luis XIV , y la fecha concreta de 1697, con un grabado realizado diez años más tarde por Claude Auguste Berey de Anne de Rohan-Chabot , princesa de Soubise, con el rompecabezas de su lado. La edición de agosto de 1697 de la revista literaria francesa Mercure galant contiene una descripción del tablero, reglas y problemas de muestra. Esta es la primera referencia impresa conocida del juego.
El juego estándar llena todo el tablero con clavijas excepto el agujero central. El objetivo es, realizando movimientos válidos, vaciar todo el tablero excepto una solitaria clavija en el agujero central.
Hay dos tableros tradicionales ('.' como clavija inicial, 'o' como agujero inicial):
Un movimiento válido es saltar una clavija ortogonalmente sobre una clavija adyacente en un agujero a dos posiciones de distancia y luego retirar la clavija saltada.
En los diagramas siguientes, ·indica una clavija en un agujero, *en negrita indica la clavija que se va a mover e oindica un agujero vacío. Un azul ¤es el agujero desde el que se movió la clavija actual; un rojo *es la posición final de esa clavija, un rojo oes el agujero de la clavija que se saltó y se quitó.
Por tanto, los movimientos válidos en cada una de las cuatro direcciones ortogonales son:
* · o → ¤ o * Saltar a la derecha
o · * → * o ¤ Saltar a la izquierda
* ¤ · → o Saltar hacia abajo o *
o * · → o Saltar hacia arriba * ¤
En un tablero inglés, los primeros tres movimientos podrían ser:
· · · · · · · · · · · · · · * · · ¤ · · o · · * ·· · · · · · · · · · o · · · · ¤ o * · · · · oo o · · ·· · · o · · · · · · * · · · · · · · · · · · · · ¤ · · ·· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Hay muchas soluciones diferentes al problema estándar, y una notación utilizada para describirlas asigna letras a los agujeros (aunque también se pueden usar números):
inglés europeo abcabc defydefzghijklmghijklmnopx PON nopx PONMLKJIHGMLKJIHG FEDZFEDY CBACBA
Esta notación de imagen especular se utiliza, entre otras razones, porque en el tablero europeo, un conjunto de juegos alternativos consiste en comenzar con un agujero en alguna posición y terminar con una sola clavija en su posición reflejada. En el tablero inglés, los juegos alternativos equivalentes son comenzar con un agujero y terminar con una clavija en la misma posición.
No hay solución para el tablero europeo con el agujero inicial situado en el centro, si sólo se permiten movimientos ortogonales. Esto se ve fácilmente de la siguiente manera, mediante un argumento de Hans Zantema . Divida las posiciones del tablero en posiciones A, B y C de la siguiente manera:
A B C ABCABABCABCABCABCABCABCABC BCABC A B C
Inicialmente, con sólo la posición central libre, el número de posiciones A cubiertas es 12, el número de posiciones B cubiertas es 12 y también el número de posiciones C cubiertas es 12. Después de cada movimiento, el número de posiciones A cubiertas aumenta o disminuye en uno, y lo mismo para el número de puestos B cubiertos y el número de puestos C cubiertos. Por lo tanto, después de un número par de movimientos, todos estos tres números son pares, y después de un número impar de movimientos, todos estos tres números son impares. Por lo tanto, no se puede alcanzar una posición final con una sola clavija, ya que eso requeriría que uno de estos números sea uno (la posición de la clavija, uno es impar), mientras que los otros dos números sean cero, por lo tanto, pares.
Sin embargo, existen otras configuraciones en las que un único orificio inicial puede reducirse a una única clavija.
Una táctica que se puede utilizar es dividir el tablero en paquetes de tres y purgarlos (eliminarlos) por completo usando una clavija adicional, el catalizador, que salta y luego vuelve a saltar . En el siguiente ejemplo, el * es el catalizador:
* · o ¤ o * o * · * o ¤ · → · → o → o · · ¤o
Esta técnica se puede utilizar con una línea de 3, un bloque de 2·3 y una forma de L de 6 clavijas con una base de longitud 3 y un montante de longitud 4.
Otros juegos alternativos incluyen comenzar con dos agujeros vacíos y terminar con dos clavijas en esos agujeros. También comenzando con un agujero aquí y terminando con una clavija allí . En un tablero inglés, el agujero puede estar en cualquier lugar y la clavija final sólo puede terminar donde lo permitan múltiplos de tres. Por lo tanto , un agujero en a sólo puede dejar una clavija en a , p , O o C.
Se conoce un análisis exhaustivo del juego. [1] Este análisis introdujo una noción llamada función pagoda , que es una potente herramienta para mostrar la inviabilidad de un problema dado, generalizado, del solitario peg.
Una solución para encontrar una función pagoda, que demuestre la inviabilidad de un problema dado, se formula como un problema de programación lineal y se puede resolver en tiempo polinómico. [2]
Un artículo de 1990 abordó los problemas generalizados de Hi-Q que son equivalentes a los problemas del solitario peg y mostró su completitud NP . [3]
Un artículo de 1996 formuló un problema de solitario de clavija como un problema de optimización combinatoria y discutió las propiedades de la región factible llamada "un cono de solitario". [4]
En 1999, el solitario peg se resolvió completamente en ordenador mediante una búsqueda exhaustiva de todas las variantes posibles. Se logró haciendo uso de las simetrías, el almacenamiento eficiente de constelaciones de tableros y el hash. [5]
En 2001 se desarrolló un método eficaz para resolver problemas de solitario peg. [2]
Un estudio inédito de 1989 sobre una versión generalizada del juego en el tablero inglés mostró que cada problema posible en el juego generalizado tiene 2 9 posibles soluciones distintas, excluyendo las simetrías, ya que el tablero inglés contiene 9 subcuadros distintos de 3 × 3. Una consecuencia de este análisis es poner un límite inferior al tamaño de posibles problemas de "posición invertida", en los que las celdas inicialmente ocupadas quedan vacías y viceversa. Cualquier solución a tal problema debe contener un mínimo de 11 movimientos, independientemente de los detalles exactos del problema.
Se puede demostrar mediante álgebra abstracta que sólo hay cinco posiciones fijas del tablero en las que el juego puede terminar con éxito con una clavija. [6]
La solución más corta al juego inglés estándar implica 18 movimientos, contando los saltos múltiples como movimientos únicos:
Esta solución fue encontrada en 1912 por Ernest Bergholt y John Beasley demostró que era la más corta posible en 1964. [7]
Esta solución también se puede ver en una página que también presenta la notación Wolstenholme, que está diseñada para facilitar la memorización de la solución.
Otras soluciones incluyen la siguiente lista. En estos, la notación utilizada es
x:x=ex,lj,ck,Pf,DP,GI,JH,mG,GI,ik,gi,LJ,JH,Hl,lj,jh,CK,pF,AC,CK,Mg,gi,ac, ck,kI,dp,pF,FD,DP,Pp,ox x:x=ex,lj,xe/hj,Ki,jh/ai,ca,fd,hj,ai,jh/MK,gM,hL,Fp,MK,pF/CK,DF,AC,JL,CK, LJ/PD, GI, mG, JH, GI, DP/Ox j:j=lj,Ik,jl/hj,Ki,jh/mk,Gm,Hl,fP,mk,Pf/ai,ca,fd,hj,ai,jh/MK,gM,hL,Fp,MK, pF/CK,DF,AC,JL,CK,LJ/Jj i:i=ki,Jj,ik/lj,Ik,jl/AI,FD,CA,HJ,AI,JH/mk,Hl,Gm,fP,mk,Pf/ai,ca,fd,hj,ai, jh/gi,Mg,Lh,pd,gi,dp/Ki e:e=xe/lj,Ik,jl/ck,ac,df,lj,ck,jl/GI,lH,mG,DP,GI,PD/AI,FD,CA,JH,AI,HJ/pF, MK,gM,JL,MK,Fp/hj,ox,xe d:d=fd,xe,df/lj,ck,ac,Pf,ck,jl/DP,KI,PD/GI,lH,mG,DP,GI,PD/CK,DF,AC,LJ,CK, JL/MK,gM,hL,pF,MK,Fp/pd b:b=jb,lj/ck,ac,Pf,ck/DP,GI,mG,JH,GI,PD/LJ,CK,JL/MK,gM,hL,pF,MK,Fp/xo,dp, buey/xe/AI/BJ,JH,Hl,lj,jb b:x=jb,lj/ck,ac,Pf,ck/DP,GI,mG,JH,GI,PD/LJ,CK,JL/MK,gM,hL,pF,MK,Fp/xo,dp, buey/xe/AI/BJ,JH,Hl,lj,ex a:a=ca,jb,ac/lj,ck,jl/Ik,pP,KI,lj,Ik,jl/GI,lH,mG,DP,GI,PD/CK,DF,AC,LJ,CK, JL/dp,gi,pd,Mg,Lh,gi/ia a:p=ca,jb,ac/lj,ck,jl/Ik,pP,KI,lj,Ik,jl/GI,lH,mG,DP,GI,PD/CK,DF,AC,LJ,CK, JL/dp,gi,pd,Mg,Lh,gi/dp
El único lugar donde es posible terminar con una clavija solitaria es el centro o la mitad de uno de los bordes; En el último salto siempre habrá la opción de elegir si terminar en el centro o en el borde.
A continuación se muestra una tabla sobre el número ( Posibles posiciones del tablero ) de posibles posiciones del tablero después de n saltos , y la posibilidad de que la misma clavija se mueva para realizar un salto adicional ( N o F urther Jumps ). Es interesante señalar que la forma más corta de fallar el juego es en seis movimientos, y la solución (además de sus rotaciones y reflejos) es única. Un ejemplo de esto es el siguiente: 4 → 16; 23 → 9; 14 → 16; 17 → 15; 19 → 17; 31 → 23. (En esta notación, las clavijas están numeradas de izquierda a derecha, comenzando con 0 y bajando en cada fila y hacia el extremo izquierdo una vez marcada cada fila).
NOTA: Si una posición del tablero se puede girar y/o voltear a otra posición del tablero, las posiciones del tablero se cuentan como idénticas.
Como sólo puede haber 31 saltos, los ordenadores modernos pueden examinar fácilmente todas las posiciones del juego en un tiempo razonable. [8]
La secuencia anterior "PBP" se ingresó como A112737 en OEIS . Tenga en cuenta que el número total de posiciones del tablero alcanzables (suma de la secuencia) es 23.475.688, mientras que el número total de posiciones posibles del tablero es 8.589.934.590 (33 bits-1) (2^33), por lo que solo alrededor del 2,2% de todas las posiciones posibles del tablero pueden llegar a partir del centro vacante.
También es posible generar todas las posiciones del tablero. Los resultados a continuación se obtuvieron utilizando el conjunto de herramientas mcrl2 (consulte el ejemplo de peg_solitaire en la distribución).
En los resultados a continuación, ha generado todas las posiciones del tablero que realmente alcanzó, comenzando con el centro vacante y terminando en el hoyo central.
Hay 3 posiciones iniciales no congruentes que tienen solución. [9] Estos son:
1)
0 1 2 3 4 5 6 0·· 1 · · · · · 2 · · · · · · · 3 · · · · · · · 4 · · · · · · · 5 · · · · · 6 · · ·
Posible solución: [2:2-0:2, 2:0-2:2, 1:4-1:2, 3:4-1:4, 3:2-3:4, 2:3-2: 1, 5:3-3:3, 3:0-3:2, 5:1-3:1, 4:5-4:3, 5:5-5:3, 0:4-2:4, 2:1-4:1, 2:4-4:4, 5:2-5:4, 3:6-3:4, 1:1-1:3, 2:6-2:4, 0: 3-2:3, 3:2-5:2, 3:4-3:2, 6:2-4:2, 3:2-5:2, 4:0-4:2, 4:3- 4:1, 6:4-6:2, 6:2-4:2, 4:1-4:3, 4:3-4:5, 4:6-4:4, 5:4-3: 4, 3:4-1:4, 1:5-1:3, 2:3-0:3, 0:2-0:4]
2)
0 1 2 3 4 5 6 0 · · · 1 · · o · · 2 · · · · · · · 3 · · · · · · · 4 · · · · · · · 5 · · · · · 6 · · ·
Posible solución: [1:1-1:3, 3:2-1:2, 3:4-3:2, 1:4-3:4, 5:3-3:3, 4:1-4: 3, 2:1-4:1, 2:6-2:4, 4:4-4:2, 3:4-1:4, 3:2-3:4, 5:1-3:1, 4:6-2:6, 3:0-3:2, 4:5-2:5, 0:2-2:2, 2:6-2:4, 6:4-4:4, 3: 4-5:4, 2:3-2:1, 2:0-2:2, 1:4-3:4, 5:5-5:3, 6:3-4:3, 4:3- 4:1, 6:2-4:2, 3:2-5:2, 4:0-4:2, 5:2-3:2, 3:2-1:2, 1:2-1: 4, 0:4-2:4, 3:4-1:4, 1:5-1:3, 0:3-2:3]
y 3)
0 1 2 3 4 5 6 0 · · · 1 · · · · · 2 · · · o · · · 3 · · · · · · · 4 · · · · · · · 5 · · · · · 6 · · ·
Posible solución: [2:1-2:3, 0:2-2:2, 4:1-2:1, 4:3-4:1, 2:3-4:3, 1:4-1: 2, 2:1-2:3, 0:4-0:2, 4:4-4:2, 3:4-1:4, 6:3-4:3, 1:1-1:3, 4:6-4:4, 5:1-3:1, 2:6-2:4, 1:4-1:2, 0:2-2:2, 3:6-3:4, 4: 3-4:1, 6:2-4:2, 2:3-2:1, 4:1-4:3, 5:5-5:3, 2:0-2:2, 2:2- 4:2, 3:4-5:4, 4:3-4:1, 3:0-3:2, 6:4-4:4, 4:0-4:2, 3:2-5: 2, 5:2-5:4, 5:4-3:4, 3:4-1:4, 1:5-1:3]
El solitario Peg se ha jugado en tableros de otros tamaños, aunque los dos mencionados anteriormente son los más populares. También se ha jugado en un tablero triangular, permitiéndose saltos en las 3 direcciones. Siempre que la variante tenga la "paridad" adecuada y sea lo suficientemente grande, probablemente tendrá solución.
Una variante triangular común tiene cinco clavijas en un lado. Una solución en la que la clavija final llegue al agujero vacío inicial no es posible para un agujero en una de las tres posiciones centrales. Una configuración de hoyo de esquina vacío se puede resolver en diez movimientos, y una configuración de hoyo medio vacío en nueve (Bell 2008):
El 26 de junio de 1992 se lanzó un videojuego basado en el solitario peg para Game Boy. Titulado simplemente Solitario , el juego fue desarrollado por Hect. En Norteamérica, DTMC lanzó el juego como Lazlos' Leap .
Cracker Barrel presenta el juego en cada mesa en sus ubicaciones. El tablero presentado es triangular con 15 agujeros en total.
En Cowboy Bebop: The Movie , el principal antagonista, Vincent Volaju, pasa la mayor parte de su tiempo libre jugando al solitario peg. El vector de su planeado ataque bioterrorista , un tipo de nanobot , se almacena en canicas de solitario.
Implementación del cálculo de fuerza bruta del juego de solitario Peg
