O puzzle de pentaminós é modelado como um grafo implícito de estados. Cada nó é um estado (PuzzleState) contendo o tabuleiro parcial e as peças usadas. Cada aresta representa o posicionamento válido de uma peça em uma orientação e posição. Resolver o puzzle equivale a encontrar um caminho do estado inicial (tabuleiro vazio) até um estado final (tabuleiro completo).

Matriz Cell[][] onde cada célula é "." (vazia) ou o ID da peça que a cobre. Funções principais: makeBoard, canPlace, placePiece,removePiece, isComplete, regionsDivisibleBy5.

As 12 pentaminós (F, I, L, N, P, T, U, V, W, X, Y, Z) são definidas por coordenadas relativas. Cada peça contém todas as orientações únicas pré-computadas.

rotate(shape) aplica (r,c) → (c, -r). reflect(shape) aplica (r,c) → (r, -c).normalize(shape) traduz para origem e ordena. generateOrientationscombina 4 rotações × 2 reflexões e remove duplicatas via shapeKey.

Pilha explícita; expande o último estado inserido. Verifica AVL antes de inserir filhos (poda por estado já visto). Respeita MaxStates, registra profundidade máxima e pico da pilha. Para se findAll=false ao achar primeira solução.

Fila FIFO; explora nível a nível, garantindo solução de menor profundidade. Mesma poda via AVL e mesmas métricas que DFS, mais o pico da fila.

Árvore AVL implementada do zero (arquivo core/avl.ts). Nós contêm chave string e altura. Rotações simples (LL, RR) e duplas (LR, RL). Métricas internas: insertions, searches, rotations,size, height(). A AVL garante busca O(log n) para detectar estados visitados, evitando explosão combinatória.

Cada estado é serializado de forma determinística:linha0/linha1/.../linhaN|peca1,peca2,.... A ordenação das peças usadas garante chaves únicas para estados equivalentes.

Tabuleiros maiores que 6×10 sem heurística costumam estourar MaxStates. A heurística "primeira célula vazia" reduz drasticamente o fator de ramificação, pois força que a próxima peça cubra a célula vazia mais à esquerda/topo. A poda por região (regiões vazias com tamanho não múltiplo de 5 são impossíveis) também reduz estados gerados.

DFS atinge profundidade máxima rapidamente e tende a achar uma solução com menos memória (pilha O(profundidade)). BFS garante solução de menor profundidade mas armazena toda a "fronteira", crescendo exponencialmente. Para encontrar QUALQUER solução de pentaminós, DFS é tipicamente mais eficiente em memória; BFS é melhor para análises de grafo por níveis. A página Laboratório mostra esses números lado a lado.

O maior desafio foi controlar a explosão de estados. Soluções aplicadas: AVL para deduplicação O(log n), poda por regiões inválidas, heurística opcional de primeira célula vazia, e parâmetro MaxStates com mensagem clara de interrupção.

Assistente de IA foi usado para apoio na estruturação do projeto, revisão das funções de rotação/reflexão e na geração da UI. Toda a lógica algorítmica (AVL, DFS, BFS, geração de vizinhos) foi implementada explicitamente e revisada manualmente.