Toda vez que você escolhe duas peças, o app de Shisen-Sho (“Remoção em duas curvas” em japonês) decide se elas se ligam por uma linha com no máximo duas curvas. Quando a dica procura um par removível, ela usa a mesma decisão para todos os pares. Neste artigo mostramos esse mecanismo em forma de programa.
A ideia: ampliar a cada curva
Uma linha anda em linha reta na vertical ou na horizontal e, de vez em quando, faz uma curva. Por isso, a partir da primeira peça, o programa confere assim:
- 0 curvas: da primeira peça, anda em linha reta para cima, baixo, esquerda e direita por casas livres. Se chegar à segunda peça, elas se ligam.
- 1 curva: de cada casa alcançada no passo 1, muda de direção e anda em linha reta de novo.
- 2 curvas: de cada casa alcançada no passo 2, muda de direção e anda em linha reta mais uma vez.
Se até o terceiro passo não chegar à segunda peça, elas não se ligam com no máximo duas curvas. Cada trecho reto vai até bater numa peça ou sair do tabuleiro.
Como tratar o lado de fora do tabuleiro
A linha também pode passar pela faixa de uma casa por fora do tabuleiro. No programa, basta usar um tabuleiro com uma volta de casas livres a mais em torno, e o lado de fora passa a ser tratado como casas livres comuns. Num tabuleiro de 6 colunas por 8 linhas, a conferência é feita num tabuleiro de 8 colunas por 10 linhas.
Os dois 5 de Bambu nas pontas da fileira de cima da figura se ligam com 2 curvas, passando pelas casas livres de fora, em cima.
O programa
Em JavaScript, fica assim.
// board[r][c] é o nome da peça, e casa livre é null. Há uma volta de casas livres a mais em torno do tabuleiro.
function canConnect(board, from, to) {
const rows = board.length;
const cols = board[0].length;
const steps = [[0, 1], [0, -1], [1, 0], [-1, 0]];
// Casa atual e última direção percorrida (no início, -1)
let frontier = [[from[0], from[1], -1]];
const seen = new Set();
for (let turn = 0; turn <= 2; turn++) {
const next = [];
for (const [r0, c0, dir] of frontier) {
for (let d = 0; d < 4; d++) {
if (d === dir) continue;
let r = r0;
let c = c0;
while (true) {
r += steps[d][0];
c += steps[d][1];
if (r < 0 || c < 0 || r >= rows || c >= cols) break;
if (r === to[0] && c === to[1]) return true;
if (board[r][c] !== null) break;
const key = r + ',' + c + ',' + d;
if (!seen.has(key)) {
seen.add(key);
next.push([r, c, d]);
}
}
}
}
frontier = next;
}
return false;
} boardé o tabuleiro com a volta de casas livres a mais. Nas casas com peça está o nome da peça, e nas casas livres estánull.frometosão[linha, coluna]das duas peças (posição no tabuleiro com a volta a mais).frontieré a lista das casas que se alcançam com o número atual de curvas, com a direção em que se chegou a elas.- Andar de novo na mesma direção já foi conferido na rodada anterior, então é pulado (
d === dir). seenguarda que se chegou à mesma casa na mesma direção, para não repetir a mesma conferência.
Este programa confere também, depois da segunda curva, se andando em linha reta se chega à segunda peça. Não dá para passar por cima de peças, então ele para ao bater numa (só a segunda peça é decidida no ponto em que se chega a ela).
Conferência com o app
Comparamos este programa com a busca de linhas do app (o mesmo cálculo usado nas figuras do site). Geramos 300 tabuleiros de 48 peças feitos como no app, incluindo tabuleiros em que parte das peças já tinha sido removida, e pedimos a decisão para 5044 pares de peças escolhidos ao acaso. As respostas “liga” e “não liga” coincidiram em todos.
No app, quando as peças se ligam, a linha é desenhada na tela, então não se guarda só se ligam, mas também a posição das curvas. Quando há várias linhas possíveis, ele desenha a que tem menos curvas e, em caso de empate, a mais curta.
Para procurar todos os pares removíveis
Quando se procuram pares removíveis, como na dica, o programa decide cada par de peças iguais. No tabuleiro de 48 peças, as combinações de peças iguais são 72, então bastam no máximo 72 decisões. A quantidade de pares removíveis no início está contada em Quantos pares dá para remover no começo?.
