No FreeCell, como todas as cartas ficam à vista, o computador é bom para procurar soluções. Aqui você vê, de forma simples, como o computador resolve o FreeCell. Para este artigo, fizemos e testamos um programa que segue as mesmas regras do app FreeCell.

Busca: fazer uma jogada e examinar o que vem depois

O computador, como uma pessoa, examina “o que acontece se eu fizer esta jogada”. A diferença está na quantidade.

  1. Anotar todas as jogadas possíveis no tabuleiro atual (colocar numa célula livre, empilhar numa coluna, levar à célula de destino etc.).
  2. Fazer uma delas e criar um novo tabuleiro.
  3. Nesse tabuleiro, anotar de novo todas as jogadas possíveis.
  4. Quando aparece um tabuleiro com as 52 cartas nas células de destino, a sequência de jogadas até ele é a resposta.

Esse caminhar “de tabuleiro em tabuleiro, abrindo ramificações” se chama busca.

Truque 1: não examinar o mesmo tabuleiro duas vezes

No FreeCell, jogadas em ordens diferentes muitas vezes chegam ao mesmo tabuleiro. Se você move uma carta para a direita e depois a devolve para a esquerda, volta ao tabuleiro original. Se o computador lembrar dos tabuleiros já examinados e não examinar de novo um que reapareça, o desperdício cai muito.

Além disso, tabuleiros que só diferem na ordem das colunas ou na ordem das cartas dentro das células livres têm a mesma solução. Tratá-los como o mesmo tabuleiro reduz ainda mais o que há para examinar.

Truque 2: começar pelos tabuleiros mais promissores

Examinar todos os tabuleiros em ordem leva tempo demais. Por isso, dão-se pontos a critérios como “muitas cartas já nas células de destino”, “poucas cartas sobre a carta que queremos levar a seguir à célula de destino” e “células livres vazias”, e examinam-se primeiro os tabuleiros mais promissores.

Quando o programa deste artigo resolveu a distribuição nº 1 do FreeCell do Windows, ele encontrou uma solução de 110 jogadas ao examinar 843 tabuleiros. Para uma pessoa pensar nisso é trabalhoso, mas para o computador é um instante. A solução encontrada nem sempre é a mais curta (jogadas e quantidade de movimentos para vencer).

Confirmar que não tem solução

Se uma solução aparece, a distribuição tem solução. Mas como se confirma que “não tem”?

A resposta é examinar todos os tabuleiros que se alcançam. Se, qualquer que seja a jogada, não surgirem mais tabuleiros novos e mesmo assim não houver nenhum com as 52 cartas na célula de destino, a distribuição não tem solução.

O jogo 11982 do FreeCell do Windows é conhecido como uma distribuição sem solução. O programa deste artigo também confirmou: mesmo examinando todos os tabuleiros alcançáveis (cerca de 95 mil), incluindo as jogadas de devolver cartas da célula de destino, não havia solução (quase todo FreeCell tem solução).

A regra de mover várias cartas não muda se dá para resolver

No app FreeCell, de uma vez só se movem até “o número de células livres vazias + 1” cartas, e uma coluna vazia não aumenta esse número (quantas cartas dá para mover de uma vez). Mas uma jogada que move várias cartas pode ser dividida em jogadas de uma carta, usando células livres e colunas vazias. Os tabuleiros alcançáveis são os mesmos, então as distribuições com solução são as mesmas. O que muda é só como as jogadas são contadas.

Verificação das distribuições do app FreeCell

As distribuições do app FreeCell são embaralhadas ao acaso a cada jogo. O autor resolveu no computador 100 mil distribuições aleatórias e conferiu as soluções encontradas jogando-as até o fim com o mesmo mecanismo do jogo do app. O resultado: as 100 mil tinham solução.

Mas isso não é uma prova de que “toda distribuição tem solução”. Continua possível que, entre as que não examinamos, haja algumas, raras, sem solução.

As ideias para resolver também ajudam quem joga. Veja ainda estratégia e como vencer no FreeCell.