Quando tenho tempo livre por pouco tempo, geralmente jogo Free Cell no meu telefone. O aplicativo que uso permite undos ilimitados e, por isso, atualmente tenho uma série de 603 vitórias, com 655 vitórias e 10 derrotas no total.
Conforme demonstrado por essas estatísticas, minhas 10 derrotas ocorreram durante meus primeiros 52 jogos. Antes de usar este aplicativo, eu só jogava Free Cell muito raramente.
Como minhas estatísticas se aproximam de uma taxa de perda de 1%, eu me pergunto: Dado uma capacidade ilimitada de desfazer seus movimentos, existe alguma negociação inicial do Free Cell que seja impossível de resolver?
Uma prova de uma forma ou de outra seria o ideal (embora eu admita que duvido que “seria capaz de compreender tal prova), embora uma fonte confiável seria uma boa alternativa.
Comentários
- Este site pode ser útil: solitairelaboratory.com/freecell.html
- Dado que há ' não há informações secretas, desfazer é irrelevante para saber se algo é impossível de resolver.
Resposta
Não é difícil provar que existe um começo insolúvel. Imagine um começo em que os únicos primeiros movimentos possíveis seriam mover as cartas para as células extras. Em algumas versões, -1 e -2 são exemplos disso, embora a única maneira de reproduzi-los seja escolhendo aquela semente. 
Se você contar apenas as configurações que podem existir na reprodução normal, o seed 11982 na versão do Windows é um exemplo disso: 
Dos 32000 jogos originais do Freecell, 11982 é o único para o qual nenhuma solução legítima foi encontrada. Desde então, vários computadores e jogadores não conseguiram encontrar uma solução – ao ponto em que todas as combinações possíveis de movimentos foram tentadas e falharam.
Comentários
- Até onde eu ' li, as 32.000 " ofertas " em as versões originais do Windows são acidentalmente aquelas produzidas quando o gerador de números aleatórios do compilador MS C ' é semeado com os valores 1-32.000. Em outras palavras, eles não ' têm qualquer status especial como tal, e 32.000 é, obviamente, uma fração infinitesimal do número de maneiras possíveis de embaralhar um baralho de cartas (e um pequeno fração do número de embaralhamentos possíveis que até mesmo um modesto gerador de números aleatórios poderia produzir).
- Definitivamente acidental. O gerador de números aleatórios mencionado anteriormente tem 15 bits de entropia, o que significa 2 ^ 15 ordenações possíveis. Esse ' é 32.768.
- @ikegami: Tem mais bits de estado, mas apenas distribui os bits de ordem superior (porque os bits de ordem inferior são péssimo com LCGs).
- Você tem uma fonte para todos os 32000 jogos que podem ser resolvidos, exceto o jogo 11982? Há uma nova pergunta no site em que o usuário está perguntando se um jogo diferente não tem solução.
- @Thunderforge eu fiz na época. Era o registro de um grupo que entre eles testava e resolvia todos os outros jogos. Não faço ideia se ' ainda está por aí.