Se você dispuser as peças ao acaso, o Shisen-Sho (“Remoção em duas curvas” em japonês) pode ficar numa disposição em que não dá para remover tudo de jeito nenhum. O app Shisen-Sho cria toda disposição de forma que sempre dê para remover todas as peças. Aqui explicamos o método de um jeito simples.
A ideia: colocar na ordem inversa da remoção
Para criar uma disposição em que dá para remover tudo, basta decidir primeiro “como remover” e seguir o caminho contrário.
- Prepare um tabuleiro vazio.
- Coloque primeiro o último par que será removido.
- Depois coloque o penúltimo par a ser removido.
- Continue assim até o primeiro par a ser removido.
Quando você coloca um par, as peças já colocadas são as que ainda estarão no tabuleiro na hora de remover esse par. As casas ainda não preenchidas são as que, na hora de remover esse par, já estarão livres, porque as peças já foram removidas. Então, considerando as peças colocadas como paredes e as casas ainda não preenchidas como livres, só se coloca o par em duas casas que se ligam por uma linha com no máximo duas curvas.
Quando termina de colocar tudo, percorrendo a ordem de colocação ao contrário, todos os pares têm a linha ligando. Isso é, ao mesmo tempo, a solução dessa disposição.
Exemplo: um tabuleiro 4×4
Com este método, criamos um tabuleiro pequeno de 16 peças (4 tipos × 4).
O último par colocado é o das duas peças de baixo, na segunda coluna da esquerda (2 de Caracteres). Por isso esse par pode ser removido primeiro (linha dourada). Percorrendo a ordem de colocação ao contrário e removendo 4 pares, o tabuleiro fica assim. O quinto a ser removido é o par de 6 de Caracteres.
Removendo assim os 8 pares em sequência, dá para remover tudo.
Um cuidado para não ficar sem lugar
Esse método tem uma armadilha. Se, no meio do caminho, restarem casas em que nenhum par de casas se liga por uma linha, não dá mais para colocar nada.
No app, para evitar isso, usa-se a seguinte propriedade:
- Duas casas lado a lado sempre se ligam (a linha tem comprimento 1, então nada a bloqueia).
- Por isso, mantém-se sempre a situação em que as casas ainda não preenchidas podem ser divididas exatamente em pares de casas vizinhas.
Se dá para dividir assim, na pior das hipóteses se coloca o par em casas vizinhas e o processo segue. O computador confere rápido se dá para dividir, tratando o problema como o de “formar pares de casas vizinhas entre casas brancas e pretas”, quando o tabuleiro é pintado como um tabuleiro de xadrez (em matemática, é o emparelhamento perfeito em grafos bipartidos). Por essa propriedade, as duas casas de um par sempre têm cores diferentes no tabuleiro de xadrez.
Sem usar só pares vizinhos
Se houvesse só pares lado a lado, daria para ver a resposta só de olhar. Por isso, a escolha de onde colocar procura primeiro, sempre que possível, duas casas afastadas.
Criando 2000 tabuleiros de 48 peças com o mesmo método do app, os pares de casas lado a lado, entre os pares da solução, foram cerca de 28%. Os outros cerca de 70% são pares afastados, removidos por linhas em L ou em U.
O embaralhamento usa o mesmo método
O embaralhamento, quando acabam os pares removíveis, usa o mesmo método. As peças restantes são recolocadas, dentro das casas onde há peças agora, na ordem inversa da remoção. Por isso, depois de embaralhar, também sempre dá para remover tudo.
Mas o que esse método garante é só que “existe pelo menos uma solução”. Se você errar a ordem de remoção, ainda pode travar. O que fazer quando isso acontece está em Ficou sem pares? Embaralhe.
