Quantas jogadas, no mínimo, são necessárias para resolver o Sort Puzzle? No tamanho do ★1 do app Sort Puzzle (4 cores, 2 vazios), dá para examinar todas as distribuições. Contamos o mínimo de jogadas de todas elas, com jogadas de “Despejar”.

Como verificamos

  • Examinamos só as “distribuições justas”, sem tubos com 3 ou mais cores iguais seguidas (o app só entrega essas).
  • Distribuições que diferem só pela ordem dos tubos ou pela troca das cores são consideradas iguais. Restam 89.675 tipos (De quantas maneiras se pode distribuir?).
  • Em cada distribuição, expandimos todas as posições alcançáveis com 1 jogada, depois com 2 jogadas… e achamos o primeiro número de jogadas em que as cores se separam (busca em largura).

Distribuição do mínimo de jogadas

Mínimo de jogadasTipos de distribuição
53
68
7124
8741
93.523
1011.070
1121.321
1226.778
1319.271
146.635
15197
164

O mais comum é 12 jogadas, e de 10 a 13 jogadas está mais de 80% do total. Só 3 tipos se resolvem em 5 jogadas e só 4 tipos exigem 16.

(Os números aqui são “tipos”. A chance de cada um sair de fato no app é um pouco diferente de tipo para tipo.)

O tabuleiro mais curto (5 jogadas)

123456
Jogada 1: 3→5 (2)
123456
Jogada 2: 1→3 (2)
123456
Jogada 3: 4→5 (2)
123456
Jogada 4: 2→4 (2)
123456
Jogada 5: 1→2 (2)
123456
Separado

Em todos os tubos, as cores iguais estão em pares. Usando os 2 tubos vazios, as cores se separam em 5 jogadas.

O tabuleiro que exige mais jogadas (16)

123456

Os tubos 1 e 2, e também os 3 e 4, têm exatamente a mesma ordem. Em todos os tubos, as cores vizinhas são sempre diferentes, e o vermelho e o verde-limão ficam, cada um, no fundo de 2 tubos.

Ver as 16 jogadas
123456
Jogada 1: 1→5
123456
Jogada 2: 1→6
123456
Jogada 3: 2→5
123456
Jogada 4: 2→6
123456
Jogada 5: 1→2
123456
Jogada 6: 1→5
123456
Jogada 7: 2→1 (2)
123456
Jogada 8: 2→5
123456
Jogada 9: 3→2
123456
Jogada 10: 3→6
123456
Jogada 11: 3→1
123456
Jogada 12: 2→3
123456
Jogada 13: 4→3
123456
Jogada 14: 4→6
123456
Jogada 15: 4→1
123456
Jogada 16: 3→4 (3)
123456
Separado

Como achar um limite inferior

Sem examinar tudo, só olhando o tabuleiro, dá para achar um limite inferior (um número abaixo do qual não se consegue).

  1. Conte as quebras de cor dentro dos tubos.
  2. Se a mesma cor está no fundo de vários tubos, some “esse número menos 1”.

Essa soma diminui no máximo 1 a cada despejo, então nunca passa do mínimo de jogadas (Resolver com o computador).

  • Tabuleiro de 5 jogadas: 4 quebras e vermelho no fundo de 2 tubos, soma-se 1, e o limite é 5. É exatamente o mínimo.
  • Tabuleiro de 16 jogadas: 12 quebras e vermelho e verde-limão no fundo de 2 tubos cada, soma-se 2, e o limite é 14. Na prática, leva 16.

Dos 89.675 tipos, em 38.571 (cerca de 43%) o limite inferior coincidiu exatamente com o mínimo. Nos demais, leva mais do que o limite.

Em tabuleiros maiores

Com mais cores, há distribuições demais para examinar todas. A média do mínimo de jogadas em 20 problemas de cada, criados do mesmo jeito que o app, foi de 11,8 no ★1 e de 18,1 no ★2 (6 cores). Do ★3 em diante, só calcular o mínimo de um problema já leva tempo.

A “Dica” do app mostra uma solução que se acha rápido, e não o mínimo de jogadas. Se quiser desafiar o mínimo, use o limite inferior como referência e pense a sequência por conta própria (como usar a dica).