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.

  1. 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).
  2. Para cada peça ainda não usada, testar todas as direções e verificar se ela pode ser colocada cobrindo essa casa.
  3. Se for possível colocar, passar para a próxima casa vazia (voltar ao passo 1).
  4. Se nenhuma peça puder ser colocada, retirar a última peça colocada e testar o próximo candidato.
  5. 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ó.