Peg solitaire - Peg solitaire

A princesa de Soubise jogando paciência, 1697

Peg solitaire (ou Solo Noble ) é um jogo de tabuleiro para um jogador que envolve o movimento de pinos em um tabuleiro com buracos. Alguns conjuntos usam mármores em um tabuleiro com recortes. O jogo é conhecido simplesmente como Paciência no Reino Unido, onde os jogos de cartas são chamados de Paciência . É também chamado de Brainvita (principalmente na Índia , onde os conjuntos são vendidos comercialmente com esse nome).

As primeiras evidências do jogo remontam à corte de Luís XIV e à data específica de 1697, com uma gravura feita dez anos depois por Claude Auguste Berey de Anne de Rohan-Chabot , princesa de Soubise, com o quebra-cabeça de o lado dela. A edição de agosto de 1687 da revista literária francesa Mercure galant contém uma descrição do tabuleiro, regras e exemplos de problemas. Esta é a primeira referência conhecida ao jogo na impressão.

O jogo padrão preenche todo o tabuleiro com pinos, exceto o buraco central. O objetivo é, fazendo jogadas válidas, esvaziar todo o tabuleiro, exceto por uma estaca solitária no buraco central.

Borda

Tabuleiro de paciência inglês
Peg solitário europeu

Existem duas placas tradicionais ('.' Como um pino inicial, 'o' como um orifício inicial):

inglês europeu 
     · · ·
     · · ·
 · · · · · · · 
 · · · o · · · 
 · · · · · · · 
     · · ·
     · · ·

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

Toque

Jogando paciência Peg
Um homem jogando paciência de peg triangular em um restaurante Cracker Barrel .

Um movimento válido é pular uma cavilha ortogonalmente sobre uma cavilha adjacente para um buraco a duas posições de distância e, em seguida, remover a cavilha saltada.

Nos diagramas a seguir, ·indica uma cavilha em um buraco, em *negrito indica a cavilha a ser movida e oindica um buraco vazio. Um azul ¤é o buraco do qual o pino atual se moveu; um vermelho *é a posição final dessa cavilha, um vermelho oé o orifício da cavilha que foi saltada e removida.

Assim, os movimentos válidos em cada uma das quatro direções ortogonais são: 

* · o  →  ¤ o *  Jump to right

o · *  →  * o ¤  Jump to left

*     ¤
·  →  o  Jump down
o     *

o     *
·  →  o  Jump up
*     ¤

Em um tabuleiro inglês, os três primeiros movimentos podem ser: 

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

Estratégia

Existem muitas soluções diferentes para o problema padrão, e uma notação usada para descrevê-los atribui letras aos buracos: 

   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 notação de imagem espelhada é usada, entre outras razões, uma vez que no tabuleiro europeu, um conjunto de jogos alternativos é começar com um buraco em alguma posição e terminar com uma única cavilha na sua posição espelhada. No tabuleiro inglês, os jogos alternativos equivalentes são começar com um buraco e terminar com uma cavilha na mesma posição.

Não há solução para o tabuleiro europeu com o buraco inicial localizado centralmente, se apenas movimentos ortogonais são permitidos. Isso é facilmente visto como segue, por um argumento de Hans Zantema . Divida as posições da placa nas posições A, B e C da seguinte forma: 

    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 com apenas a posição central livre, o número de posições A cobertas é 12, o número de posições B cobertas é 12 e também o número de posições C cobertas é 12. Após cada movimento, o número de posições A cobertas aumenta ou diminui em um, e o mesmo para o número de posições B cobertas e o número de posições C cobertas. Portanto, após um número par de movimentos, todos esses três números são pares e, após um número ímpar de movimentos, todos esses três números são ímpares. Conseqüentemente, uma posição final com apenas um pino não pode ser alcançada, pois isso exigiria que um desses números seja um (a posição do pino, um é ímpar), enquanto os outros dois números são zero, portanto, par.

Existem, no entanto, várias outras configurações onde um único furo inicial pode ser reduzido a um único pino.

Uma tática que pode ser usada é dividir o tabuleiro em pacotes de três e purgá-los (removê-los) inteiramente usando uma cavilha extra, o catalisador, que salta para fora e depois volta novamente . No exemplo abaixo, o * é o catalisador: 

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

Esta técnica pode ser usada com uma linha de 3, um bloco de 2,3 e uma forma de L de 6 pinos com uma base de comprimento 3 e vertical de comprimento 4.

Outros jogos alternativos incluem começar com dois buracos vazios e terminar com dois pinos nesses buracos. Também começando com um buraco aqui e terminando com uma cavilha ali . Em uma placa inglesa, o buraco pode estar em qualquer lugar e a cavilha final só pode terminar onde permitirem múltiplos de três. Assim, um orifício em um só pode deixar um único PEG a um , P , S ou C .

Estudos sobre peg solitário

Uma análise completa do jogo é conhecida. Esta análise introduziu uma noção chamada função de pagode, que é uma ferramenta forte para mostrar a inviabilidade de um determinado problema generalizado de peg solitário.

Uma solução para encontrar uma função pagode, que demonstra a inviabilidade de um determinado problema, é formulada como um problema de programação linear e solucionável em tempo polinomial.

Um artigo em 1990 tratou dos problemas Hi-Q generalizados que são equivalentes aos problemas do solitário peg e mostrou sua NP-completude .

Um artigo de 1996 formulou um problema peg solitaire como um problema de otimização combinatória e discutiu as propriedades da região viável chamada 'um cone solitaire'.

Em 1999, o peg solitaire foi completamente resolvido em um computador usando uma pesquisa exaustiva por todas as variantes possíveis. Isso foi conseguido aproveitando as simetrias, armazenamento eficiente de constelações de tabuleiro e hashing.

Em 2001, um método eficiente para resolver problemas de peg solitário foi desenvolvido.

Um estudo não publicado de 1989 sobre uma versão generalizada do jogo no tabuleiro inglês mostrou que cada problema possível no jogo generalizado tem 2 9 soluções distintas possíveis, excluindo simetrias, já que o tabuleiro inglês contém 9 sub-quadrados 3 × 3 distintos. Uma consequência dessa análise é colocar um limite inferior no tamanho dos possíveis problemas de "posição invertida", nos quais as células inicialmente ocupadas são deixadas vazias e vice-versa. Qualquer solução para esse problema deve conter um mínimo de 11 movimentos, independentemente dos detalhes exatos do problema.

Pode-se provar, usando álgebra abstrata, que existem apenas 5 posições fixas no tabuleiro onde o jogo pode terminar com sucesso com um pino.

Soluções para o jogo inglês

A solução mais curta para o jogo inglês padrão envolve 18 movimentos, contando vários saltos como movimentos únicos:

Essa solução foi encontrada em 1912 por Ernest Bergholt e comprovada como a mais curta possível por John Beasley em 1964.

Essa solução também pode ser vista em uma página que também apresenta a notação Wolstenholme , projetada para tornar a memorização da solução mais fácil.

Outras soluções incluem a lista a seguir. Nestes, a notação usada é

  • Lista de buracos iniciais
  • Cólon
  • Lista de Pegs de destino final
  • Sinal de igual
  • Peg de origem e buraco de destino (os pinos saltados são deixados como um exercício para o leitor)
  • , ou / ( uma barra é usada para separar 'pedaços', como uma eliminação 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 força bruta no Paciência Peg padrão inglês

O único lugar em que é possível acabar com uma estaca solitária é no centro, ou no meio de uma das bordas; no último salto, sempre haverá a opção de escolher se termina no centro ou na borda.

Segue-se uma tabela sobre o número ( P OSSÍVEIS B clad P ositions) de possíveis posições do tabuleiro depois de n salta, e a possibilidade do mesmo peão movido para fazer um novo salto ( N O F utros J umps).

NOTA: Se uma posição da placa pode ser girada e / ou invertida para outra posição da placa, as posições da placa são contadas como idênticas.

Como só pode haver 31 saltos, os computadores modernos podem examinar facilmente todas as posições do jogo em um tempo razoável.

A sequência "PBP" acima foi inserida como A112737 no OEIS . Observe que o número total de posições de placa alcançáveis ​​(soma da sequência) é 23.475.688, enquanto o número total de posições de placa possíveis é 8.589.934.590 (33bit-1) (2 ^ 33), portanto, apenas cerca de 2,2% de todas as posições de placa possíveis podem ser alcançado começando com o centro vago.

Também é possível gerar todas as posições do tabuleiro. Os resultados abaixo foram obtidos usando o conjunto de ferramentas mcrl2 (veja o exemplo peg_solitaire na distribuição).

Nos resultados abaixo são geradas todas as posições do tabuleiro realmente alcançadas começando com o centro vago e terminando no buraco central.

Soluções para o jogo europeu

Existem 3 posições iniciais não congruentes que possuem soluções. Estes são:

1) 

          0 1 2 3 4 5 6
        0     o · ·
        1   · · · · ·
        2 · · · · · · ·
        3 · · · · · · ·
        4 · · · · · · ·
        5   · · · · ·
        6     · · ·

Solução possível: [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     · · ·

Solução possível: [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]

e 3) 

          0 1 2 3 4 5 6
        0     · · ·
        1   · · · · ·
        2 · · · o · · ·
        3 · · · · · · ·
        4 · · · · · · ·
        5   · · · · ·
        6     · · ·

Solução possível: [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 tabuleiro

Peg solitaire foi jogado em tabuleiros de outros tamanhos, embora os dois dados acima sejam os mais populares. Também foi jogado em um tabuleiro triangular, com saltos permitidos em todas as 3 direções. Contanto que a variante tenha a "paridade" adequada e seja grande o suficiente, provavelmente será solucionável.

Formas do tabuleiro de jogo de paciência Peg:
(1) Estilo francês (europeu), 37 buracos, século 17;
(2) JC Wiegleb, 1779, Alemanha, 45 buracos;
(3) Assimétrico 3-3-2-2 conforme descrito por George Bell, século 20;
(4) Estilo inglês (padrão), 33 buracos;
(5) Diamante, 41 furos;
(6) Triangular, 15 orifícios.
Cinza = o buraco para o sobrevivente.

Uma variante triangular comum tem cinco pinos de lado. Uma solução em que o pino final chega ao buraco vazio inicial não é possível para um buraco em uma das três posições centrais. Uma configuração de orifício de canto vazio pode ser resolvida em dez movimentos, e uma configuração de orifício médio vazio em nove (Bell 2008):

Videogame

Em 26 de junho de 1992, um videogame baseado em peg solitaire foi lançado para o Game Boy. Intitulado simplesmente "Solitaire", o jogo foi desenvolvido pela Hect. Na América do Norte, o DTMC lançou o jogo como "Lazlos 'Leap".

Referências

Leitura adicional

links externos