A resposta do Resta Um pode ser encontrada pelo computador. A “Dica” do app “Resta Um” e a conferência das respostas deste site usam programas com a mesma ideia. Aqui explicamos de forma simples como isso funciona.
Testar todas as jogadas em ordem
O método mais direto é repetir: escolher uma jogada possível e jogá-la, e escolher outra e jogá-la. Quando trava, volta uma jogada e escolhe outra ainda não testada.
- Escolha e faça uma das jogadas possíveis no tabuleiro atual.
- Se sobrar uma só bola, a resposta foi encontrada.
- Se não houver mais jogadas, volte uma jogada e teste outra.
- Se todas já foram testadas, volte mais uma jogada.
Esse método se chama busca em profundidade. É o mesmo que uma pessoa faz com o “Desfazer”, só que repetido numa velocidade enorme.
Não examinar a mesma posição várias vezes
No Resta Um, jogadas em ordens diferentes costumam levar à mesma posição. No inglês de 33 furos, depois da 7ª jogada há mais de 220 mil sequências, mas só cerca de 22 mil posições diferentes (de quantas maneiras se resolve?).
Por isso, guarda-se na memória as posições já examinadas que se mostraram sem saída e, ao encontrá-las de novo, volta-se logo. Só isso reduz muito o que há para examinar.
No programa usado para este site, a resposta do inglês de 33 furos que começa e termina no centro foi achada num instante (menos de 0,1 segundo). Mas nem sempre é rápido: procurando do mesmo modo a partir de um tabuleiro com outra 2ª jogada, levou cerca de 9 segundos. O tempo muda muito conforme a jogada que se testa primeiro.
Cortar sem olhar adiante
Outro truque é, ao perceber que desta posição não há como chegar à meta, seja qual for a jogada, parar sem examinar o resto. Chama-se “poda”.
O app poda de duas formas.
- Pintura em 3 cores: pintando o tabuleiro de 3 cores na diagonal, a cada jogada a paridade do número de bolas das 3 cores se inverte. Assim, só pelo cálculo se sabe em que furos a última bola pode ficar a partir da posição atual (artigo sobre a pintura em 3 cores).
- Linha e coluna da bola chefe: como a bola chefe anda duas casas por vez, a paridade da linha e da coluna do furo em que está não muda (Como deixar a bola chefe por último).
Se não resta nenhum furo que cumpra as duas condições ao mesmo tempo, não há furo em que a bola chefe possa ficar por último. Essa posição já se vê como “sem solução” sem olhar adiante.
Na “Dica” do app
A “Dica” do app procura a próxima jogada que, da posição atual, leva à meta, e a faz brilhar com um anel dourado.
- Sabe a resposta de antemão: os tabuleiros de “Quebra-cabeças” são criados pulando ao contrário, então se conhece a resposta de quando foram criados (como criamos problemas que sempre têm solução). As posições no caminho dessa resposta são guardadas como “tem solução”, então a resposta vem logo. Mesmo numa posição fora do caminho, se a busca encontrar o caminho da resposta, ela para ali.
- Limite do que se examina: cada dica examina no máximo 1,5 milhão de posições ou 3 segundos. Em tabuleiros grandes, a resposta pode não sair até lá.
- Diz quantas jogadas voltar: quando a meta já não pode ser alcançada, ou não se descobre dentro do limite, ela examina as posições a que “Desfazer” pode voltar e diz, por exemplo, “Volte 3 para salvar”. Como vai reduzindo pela metade as posições examinadas, acha rápido mesmo com muitas jogadas.
Dicas para quem resolve à mão
Os truques do computador servem também para as pessoas.
- Decore as formas sem saída: uma forma que já falhou falha de novo, mesmo que se chegue a ela por outra ordem.
- Pense a partir do objetivo: os furos em que a última bola pode ficar já estão definidos desde o início. Decidir antes o furo que quer alcançar facilita escolher as jogadas (como deixar a última bola no centro).
- Volte e teste: como na busca em profundidade, na dúvida, voltar um pouco e testar outra jogada é o jeito certo.
