Solitario Peg - Peg solitaire

La princesa de Soubise jugando al solitario, 1697

Peg solitaire (o Solo Noble ) 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 hendiduras. El juego se conoce simplemente como Solitario en el Reino Unido, donde los juegos de cartas se llaman Paciencia . También se llama Brainvita (principalmente en India , donde los juegos se venden comercialmente con este nombre).

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 de su lado. La edición de agosto de 1687 de la revista literaria francesa Mercure galant contiene una descripción del tablero, reglas y ejemplos de problemas. Esta es la primera referencia conocida impresa del juego.

El juego estándar llena todo el tablero con clavijas excepto el agujero central. El objetivo es, haciendo jugadas válidas, vaciar todo el tablero salvo una clavija solitaria en el agujero central.

Tablero

Tablero de solitario inglés
Tablero de solitario clavija europea

Hay dos tablas tradicionales ('.' Como clavija inicial, 'o' como agujero inicial):

inglés europeo 
     · · ·
     · · ·
 · · · · · · · 
 · · · o · · · 
 · · · · · · · 
     · · ·
     · · ·

     · · ·
   · · · · ·
 · · · · · · · 
 · · · o · · · 
 · · · · · · · 
   · · · · ·
     · · ·

Jugar

Jugando al solitario Peg
Un hombre jugando al solitario de clavija triangular en un restaurante Cracker Barrel .

Un movimiento válido es saltar una clavija ortogonalmente sobre una clavija adyacente a un agujero a dos posiciones de distancia y luego quitar la clavija saltada.

En los siguientes diagramas, ·indica una clavija en un agujero, *envalentonado indica la clavija que se debe 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 *  Jump to right

o · *  →  * o ¤  Jump to left

*     ¤
·  →  o  Jump down
o     *

o     *
·  →  o  Jump up
*     ¤

En un tablero en inglés, los primeros tres movimientos podrían ser: 

    · · ·             · · ·             · · ·             · · · 
    · * ·             · ¤ ·             · o ·             · * · 
· · · · · · ·     · · · o · · ·     · ¤ o * · · ·     · o o o · · ·
· · · o · · ·     · · · * · · ·     · · · · · · ·     · · · ¤ · · ·
· · · · · · ·     · · · · · · ·     · · · · · · ·     · · · · · · ·
    · · ·             · · ·             · · ·             · · ·
    · · ·             · · ·             · · ·             · · ·

Estrategia

Hay muchas soluciones diferentes para el problema estándar, y una notación utilizada para describirlas asigna letras a los agujeros: 

   English          European
    a b c             a b c
    d e f           y d e f z
g h i j k l m     g h i j k l m
n o p x P O N     n o p x P O N
M L K J I H G     M L K J I H G
    F E D           Z F E D Y
    C B A             C B A

Esta notación de imagen de espejo se usa, entre otras razones, ya que en el tablero europeo, un conjunto de juegos alternativos es comenzar con un agujero en alguna posición y terminar con una sola clavija en su posición de espejo. En el tablero inglés, los juegos alternativos equivalentes son comenzar con un hoyo y terminar con una clavija en la misma posición.

No hay solución para el tablero europeo con el hoyo inicial ubicado en el centro, si solo se permiten movimientos ortogonales. Esto se ve fácilmente de la siguiente manera, por un argumento de Hans Zantema . Divida las posiciones del tablero en posiciones A, B y C de la siguiente manera: 

    A B C
  A B C A B
A B C A B C A
B C A B C A B
C A B C A B C
  B C A B C
    A B C

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 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, 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 solo una 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, por lo tanto, par.

Sin embargo, hay varias otras configuraciones en las que un solo orificio inicial se puede reducir a una sola clavija.

Una táctica que se puede utilizar es dividir el tablero en paquetes de tres y purgarlos (eliminarlos) por completo con 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 una tabla inglesa, el agujero puede estar en cualquier lugar y la clavija final solo puede terminar donde lo permitan múltiplos de tres. Por lo tanto un agujero en un sólo puede dejar un solo PEG a una , p , O o C .

Estudios sobre el solitario peg

Se conoce un análisis exhaustivo del juego. 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 clavija, generalizado y dado.

Una solución para encontrar una función de 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.

Un artículo de 1990 trató los problemas Hi-Q generalizados que son equivalentes a los problemas de solitario de clavija y mostró su NP-completo .

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

En 1999, el solitario peg se resolvió por completo en una computadora mediante una búsqueda exhaustiva a través de todas las variantes posibles. Se logró haciendo uso de las simetrías, almacenamiento eficiente de constelaciones de tableros y hashing.

En 2001 se desarrolló un método eficaz para resolver problemas de solitario con clavijas.

Un estudio no publicado desde 1989 en una versión generalizada del juego en el tablero Inglés mostró que cada posible problema en el juego generalizada tiene 2 9 posibles soluciones distintas, con exclusión de las simetrías, como la junta Inglés contiene 9 diferenciadas 3 × 3 sub-cuadrados. 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 tal problema debe contener un mínimo de 11 movimientos, independientemente de los detalles exactos del problema.

Se puede demostrar usando álgebra abstracta que solo hay 5 posiciones fijas en el tablero donde el juego puede terminar con éxito con una clavija.

Soluciones para el juego inglés

La solución más corta para el juego en 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ó ser la más corta posible en 1964.

Esta solución también se puede ver en una página que también presenta la notación de 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

  • Lista de hoyos iniciales
  • Colon
  • Lista de clavijas de destino final
  • Signo de igual
  • Clavija de origen y agujero de destino (las clavijas saltadas se dejan como ejercicio para el lector)
  • , o / ( se usa una barra oblicua para separar 'trozos' como una purga de seis )
 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,ox/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,ox/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

Ataque de fuerza bruta al solitario peg inglés estándar

El único lugar donde es posible terminar con una clavija solitaria es el centro, o el medio de uno de los bordes; en el último salto, siempre habrá una opción de elegir si terminar en el centro o en el borde.

A continuación se presenta una tabla sobre el número ( P OSIBLE B Oard P ositions) de posibles posiciones de la junta después de n saltos, y la posibilidad de la misma peón trasladó a hacer un salto adicional ( N o F ás J umps).

NOTA: Si una posición de la placa se puede rotar y / o voltear a otra posición de la placa, las posiciones de la placa 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.

La secuencia anterior "PBP" se ha introducido como A112737 en OEIS . Tenga en cuenta que el número total de posiciones de tablero alcanzables (suma de la secuencia) es 23,475,688, mientras que el número total de posiciones de tablero posibles es 8,589,934,590 (33bit-1) (2 ^ 33), por lo que solo alrededor del 2.2% de todas las posiciones de tablero posibles pueden llegar comenzando con el centro vacante.

También es posible generar todas las posiciones del tablero. Los resultados a continuación se han obtenido utilizando el conjunto de herramientas mcrl2 (consulte el ejemplo de peg_solitaire en la distribución).

En los resultados a continuación se generan todas las posiciones del tablero realmente alcanzadas comenzando con el centro vacante y terminando en el hoyo central.

Soluciones para el juego europeo

Hay 3 posiciones iniciales no congruentes que tienen soluciones. Estos 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]

Variantes de placa

El solitario Peg se ha jugado en tableros de otros tamaños, aunque los dos anteriores son los más populares. También se ha jugado en un tablero triangular, con saltos permitidos en las 3 direcciones. Siempre que la variante tenga la "paridad" adecuada y sea lo suficientemente grande, probablemente tendrá solución.

Formas de tablero de juego de solitario Peg:
(1) estilo francés (europeo), 37 hoyos, siglo XVII;
(2) JC Wiegleb, 1779, Alemania, 45 hoyos;
(3) 3-3-2-2 asimétrico según lo descrito por George Bell, siglo XX;
(4) estilo inglés (estándar), 33 hoyos;
(5) Diamante, 41 agujeros;
(6) Triangular, 15 agujeros.
Gris = el agujero para el superviviente.

Una variante triangular común tiene cinco clavijas en un 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 de esquina vacía se puede resolver en diez movimientos y una configuración de agujero medio vacío en nueve (Bell 2008):

Videojuego

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 América del Norte, DTMC lanzó el juego como "Lazlos 'Leap".

Referencias

Otras lecturas

enlaces externos