Peg Solitaire , Solo Noble , Solo Goli , Marble Solitaire o simplemente Solitaire es un juego de mesa para un jugador que implica el movimiento de fichas en un tablero con agujeros. Algunos juegos utilizan canicas en un tablero con hendiduras. El juego se conoce como solitario en Gran Bretaña y como peg solitaire en los EE. UU., donde "solitario" es ahora el nombre común para la paciencia .
La primera evidencia del juego se remonta a la corte de Luis XIV y la fecha específica de 1697, con un grabado realizado diez años después por Claude Auguste Berey de Anne de Rohan-Chabot , princesa de Soubise, con el rompecabezas a su lado. La edición de agosto de 1697 de la revista literaria francesa Mercure galant contiene una descripción del tablero, las reglas y problemas de muestra. Esta es la primera referencia conocida al juego impresa.
El juego estándar llena todo el tablero con fichas, excepto el agujero central. El objetivo es, realizando movimientos válidos, vaciar todo el tablero, excepto una ficha solitaria en el agujero central.
Hay dos tableros tradicionales ('.' como clavija inicial, 'o' como agujero inicial):
Un movimiento válido es hacer saltar una clavija ortogonalmente sobre una clavija adyacente hasta un agujero situado dos posiciones más allá y luego retirar la clavija saltada.
En los diagramas que siguen, ·indica una clavija en un agujero, *en negrita indica la clavija que se va a mover y en rojo oindica un agujero vacío. El azul ¤es el agujero del que se movió la clavija actual; el rojo *es la posición final de esa clavija; el rojo oes el agujero de la clavija que se saltó y se eliminó.
Por lo 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 arriba * ¤
En un tablero inglés, los tres primeros 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 abccabc desafiar a defzghijklmghijklmnopx PON nopx PONMLKJIHGMLKJIHG FEDERACIÓN FEDERAL CBAACBA
Esta notación de imagen especular se utiliza, entre otras razones, porque en el tablero europeo, una serie de juegos alternativos consiste en empezar con un agujero en una posición determinada y terminar con una sola clavija en su posición reflejada. En el tablero inglés, los juegos alternativos equivalentes consisten en empezar 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:
abecedario ABCABABCABCABCABCABC BCABC abecedario
Inicialmente, con solo 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 ocurre con el número de posiciones B cubiertas y el número de posiciones C cubiertas. 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 llegar a 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 son cero, es decir, 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 utilizando una clavija adicional, el catalizador, que salta y luego vuelve a saltar . En el ejemplo siguiente, 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 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 comenzar con un agujero aquí y terminar con una clavija allí . En un tablero inglés, el agujero puede estar en cualquier lugar y la clavija final solo puede terminar donde lo permitan los múltiplos de tres. Por lo tanto, un agujero en a solo puede dejar una única 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 herramienta poderosa para mostrar la inviabilidad de un problema de solitario de clavijas generalizado dado.
Una solución para encontrar una función pagoda, que demuestra la inviabilidad de un problema dado, se formula como un problema de programación lineal y se puede resolver en tiempo polinomial. [2]
Un artículo de 1990 abordó los problemas Hi-Q generalizados que son equivalentes a los problemas de solitario de clavijas y mostró su NP-completitud . [3]
Un artículo de 1996 formuló un problema de solitario de clavijas como un problema de optimización combinatoria y analizó las propiedades de la región factible denominada "cono solitario". [4]
En 1999, el solitario de clavijas se resolvió completamente en un ordenador mediante una búsqueda exhaustiva entre todas las variantes posibles. Se logró haciendo uso de las simetrías, el almacenamiento eficiente de las constelaciones del tablero y el hashing. [5]
En 2001 se desarrolló un método eficiente para resolver problemas de solitario de clavijas. [2]
Un estudio inédito de 1989 sobre una versión generalizada del juego en el tablero inglés mostró que cada posible problema en el juego generalizado tiene 2 9 posibles soluciones distintas, excluyendo las simetrías, ya que el tablero inglés contiene 9 subcuadrados distintos de 3 × 3. Una consecuencia de este análisis es poner un límite inferior al tamaño de los posibles problemas de "posición invertida", en los que las celdas ocupadas inicialmente se dejan vacías y viceversa. Cualquier solución a un problema de este tipo debe contener un mínimo de 11 movimientos, independientemente de los detalles exactos del problema.
Se puede demostrar usando álgebra abstracta que sólo hay cinco posiciones fijas del tablero en las que el juego puede terminar exitosamente con una clavija. [6]
La solución más corta del juego inglés estándar implica 18 movimientos, contando los saltos múltiples como movimientos individuales:
Esta solución fue encontrada en 1912 por Ernest Bergholt y John Beasley demostró ser 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 ellas, 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 en el que es posible terminar con una clavija solitaria es en el centro o en 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 con el número ( posibilidades de posiciones del tablero ) de posibles posiciones del tablero después de n saltos , y la posibilidad de que la misma ficha se mueva para realizar un salto adicional ( N o más saltos ). Es interesante notar que la forma más corta de perder el juego es en seis movimientos, y la solución (además de sus rotaciones y reflexiones) 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 fichas están numeradas de izquierda a derecha, comenzando con 0 y moviéndose hacia abajo en cada fila y hacia el extremo izquierdo una vez que se marca cada fila).
NOTA: Si una posición del tablero se puede rotar y/o voltear hacia otra posición del tablero, las posiciones del tablero se cuentan como idénticas.
Dado que solo puede haber 31 saltos, las computadoras modernas pueden examinar fácilmente todas las posiciones del juego en un tiempo razonable. [8]
La secuencia anterior "PBP" se ha introducido como A112737 en OEIS . Tenga en cuenta que el número total de posiciones de placa alcanzables (suma de la secuencia) es 23.475.688, mientras que el número total de posiciones de placa posibles es 8.589.934.590 (33 bit-1) (2^33), por lo que solo se puede alcanzar alrededor del 2,2 % de todas las posiciones de placa posibles comenzando con el centro vacante.
También es posible generar todas las posiciones del tablero. Los resultados que se muestran a continuación se obtuvieron utilizando el conjunto de herramientas mCRL2 (consulte el ejemplo 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 agujero central.
Hay 3 posiciones iniciales no congruentes que tienen soluciones. [9] Estas son:
1)
0 1 2 3 4 5 6 0 o · · 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 de clavijas se ha jugado en tableros de otros tamaños, aunque los dos que se mencionan arriba son los más populares. También se ha jugado en un tablero triangular, con saltos permitidos en las tres direcciones. Siempre que la variante tenga la "paridad" adecuada y sea lo suficientemente grande, probablemente se pueda resolver.
Una variante triangular común tiene cinco clavijas en cada lado. Una solución en la que la clavija final llega al agujero vacío inicial no es posible para un agujero en una de las tres posiciones centrales. Una configuración de agujero vacío en la esquina se puede resolver en diez movimientos, y una configuración de agujero vacío en el medio del lado en nueve (Bell 2008):
El 26 de junio de 1992 se lanzó un videojuego basado en el solitario de clavijas para Game Boy. Titulado simplemente Solitaire , el juego fue desarrollado por Hect. En Norteamérica, DTMC lanzó el juego como Lazlos' Leap .
El juego para PC Shivers , un juego de rompecabezas de tipo point and click con temática de terror , incluye muchos rompecabezas y juegos para que el jugador los complete. El rompecabezas denominado "Damas chinas" es en realidad un solitario de fichas.
Cracker Barrel ofrece el juego en todas las mesas de sus sucursales. El tablero que se muestra es triangular con 15 hoyos en total.
En Cowboy Bebop: La Película , el antagonista principal, Vincent Volaju, pasa la mayor parte de su tiempo libre jugando al solitario. El vector para su ataque bioterrorista planeado, un tipo de nanobot , está almacenado en canicas de solitario.
Implementación del cálculo de fuerza bruta del juego de solitario Peg
