O quebra-cabeça de blocos também pode ser resolvido pelo computador. Neste artigo mostramos o jeito mais básico.
A ideia: começar pela casa vazia do canto superior esquerdo
O computador repete estes passos.
- Procurar, na moldura, a casa vazia mais acima e à esquerda (olhando da linha de cima para baixo e, em cada linha, da esquerda para a direita).
- Para cada peça ainda não usada, testar todas as direções e verificar se ela pode ser colocada cobrindo essa casa.
- Se for possível colocar, passar para a próxima casa vazia (voltar ao passo 1).
- Se nenhuma peça puder ser colocada, retirar a última peça colocada e testar o próximo candidato.
- Quando não houver mais casas vazias, uma solução foi encontrada.
A casa vazia mais acima e à esquerda sempre é coberta pela casa mais acima e à esquerda de alguma peça. Por isso, basta testar as colocações em que essa casa da peça coincide com ela; não é preciso testar as outras posições.
No diagrama acima, depois de colocar a primeira peça, a casa vazia mais acima e à esquerda é a da 2ª linha, 1ª coluna (anel dourado). Agora só se testam as colocações que cobrem essa casa.
Esse jeito de procurar, avançando até onde der e voltando para tentar outro caminho quando não dá, se chama busca em profundidade (backtracking).
Em JavaScript
A moldura é uma tabela de true (vazio) e false (preenchido), e a peça é uma lista de [linha, coluna] das casas. As casas da peça ficam em ordem, da linha de cima para baixo e, em cada linha, da esquerda para a direita.
// Moldura: true é casa vazia. Peça: lista de [linha, coluna] das casas
function rotate(shape) {
const turned = shape.map(([r, c]) => [c, -r]);
const minR = Math.min(...turned.map(([r]) => r));
const minC = Math.min(...turned.map(([, c]) => c));
return turned
.map(([r, c]) => [r - minR, c - minC])
.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
}
function solve(frame, pieces) {
const rows = frame.length;
const cols = frame[0].length;
const used = pieces.map(() => false);
let count = 0;
function search() {
// Procura a casa vazia mais acima e à esquerda
let at = -1;
for (let i = 0; i < rows * cols && at < 0; i++) {
if (frame[Math.floor(i / cols)][i % cols]) at = i;
}
if (at < 0) {
count++; // Tudo preenchido
return;
}
const r0 = Math.floor(at / cols);
const c0 = at % cols;
pieces.forEach((piece, p) => {
if (used[p]) return;
let shape = piece;
const seen = new Set();
for (let turn = 0; turn < 4; turn++, shape = rotate(shape)) {
const key = JSON.stringify(shape);
if (seen.has(key)) continue;
seen.add(key);
// Alinha a casa mais acima e à esquerda da forma com a casa vazia
const [dr, dc] = shape[0];
const cells = shape.map(([r, c]) => [r - dr + r0, c - dc + c0]);
const fits = cells.every(
([r, c]) => r >= 0 && r < rows && c >= 0 && c < cols && frame[r][c]
);
if (!fits) continue;
cells.forEach(([r, c]) => (frame[r][c] = false));
used[p] = true;
search();
used[p] = false;
cells.forEach(([r, c]) => (frame[r][c] = true));
}
});
}
search();
return count;
} Passando para solve uma moldura 4×5 e as 5 peças P, T, L, S e L de 3 casas, o resultado é 8. Ou seja, o exemplo do artigo sobre como resolver tem 8 soluções, contando as direções das peças.
Voltar cedo
O código acima avança até não poder mais colocar peças. Mas, no momento em que surge um espaço pequeno e isolado, já se sabe que adiante não há solução.
A cada peça colocada, verifica-se o tamanho dos blocos de casas vazias e, se surgir um bloco de tamanho que as peças restantes não conseguem formar, volta-se logo. Só isso reduz bastante o número de buscas.
Ao contar todas as soluções dos 12 pentaminós num retângulo 3×20, antes dessa melhoria o programa não terminava em 10 minutos. Com ela, terminou em cerca de 6 segundos (cálculo feito ao escrever os artigos deste site; o tempo varia conforme o computador).
Como funciona a “Dica” do app
A “Dica” do app “Encaixe blocos” também usa a mesma busca em profundidade.
- Testa só as colocações que cobrem a casa vazia de menor número.
- Das peças de formato igual (que coincidem ao girar), testa só uma.
- Volta quando surge um espaço isolado menor do que uma peça.
- Limita o número de situações examinadas, para não demorar demais.
Se a colocação atual permite preencher tudo, faz brilhar a peça e a colocação para a casa vazia mais difícil de preencher. Se não permite, compara com a solução criada no início, faz brilhar as peças que não conferem e avisa: “Tire a peça que está brilhando para voltar ao caminho certo”.
Como os problemas são criados está em como criamos problemas que sempre têm solução, e o número de soluções dos 12 pentaminós, em soluções do pentaminó.
