Os problemas do app Sort Puzzle não são prontos: são criados na hora, a cada jogo. Mesmo assim, todos só são entregues depois de confirmarmos que têm solução. Aqui está como isso é feito.
Passos da criação
- Escolher as cores: entre as 10 cores, escolhe-se tantas quanto a dificuldade pede (4 no ★1).
- Misturar e distribuir: juntam-se 4 peças de cada cor escolhida, misturam-se e enchem-se os tubos de cores com 4 peças cada. Os tubos vazios ficam à direita.
- Descartar tubos quase prontos: se algum tubo tiver 3 ou mais cores iguais seguidas, a distribuição não é usada. Um tubo quase pronto desde o começo é sem graça.
- Conferir se tem solução: o solucionador do computador procura a sequência até que tudo esteja separado. Se não achar, a distribuição não é usada.
- Ver a condição de armadilha: do ★3 em diante, verifica-se se há uma “armadilha” que trava quando se escolhe sempre a jogada que parece boa na hora, e redistribui-se até atender à condição da dificuldade (problemas com armadilhas).
A cada problema, o app repete esses passos até achar uma distribuição que atenda às condições. Mesmo no ★5, criar um problema leva, no máximo, algumas dezenas de milissegundos.
Quantas distribuições aleatórias têm solução?
Quantas distribuições são descartadas no passo 4? Distribuímos do mesmo jeito que o app e, entre as “distribuições sem tubo com 3 ou mais cores iguais seguidas” (distribuições justas), conferimos todas para ver se têm solução.
| Dificuldade | Distribuições justas | Com solução |
|---|---|---|
| ★1 (4 cores, 2 vazios) | 416 | 416 |
| ★2 (6 cores, 2 vazios) | 431 | 431 |
| ★3 (8 cores, 2 vazios) | 453 | 453 |
| ★4 (10 cores, 2 vazios) | 460 | 460 |
| ★5 (9 cores, 1 vazio) | 4539 | 29 |
No ★1 ao ★4, que têm dois tubos vazios, todas as distribuições justas contadas tinham solução. Já no ★5, com um tubo vazio, só 29 de 4539 (0,64%) tinham solução. As demais são distribuições que não se resolvem de jeito nenhum.
Com um tubo vazio, de repente quase nada tem solução
Contamos também como muda a proporção com solução conforme o número de cores, com um tubo vazio.
| Número de cores (1 vazio) | Proporção com solução |
|---|---|
| 3 cores | 72,7% |
| 4 cores | 44,9% |
| 5 cores | 26,3% |
| 6 cores | 14,0% |
| 7 cores | 6,0% |
| 8 cores | 2,3% |
| 9 cores | 0,64% |
A cada cor a mais, a proporção com solução cai para cerca da metade, e com muitas cores cai ainda mais depressa. Com um só tubo vazio, a primeira jogada só pode ir para o tubo vazio e há poucos caminhos a escolher depois, o que provavelmente explica (Como resolver o ★5 (1 tubo vazio)).
Como se cria o ★5
No ★5, distribuições com solução são raras, então o app redistribui até 400 vezes. Se mesmo assim não achar, muda de método.
- Desmanchar um tabuleiro pronto: parte-se de um tabuleiro com as cores já separadas e desmancha-se ao acaso com jogadas no sentido contrário. Como refazer as jogadas de trás para frente sempre separa as cores, garante-se que tem solução.
Criando 500 problemas ★5 do mesmo jeito que o app, 18 deles eram esses “tabuleiros desmanchados”. Um tabuleiro desmanchado pode ter tubos que não estão cheios com 4 peças.
A mesma semente dá o mesmo problema
O gerador de números aleatórios da criação de problemas (SplitMix64) produz sempre a mesma sequência quando se fixa um número, a “semente”. Da mesma semente sai o mesmo problema. O tabuleiro de Jogar no navegador deste site também cria problemas pelo mesmo procedimento do app.
O funcionamento do solucionador que confere se há solução está em Resolver com o computador.
