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 jogadas | Tipos de distribuição |
|---|---|
| 5 | 3 |
| 6 | 8 |
| 7 | 124 |
| 8 | 741 |
| 9 | 3.523 |
| 10 | 11.070 |
| 11 | 21.321 |
| 12 | 26.778 |
| 13 | 19.271 |
| 14 | 6.635 |
| 15 | 197 |
| 16 | 4 |
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)
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)
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
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).
- Conte as quebras de cor dentro dos tubos.
- 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).
