Antes de entregar um problema, o app Sort Puzzle confere com o computador se ele tem solução. A próxima jogada da “Dica” também é a primeira de uma sequência achada pelo mesmo solucionador. Aqui está como ele funciona.

Seguindo posições e jogadas

O estado do tabuleiro do Sort Puzzle (que cores há em cada tubo) se chama posição. Fazer uma jogada leva a outra posição. Seguindo as jogadas a partir da posição inicial, se você chega a uma posição com tudo separado, o caminho percorrido é a resposta.

O jeito mais direto de buscar é a busca em largura: examina todas as posições a 1 jogada, depois todas a 2 jogadas, e assim por diante. Ela sempre acha a resposta com o mínimo de jogadas, mas, com muitas cores, o número de posições a examinar fica enorme.

Estimando a “distância” até a solução

Por isso, o app estima, para cada posição, a distância até a solução e examina primeiro as que parecem mais perto. A estimativa é a soma destas duas coisas:

  1. Número de quebras de cor nos tubos: quantos pontos, olhando de baixo para cima, onde a cor muda.
  2. Sobreposição de fundos: se a mesma cor está no fundo de vários tubos, esse número menos 1.
123456

Neste tabuleiro, as quebras de cor são 2 no tubo 1, 2 no tubo 2, 3 no tubo 3 e 3 no tubo 4, 10 no total. O azul-claro está no fundo dos tubos 3 e 4, então a sobreposição de fundos é 1. A estimativa é 11. Em uma posição com tudo separado, não há quebras nem sobreposição, então a estimativa é 0.

A estimativa nunca passa do mínimo de jogadas

Essa estimativa tem uma boa propriedade: numa jogada, ela nunca diminui mais que 1.

  • Em cada despejo, as quebras do tubo de origem diminuem no máximo 1. Como o destino é em cima da mesma cor ou um tubo vazio, as quebras dele não aumentam nem diminuem.
  • A sobreposição de fundos só diminui 1 quando o último trecho de um tubo é movido e ele fica vazio, e nesse caso as quebras não diminuem.

Ou seja, um tabuleiro com estimativa 11 leva no mínimo 11 jogadas. Examinando mais de 120 mil jogadas em vários tabuleiros, não houve nenhuma que reduzisse a estimativa em 2 ou mais. O mínimo de jogadas do tabuleiro acima é exatamente 11.

Busca A* com peso

O app dá a cada posição uma pontuação, “jogadas até aqui + 3 × estimativa”, e examina primeiro as de pontuação menor. Isso se chama busca A* (A-estrela) com peso.

  • Com peso 1 (a busca A* comum), como a estimativa é um limite do mínimo de jogadas, sempre se acha a resposta com o mínimo de jogadas.
  • Com peso 3, examinam-se logo as posições de estimativa baixa e a resposta aparece bem mais rápido. Em troca, a resposta pode ter um pouco mais de jogadas que o mínimo.

Criando 20 problemas de cada, do mesmo jeito que o app, comparamos o número de posições examinadas até resolver e o número de jogadas da resposta (não contamos a busca em largura do ★3, porque as posições são demais).

★1 (4 cores, 2 vazios)Posições examinadasJogadas da resposta
Busca em largura53711,8
A* (peso 1)20311,8
A* (peso 3)3911,9
★2 (6 cores, 2 vazios)Posições examinadasJogadas da resposta
Busca em largura293418,1
A* (peso 1)62218,1
A* (peso 3)6418,8

Em ambas, é a média dos 20 problemas. Com peso 3, a resposta saiu examinando algumas dezenas de vezes menos posições que a busca em largura, e o aumento de jogadas foi pequeno.

Truques para examinar menos jogadas

O solucionador do app reduz ainda mais as posições examinadas com estas ideias.

  • Não distinguir a ordem dos tubos: se o conteúdo dos tubos é o mesmo, a posição é tratada como a mesma, mesmo com a ordem diferente.
  • Não examinar jogadas sem sentido: descarta-se mover um tubo de uma cor só para um tubo vazio (a forma não muda) e mover para o segundo tubo vazio em diante (dá a mesma posição que o primeiro).
  • Buscar só com jogadas de “Despejar”: mesmo nos problemas de “Empilhar”, confere-se se se resolve com despejos (diferença entre Despejar e Empilhar).
  • Definir um limite: se não achar depois de examinar 60 mil posições, responde “não sei” e essa distribuição não é usada.

Esse solucionador cumpre ao mesmo tempo a “conferência de que tem solução” na criação de problemas (como criar problemas que sempre têm solução) e a “Dica” (como usar a dica). A ideia do fundo dos tubos também aparece em Por qual cor começar?.