No modo “Quebra-cabeças” do app “Resta Um”, a cada “Novo jogo” é criado um tabuleiro de formato diferente. Mesmo assim, todos eles sempre têm solução. Este artigo mostra como isso funciona.

Criar do jeito comum não garante solução

Se o formato dos furos e a posição das bolas forem sorteados, muitos tabuleiros ficarão sem solução. Para saber se há solução, seria preciso examinar todas as jogadas, o que leva tempo quando há muitas bolas.

Por isso o app usa o método de criar o problema ao contrário, a partir da resposta.

Pular ao contrário

Uma jogada do Resta Um é: “uma bola pula por cima da vizinha até um furo vazio e a pulada é capturada”. Ao fazer isso ao contrário, fica

uma bola volta para o furo vazio duas casas atrás e uma bola é colocada no furo vazio do meio

A cada jogada ao contrário, aumenta uma bola.

Começando com uma só bola chefe

As jogadas ao contrário são empilhadas a partir de um tabuleiro com só a bola chefe (ou seja, um tabuleiro já vencido). Veja um exemplo pequeno.

Primeiro, um tabuleiro com só a bola chefe.

1ª vez: a bola chefe volta duas casas para cima e se coloca uma bola no furo do meio.

2ª vez: a bola colocada no meio volta duas casas para a esquerda e se coloca uma bola no furo entre elas.

3ª vez: a bola chefe volta duas casas para a direita e se coloca uma bola no furo do meio.

Agora temos um problema de 4 bolas.

As jogadas ao contrário viram a resposta

Se você jogar as jogadas criadas, da última para a primeira, no sentido normal, elas formam a resposta. No exemplo, usando como tabuleiro só os furos empregados, o problema se resolve assim.

  1. Jogada 1 e1→c1
  2. Jogada 2 a2→c2
  3. Jogada 3 c1→c3
  4. Após a jogada 3 Restam 1

A sequência criada ao contrário parte de um tabuleiro já vencido, então, seguida no sentido normal, sempre deixa só a bola chefe. Por isso fica garantido que todo problema tem pelo menos uma resposta.

Truques usados no app

O app acrescenta alguns truques a esse método de criação.

  • Reaproveitar furos: ao escolher jogadas ao contrário, ele dá preferência às que reutilizam furos já usados. As jogadas se entrelaçam e o problema dificilmente vira uma simples fila reta.
  • Acertar o formato do tabuleiro: em metade dos tabuleiros criados, são acrescentados furos para deixá-los simétricos. Nos demais, 1 ou 2 furos vazios são acrescentados na borda para mudar o formato. Mesmo com furos vazios a mais, a resposta original continua valendo, então o problema segue tendo solução.
  • Mesma semente, mesmo problema: o problema é criado a partir de um número chamado “semente”, então a mesma semente e dificuldade geram o mesmo problema no iPhone e no Android.

Medir a dificuldade e refazer se não servir

O problema criado ao contrário sempre tem resposta. Mas só isso pode deixá-lo fácil ou difícil demais.

Por isso o app examina o problema criado pela quantidade de jogadas armadilha, aquelas que, feitas no meio da resposta, impedem de salvar a bola chefe. Ele refaz o problema até 24 vezes, até que a proporção de armadilhas caia na faixa de cada nível de ★1 a ★5 (as faixas estão no artigo sobre dificuldade).

Mesmo nos problemas ★5 Grão-mestre (27 a 32 bolas), criar um leva em média cerca de 0,6 segundo no Mac usado no desenvolvimento. Além disso, são mantidos 3 problemas prontos de cada dificuldade e, quando um é usado, outro é criado em segundo plano, então quase nunca há espera.

A resposta pode não ser única

A sequência criada ao contrário é uma das respostas. É comum o mesmo tabuleiro ter várias outras. Os tabuleiros de “Treino da bola chefe” da página para jogar foram criados com a mesma ideia, e o de 16 bolas tem mais de 3 milhões de soluções (de quantas maneiras se resolve?).

A “Dica” do app guarda a resposta de quando o problema foi criado, então, enquanto você está no caminho da resposta, ela mostra logo a próxima jogada. Se você sai do caminho, um programa de busca procura outro caminho (Resolvendo com o computador).