FreeCell #11982: a única partida impossível

A mesa inicial da #11982

Esta é a mesa que o jogo distribui quando você escolhe a partida 11982. As colunas são lidas de cima para baixo, e a última carta de cada uma é a única livre para mover. A notação é a de sempre: A (ás), J (valete), Q (dama) e K (rei), com ♥ copas, ♦ ouros, ♠ espadas e ♣ paus.

Tem solução?

Não

Cartas sobre os ases

22 (o máximo possível é 24)

Nosso solver

Esgotou as 61.643 posições que alcança, sem saída

Jogar esta partida

Pode jogar à vontade: o botão abre exatamente esta mesa no FreeCell. Ninguém vence, mas é o melhor jeito de entender o que a trava.

Como se descobriu que ela não tem solução

O FreeCell do Windows numerava as partidas de 1 a 32.000, e a pergunta era inevitável: dá para vencer todas? Em agosto de 1994, Dave Ring resolveu descobrir. Ele chamou voluntários em grupos de discussão da Usenet, como o rec.puzzles e o sci.math, e entregou a cada um um bloco de 100 partidas seguidas. Quem não conseguia vencer uma partida devolvia o número, e Ring passava a partida para os jogadores que mais resolviam. O esforço ficou conhecido como Internet FreeCell Project.

Em abril de 1995 o projeto terminou com 31.999 partidas vencidas. Sobrou só uma, a #11982. Desde então, ela resistiu a provavelmente milhares de jogadores e a pelo menos oito programas de computador diferentes, feitos para vasculhar todas as possibilidades. Mais tarde, a análise de Adrian Ettlinger, com o solver de Don Woods adaptado no FreeCell Pro, confirmou o resultado do projeto: das 32.000 partidas, todas têm solução menos a #11982.

Por que ela é impossível, em palavras simples

Não existe uma "prova de bolso" que caiba numa frase. A certeza vem de programas que testaram as jogadas possíveis e não acharam saída. Mas dá para ver na mesa o que pesa contra o jogador.

Os ases estão enterrados. Na #11982, 22 cartas cobrem os quatro ases, e o máximo possível numa mesa de FreeCell é 24. Três dos ases estão na primeira linha, o fundo da mesa: A♥ na coluna 1, sob 6 cartas, A♠ na coluna 2, sob 6 cartas, A♣ na coluna 4, sob 6 cartas e A♦ na coluna 7, sob 4 cartas. Para tirar um ás de baixo de seis cartas, você precisa ter onde guardar as seis, e só existem quatro células livres.

Há poucas jogadas boas de saída. Entre as oito cartas livres no começo, só três encaixam em outra: a Q♦ no K♣, o 2♥ no 3♠ e o 4♣ no 5♥. Nenhuma delas descobre um ás. O resto precisa passar pelas células livres, e cada carta que vai para uma célula fica presa lá até achar lugar, então as células enchem antes de qualquer coluna esvaziar.

As espadas baixas chegam cedo demais. O 2♠ e o 3♠ ficam livres logo de saída, na ponta das colunas 3 e 4, mas o A♠ está no fundo da coluna 2, sob seis cartas. Uma pista de que esse é um nó central: Michael Keller, que mantém um dos levantamentos mais completos sobre o FreeCell, registra que, se o A♠ e o A♦ trocarem de lugar, a partida passa a ter solução, e com só três células livres. Fizemos o teste com o nosso solver, e com a troca ele acha uma solução rapidamente.

Outra forma de medir: a #11982 precisaria de uma quinta célula livre. Com cinco células ela tem solução; com as quatro do jogo, não.

O que os jogadores tentam

Quem abre a #11982 costuma seguir o caminho natural, e vale a pena tentar cada um para ver onde ele quebra:

• Cavar o A♦ primeiro. Ele é o ás mais raso, com quatro cartas por cima na coluna 7. O problema é que, para chegar nele, as células enchem com cartas altas que não têm onde descer.
• Esvaziar uma coluna. Uma coluna vazia dobra o tamanho dos blocos que você move. Mas toda coluna da #11982 tem seis ou sete cartas, sem nenhum par já em sequência, e esvaziar uma custa mais espaço do que existe.
• Montar sequências longas para liberar espaço. Ajuda por algumas jogadas, até que os reis no meio das colunas 1, 7 e 8 bloqueiam o caminho.

Use o Desfazer à vontade: o interessante aqui é ver a mesa travar de jeitos diferentes. O nosso solver examinou 61.643 posições, todas as que ele consegue alcançar a partir desta mesa, e nenhuma leva à vitória.

As outras partidas famosas

A #11982 não está sozinha. Na lista estendida de 1 milhão de partidas, que chegou com o Windows XP, há outras sete sem solução: veja as 8 partidas impossíveis do FreeCell. Se você quer uma mesa difícil que tem solução, a mais pedida é a #617, e a primeira da numeração é a #1. As que mais deram trabalho ao nosso solver estão em partidas mais difíceis do FreeCell, e todas as famosas, lado a lado, em partidas famosas do FreeCell. Se está começando agora, veja antes como jogar FreeCell.

Perguntas frequentes