Solitaire es un juego de mesa para un solo jugador en el que se intercambian clavijas en un tablero con agujeros. Algunos kits usan bolas y tablas con muescas. En los EE. UU., el juego se llama Peg Solitaire (peg solitario), y el nombre Solitario se refiere al solitario. En el Reino Unido el juego se conoce como Solitaire (solitario) y el juego de cartas se llama Patience ( solitario ). En algunos lugares, especialmente en India , el juego se llama Brainvita . En la URSS se produjo un rompecabezas llamado Yoga [1] .
La primera mención del juego se encuentra en la corte de Luis XIV en 1697. Este año se destaca un grabado de Claude Auguste Bereille Anne de Roan Chabot, princesa de Soubise , que representa a una princesa jugando al solitario. En agosto de 1697, se publicó una descripción del tablero, reglas y ejemplos de problemas en la revista literaria francesa Mercure galant . Esta es la primera mención conocida del juego impresa.
En un juego estándar, todo el campo está lleno de clavijas, a excepción del agujero central. El objetivo del juego es liberar todo el tablero de la clavija, dejando la última clavija en el centro del tablero.
Hay dos tableros tradicionales para jugar ('.' como clavija inicial, 'o' como el hoyo vacío):
| inglés | europeo | ||
|---|---|---|---|
| • • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • | • • • • • • • • • • • • • • • • • • o • • • • • • • • • • • • • • • • • • |
Un movimiento legal es saltar una clavija a través de una clavija adyacente a un hoyo libre inmediatamente después de la segunda clavija (como en las damas, pero el movimiento es vertical u horizontal, no puede moverse en diagonal), luego se retira la clavija saltada.
Símbolos en los siguientes diagramas:
• clavija en el agujero
* clavija que se está moviendo
o agujero vacío
¤ agujero desde el que se realizó el movimiento
* posición final de la clavija
o agujero de la clavija retirada.
Entonces los movimientos legales en las cuatro direcciones son:
* • o → ¤ o * salta a la derecha o • * → * o ¤ saltar a la izquierda * ¤ • → o saltar hacia abajo o * o * • → o saltar * ¤En el tablero inglés, los tres primeros movimientos pueden ser:
• • • • • • • • • • • • • * • • ¤ • • o • • * • • • • • • • • • • • o • • • • ¤ o * • • • • oo o • • • • • • o • • • • • * • • • • • • • • • • • ¤ • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •Es fácil ir por el camino equivocado y descubrir que dos o tres agujeros vacíos separan una clavija solitaria. Muchas personas no han podido resolver el problema.
Hay muchas soluciones diferentes para un problema estándar, y para describirlas, daremos designaciones de letras a los agujeros:
inglés europeo abcbc defydefz ghijklmghijklm nopx PON nopx PON MLKJIHGMLKJIHG FEDZFEDY CBACBALa designación espejo de los campos se usa, entre otras cosas, porque en el tablero europeo en una de las familias de juegos alternativos, el juego comienza con algún agujero en un lugar arbitrario y debe terminar en el agujero espejo. En el tablero inglés, los juegos alternativos comienzan y terminan en el mismo hoyo.
En la versión europea del juego, no hay solución con un cuadrado inicial vacío en el centro, a menos que se permitan movimientos en diagonal. Esto es fácil de entender si se consideran los argumentos de Hans Zantema. Marquemos las posiciones del tablero con las letras A, B y C de la siguiente manera:
A B C ABCAB ABCABCA BCABCAB CABCABC BCABC A B CContaremos el número de clavijas en posiciones de cada tipo. Si la posición vacía inicial está en el centro, el número de posiciones A es 12, las posiciones B también son 12 (un total de 13, pero uno está libre), el número de posiciones C también es 12. Después de cada movimiento, el número de clavijas del grupo A disminuye o aumenta en uno, lo mismo sucede con las posiciones de los grupos B y C. Así, después de un número par de movimientos, todos estos tres números son pares, y después de un número impar, son impares. Por lo tanto, la posición final, en la que solo queda una clavija, no se puede obtener: el grupo donde termina la clavija tendrá una suma de uno, mientras que los otros dos deben tener una suma de cero.
Hay, sin embargo, algunas otras configuraciones en las que un agujero libre se puede llevar a una sola clavija.
Una táctica útil para resolver el rompecabezas es dividir todo el tablero en trillizos, y luego los trillizos se eliminan con una clavija adicional, un catalizador. En el ejemplo anterior, * es el catalizador:
* • o ¤ o * o * • * o ¤ • → • → o → o • • ¤oEsta técnica se puede utilizar para tres clavijas en fila, para bloques de 2x3 y para un patrón en L de 6 clavijas (3 unidireccionales y 4 perpendiculares).
Hay juegos que comienzan con dos posiciones vacías y terminan con dos clavijas en esas posiciones. También es posible comenzar en una posición preseleccionada y terminar en otra posición preseleccionada. En el tablero inglés, un hoyo vacío puede estar en cualquier lugar y el juego debe terminar en la misma posición o en una de las tres posiciones adicionales permitidas. Entonces, si el campo vacío inicial estaba en el punto a , el juego debería terminar con una sola ficha en las posiciones a , p , O o C .
Para obtener un análisis completo del juego, consulte Winning Ways for your Mathematical Plays ( ISBN 0-12-091102-7 en el Reino Unido e ISBN 1-56881-144-6 en los EE. UU.) (volumen 4, segunda edición). El libro introduce una notación llamada función de pagoda , que es una poderosa herramienta para probar la imposibilidad de resolver un problema de solitario dado (generalizado). El problema de encontrar tal función se formula como un problema de programación lineal entera (ver Kiyomi y Matsui 2001). Uehara e Iwata (1990) estudiaron problemas Hi-Q generalizados que son equivalentes a problemas solitarios y demostraron que son NP-completos . Avis y Deza (1996) formularon el problema del solitario como un problema de optimización combinatoria y discutieron una propiedad del dominio de soluciones factibles llamada cono del solitario. Kiyomi y Matsui (Kiyomi, Matsui, 2001) propusieron un método eficiente para resolver problemas de tenia.
Un estudio inédito de 1989 sobre una versión generalizada del juego en el tablero inglés mostró que cada problema factible en el juego generalizado tiene 2 9 soluciones diferentes, excluyendo la simetría, ya que el tablero inglés contiene 9 subcuadrados diferentes de 3x3. Este estudio dio un límite inferior al tamaño de los posibles problemas de 'posiciones inversas' en los que los agujeros originalmente ocupados se ocupan y viceversa. Cualquier solución a tal problema debe consistir en al menos 11 movimientos, independientemente de la formulación exacta del problema.
El álgebra se puede usar para demostrar que solo hay 5 puntos fijos donde el juego puede terminar con éxito con una clavija [2] .
La solución más corta de la versión estándar en inglés del juego es de 18 movimientos, contando múltiples saltos en un solo movimiento:
| La solución más corta al solitario peg inglés |
|---|
|
ex lj ck
• • • • • • • • • • • ¤
• * • • ¤ • • • o • • o o
• • • • • • • • o • • • • • * o ¤ • • • • • * o •
• • • o • • • • • * • • • • • • • • • • • • • • •
• • • • • • • • • • • • • • • • • • • • • • • • •
• • • • • • • • • • • •
• • • • • • • • • • • •
Pf DP GI JH
• • o • • o • • o • • o
• o * • o • • o • • o •
• • • • o o • • • • • oo • • • • • oo • • • • • oo •
• • • • ¤ • • • • • • • • • • • • • • • • • • • • •
• • • • • • • • • • • o • • • • • * o ¤ • • • ¤ o * o
• • • • • ¤ • • o • • o
• • • • • • • • • • • •
mGI ik gi LJHljh
• • o • • o • • o • • o
• o • • o • • o • • o •
• • • • oo ¤ • • ¤ o * oo ¤ o * o • ooo * o o o o o
• • • • • • o • • • • • • o • • • • • • o • • • • • o o
• • • o * o o • • • o • oo • • • o • oo • ¤ o o o o o
• • o • • o • • o • • o
• • • • • • • • • • • •
CK pF ACK Mgi
• • o • • o • • o • • o
• o • • o • • o • • o •
o • oooooo • oooooo • ooooo o o * oooo
• • • • • oo • • ¤ • • oo • • o • • oo o • o • • oo
• o * oooo • o o oooo • o * oooo ¤ o • oooo
o • o * • o o • oo • o
¤ • • o • • o o ¤ ooo
ackI dpFDPp buey
¤ooooooo _ _ _
• o o ¤ ooooo
oo • o o oooo o ooooooooooo
o • o • o ooo • * o o ooo ¤ o * ooo
oo • o * oooo o o o ooooooooo
o • o o o o o o
oooooooooo
El orden de algunos movimientos se puede cambiar. Tenga en cuenta que si usa * para agujeros y o para clavijas, puede resolver el rompecabezas trabajando hacia atrás desde la última imagen y trabajando hasta la primera. Sin embargo, esto requerirá más de 18 movimientos. |
La solución fue encontrada en 1912 por Ernest Bergholt y resultó ser la solución más corta por John Beasley en 1964 [3] .
La misma solución se puede ver en [4] , que también introduce la notación de Wolstenholme, que está diseñada para facilitar el recuerdo de la solución.
Otras soluciones se incluyen en la siguiente lista. La lista tiene el formato
posición inicial: posición final =Luego vienen los pares: la clavija y la posición a la que se mueve. Los pares están separados por una coma o una barra oblicua (la barra oblicua se coloca al final de un grupo de movimientos)
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, buey 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/buey 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, buey, 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/dpEl lugar donde puede terminar el juego es el centro, o uno de los medios de los bordes, y el último movimiento tenemos que estar allí.
A continuación se muestra una tabla del número de B Posiciones posibles después de n jugadas, y el número O de la ausencia de X jugadas, posiciones en las que la continuación es imposible.
Si una posición se puede obtener por rotación o espejo, se considera idéntica.
|
|
|
|
Dado que el número máximo de posiciones para cada movimiento no supera los 3626632 y el número de movimientos es 31, las computadoras modernas pueden calcular fácilmente todas las posiciones en un tiempo razonable.
Las secuencias anteriores de "VP" se enumeran en la OEIS con el número A112737 [5] . Tenga en cuenta que el número total de posiciones alcanzables (la suma de la secuencia) es 23 475 688 [5] , mientras que el número total de posiciones posibles es 2 33 , o aproximadamente 2 33 /8 ~ 1 billón si se tiene en cuenta la simetría. Por lo tanto, solo alrededor del 2,2% de todas las posiciones posibles en el tablero se pueden lograr si se comienza desde un centro vacío.
Puedes conseguir todas las posiciones posibles en el tablero. Los resultados que se muestran en la tabla se pueden obtener usando el conjunto de herramientas mcrl2 (vea el ejemplo peg_solitaire en el paquete).
|
|
|
|
hay 3 posiciones iniciales incongruentes que tienen solución. Eso:
una)
0 1 2 3 4 5 6 0 o • • una • • • • • 2 • • • • • • • 3 • • • • • • • cuatro • • • • • • • 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 • • • • • • • cuatro • • • • • • • 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 • • • una • • • • • 2 • • • o • • • 3 • • • • • • • cuatro • • • • • • • 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 también se juega en otros tableros, aunque estos dos son los más populares. El tablero puede ser triangular, con movimientos en tres direcciones.
Por lo general, la variante triangular tiene cinco agujeros por lado. Una solución en la que la clavija final termina en un campo inicialmente vacío no es posible en los tres puntos centrales. Un problema con un cuadrado vacío en la esquina se puede resolver en diez movimientos, pero si el cuadrado vacío está ubicado en el centro del lado, se puede resolver en nueve movimientos (Bell 2008):
| La solución más corta de la variante triangular. |
|---|
|
* = la clavija que hace el siguiente movimiento; ¤ = agujero liberado por el movimiento; o = clavijas quitadas (sobre saltadas); * = hoyo en el que terminó la clavija después del movimiento; • • • * ¤ • • • • • • • * o ¤ • • • • • • * • • ¤ • • * o • • • • • • • • • • • • • • o • • * * • * * • o • • ¤ o * * • o * o ¤ • o • * o • o • • o • ooooo * * * * ¤ ¤ oooo o o o o * * o o o oo * oo ¤ ¤ • • ¤ o o o ooo * * oo • o o o o o * * o • o ¤ ¤ o • oooo * oooo ¤ oo * oo |