Guia de estratégias

Use as regras para eliminar possibilidades. Marque ✕ quando tiver certeza de que uma célula não pode receber gato; guarde seus palpites para quando a lógica não avançar.

Documentação Algorítmica

Este artigo explica, passo a passo, como o MeowColor gera tabuleiros infinitos e válidos. O código correspondente está em engine.js.

1. O problema

Dado um tabuleiro N × N dividido em N regiões coloridas conexas, devemos colocar exatamente N gatos tais que:

• há exatamente um gato em cada linha;
• há exatamente um gato em cada coluna;
• há exatamente um gato em cada região;
• dois gatos nunca se tocam, nem na diagonal (vizinhança de 8 direções).

Isso é uma instância do Problema da Cobertura Exata (Exact Cover): temos um conjunto de "restrições" (linha 0, linha 1, ..., coluna 0, ..., região 0, ...) e cada posição candidata (r, c) cobre três restrições ao mesmo tempo (sua linha, sua coluna e sua região). Queremos escolher posições de modo que cada restrição seja coberta exatamente uma vez. A restrição de não-adjacência é uma regra extra de exclusão entre candidatas.

O algoritmo clássico para Cobertura Exata é o Algoritmo X de Knuth, implementado com Dancing Links (listas duplamente encadeadas circulares que permitem remover e restaurar colunas em O(1)). Para tabuleiros tão pequenos (N ≤ 10), um backtracking direto, especializado, é mais simples e mais que suficiente.

2. Backtracking: posicionando os gatos

A ideia

Backtracking é uma busca em profundidade sobre o espaço de decisões. Construímos a solução aos poucos; se uma escolha parcial leva a um beco sem saída, desfazemos a última decisão e tentamos outra.

Como foi montado

Em vez de testar todas as N² células, usamos a restrição "um gato por linha" para embutir a regra na estrutura: a recursão decide a coluna do gato de cada linha, uma linha por nível. O estado é só um vetor cols[row]. Assim, "uma por linha" é garantido por construção, e só verificamos:

1. Coluna livre: um Set (usedCols) com as colunas já usadas — teste O(1).
2. Sem toque: como a linha anterior é a única que pode ser vizinha, basta |cols[row-1] − c| > 1. Isso cobre diagonais e a vertical (a vertical já é barrada pela coluna).

solve(row):
  se row == N: retorne verdadeiro            // caso base
  para cada coluna c (em ordem aleatória):
      se c usada ou encosta na linha anterior: continue
      cols[row] = c; marque c                // ESCOLHE
      se solve(row + 1): retorne verdadeiro  // EXPLORA
      desmarque c; cols[row] = -1            // DESFAZ (backtrack)
  retorne falso                              // beco sem saída

Aleatoriedade: embaralhamos a ordem das colunas (Fisher-Yates) a cada nível, assim cada chamada produz uma configuração diferente — origem dos "níveis infinitos".

Complexidade: no pior caso é O(N!) (o número de permutações), porém a poda pela regra de adjacência corta a árvore drasticamente; para N ≤ 10 é instantâneo.

3. Como as regiões coloridas são criadas

Desenhar regiões primeiro e depois procurar gatos seria difícil: quase nenhum mapa teria solução. Fazemos o processo inverso: com os gatos já posicionados, cada gato vira a semente de uma região, que então cresce até cobrir o tabuleiro. A solução existe por construção — cada região contém exatamente o gato que a originou.

O algoritmo (crescimento multi-fonte, estilo Flood Fill / BFS randomizada)

1. Crie uma matriz regions preenchida com -1 ("livre").
2. Para cada gato na linha r, marque regions[r][col] = r e coloque a célula na fronteira da região r.
3. Enquanto restarem células livres: sorteie uma região; sorteie uma célula da fronteira dela; olhe os 4 vizinhos ortogonais; se algum estiver livre, sorteie um e anexe-o à região (e à fronteira). Se nenhum estiver livre, remova a célula da fronteira.

Um Flood Fill comum pinta uma área a partir de um ponto. Aqui rodamos N preenchimentos em paralelo e competindo pelas mesmas células; a escolha aleatória de região e vizinho dá formas orgânicas e irregulares. Como só anexamos células adjacentes a algo já na região, cada região é garantidamente conexa. O laço termina porque cada iteração ou pinta uma célula nova ou reduz a fronteira.

As cores vêm de uma paleta indexada pelo id da região; as bordas grossas são desenhadas onde o vizinho tem id diferente.

4. Garantindo solução única

Um mapa gerado dessa forma pode ter mais de uma solução válida, o que frustra o jogador. Por isso, depois de gerar as regiões, rodamos countSolutions: o mesmo backtracking, agora com a restrição extra de região (usedRegs), que para ao encontrar 2 soluções. Se o total for 1, o nível é aceito; senão, geramos outro (até 300 tentativas). Esse é o padrão "gerar e testar".

5. Grafos

5.1 O que é um grafo?

Um grafo G = (V, E) é formado por um conjunto de vértices (ou nós) V e um conjunto de arestas E, cada uma ligando dois vértices. Pense em cidades (vértices) e estradas (arestas), pessoas e amizades, páginas web e links.

• Não-direcionado: a aresta vale nos dois sentidos (amizade). Direcionado: tem sentido (seguir alguém).
• Ponderado: as arestas têm custo (distância). Não-ponderado: todas valem o mesmo.
• Grau de um vértice: número de arestas incidentes.
• Caminho: sequência de vértices ligados por arestas. Ciclo: caminho que volta ao início.
• Conexo: existe caminho entre quaisquer dois vértices. Componente conexa: pedaço máximo conexo.
• Árvore: grafo conexo sem ciclos. DAG: grafo direcionado acíclico.

5.2 Como representar um grafo no computador

5.3 Modelando uma matriz 2D como um grafo

O tabuleiro do MeowColor é um grafo-grade (grid graph):

• cada célula (r, c) é um vértice;
• há uma aresta entre células vizinhas: cima, baixo, esquerda, direita (conectividade-4). Com as diagonais, seria conectividade-8.

Note que não construímos a lista de adjacência. Ela é implícita: os vizinhos de (r, c) são calculados na hora somando os deslocamentos [[1,0],[-1,0],[0,1],[0,-1]] e descartando o que sai dos limites. Isso economiza memória e é o truque padrão em problemas de grade.

Exemplo 3×3 — os vértices e as arestas do centro:

(0,0)─(0,1)─(0,2)
  │     │     │
(1,0)─(1,1)─(1,2)      vizinhos de (1,1): (0,1), (2,1), (1,0), (1,2)
  │     │     │
(2,0)─(2,1)─(2,2)      grau: cantos = 2, bordas = 3, centro = 4

Uma região colorida do jogo é exatamente uma componente conexa de um subgrafo: o conjunto de células com o mesmo id, ligadas por vizinhança.

5.4 DFS e BFS: percorrendo o grafo

Ambos visitam todos os vértices alcançáveis a partir de uma origem, usando um conjunto visitado para não repetir. Diferem na estrutura que guarda os "próximos":

BFS(origem):
  fila = [origem]; visitado = {origem}
  enquanto fila não vazia:
      u = fila.remove_primeiro()
      para cada vizinho v de u:
          se v não visitado: marque v; fila.adicione(v)

5.5 Como isso cria as regiões do jogo

Nosso crescimento de regiões é uma BFS/DFS multi-fonte: em vez de uma origem, temos N (os gatos). Cada região possui sua própria fronteira (o equivalente da fila/pilha). Se sempre retirássemos o primeiro elemento da fronteira, teríamos BFS pura: regiões em forma de "losangos" crescendo por camadas. Se sempre retirássemos o último, tenderíamos a DFS: regiões compridas e tortuosas. Sortear o elemento da fronteira (nosso caso) mistura os dois comportamentos e produz formas orgânicas.

E o backtracking da seção 2? Ele também é uma DFS — não sobre a grade, mas sobre o grafo de estados da busca (cada vértice é uma configuração parcial; as arestas são "colocar um gato na próxima linha"). Retroceder é voltar na DFS. Grafos aparecem em todo lugar, mesmo quando não estão desenhados.

5.6 Aplicações além do jogo

• Mapas e GPS (Dijkstra, A*), redes sociais (recomendação, comunidades).
• Compiladores e builds (ordenação topológica de dependências).
• Redes de computadores, roteamento e fluxo máximo.
• Editores de imagem ("balde de tinta" é um Flood Fill), IA de jogos.

6. Guia para iniciantes: como começar a estudar Teoria dos Grafos

1. Pré-requisitos: arrays/listas, laços, funções, recursão, e noções de conjuntos, mapas (dicionários), pilha e fila.
2. Vocabulário: vértice, aresta, grau, caminho, ciclo, conexo, árvore, direcionado, ponderado.
3. Representações: implemente uma lista de adjacência e uma matriz de adjacência à mão, em sua linguagem favorita.
4. BFS e DFS: o alicerce de tudo. Pratique em grades: contar ilhas, labirinto (menor caminho com BFS), flood fill, componentes conexas.
5. Aplicações diretas: detecção de ciclo, ordenação topológica, verificação de grafo bipartido (2-coloração).
6. Caminhos mínimos: BFS (sem pesos) → Dijkstra (pesos não-negativos, com fila de prioridade) → Bellman-Ford → Floyd-Warshall.
7. Árvores geradoras mínimas: Kruskal (com Union-Find/DSU) e Prim.
8. Tópicos avançados: componentes fortemente conexas (Tarjan/Kosaraju), fluxo máximo (Ford-Fulkerson/Dinic), emparelhamento, LCA.
9. Prática constante: resolva 2–3 problemas por semana em LeetCode, Codeforces, AtCoder, CSES ou URI/beecrowd, sempre começando pelos tags "graph", "bfs" e "dfs".
10. Material: Introduction to Algorithms (CLRS, cap. 20-22), Algorithms (Sedgewick & Wayne), Competitive Programmer's Handbook (gratuito), visualizações em visualgo.net.

Exercício sugerido: altere growRegions para sempre tirar a primeira célula da fronteira (BFS pura) e depois a última (DFS-like), e observe como o formato das regiões muda.