Um solver informático de nonogramas normalmente alterna entre duas tarefas: resolver linhas individuais sob as restrições atuais e propagar cada nova célula forçada para as linhas cruzadas. Se esse processo chegar a um ponto fixo antes de completar a grade, solvers mais fortes podem fazer probing de hipóteses ou ramificar pelas possibilidades restantes.
Programas diferentes implementam os detalhes de maneiras diferentes, mas a estrutura análise de linha → propagação → busca é um bom modelo para entendê-los.
1. Representar o quebra-cabeça como restrições
O solver armazena:
- as sequências de pistas das linhas;
- as sequências de pistas das colunas;
- o estado atual de cada célula: preenchida, vazia ou desconhecida.
Cada linha e coluna é um problema unidimensional: encontrar arranjos de seus blocos que sejam compatíveis com todas as células já conhecidas.
Uma grade completa só é válida quando cada linha possui pelo menos um arranjo compatível e todas as células concordam nos cruzamentos de linhas e colunas.
2. Resolver uma linha
Um solver de linha tenta determinar quais células são forçadas pelas pistas daquela linha e pelos estados já conhecidos.
Existem várias estratégias de implementação.
Uma estratégia prática, documentada pelo pbnsolve do WebPBN, encontra uma colocação legal com os blocos empurrados o máximo possível para uma extremidade e outra colocação para a extremidade oposta. Células ocupadas pelo mesmo bloco nas duas colocações extremas podem ser marcadas como preenchidas; células provadas como estando entre os mesmos blocos podem ser marcadas como vazias.
Solvers de linha mais completos podem enumerar ou calcular dinamicamente todos os padrões válidos de linha compatíveis com o estado atual e então intersectá-los.
3. Colocar as linhas cruzadas afetadas de volta na fila de trabalho
Suponha que o solver de uma linha prove que a célula R4C7 está preenchida.
A coluna 7 agora possui uma informação nova. Uma boa implementação não precisa reiniciar o quebra-cabeça inteiro às cegas; ela pode agendar essa coluna afetada para uma nova passagem.
Se a coluna então forçar células nas linhas 2 e 8, essas linhas viram candidatas a novo processamento.
Essa é a forma programática do mesmo ritmo linha-coluna usado por jogadores humanos.
4. Continuar até a propagação chegar a um ponto fixo
O solver continua processando linhas úteis até que:
- todas as células estejam determinadas;
- apareça uma contradição;
- nenhuma linha consiga produzir outra célula forçada.
O terceiro estado é um ponto fixo sob o método de resolução atual. Isso não significa automaticamente que o quebra-cabeça tenha várias soluções ou que não exista solução lógica. Significa apenas que esse mecanismo específico de inferência não consegue avançar diretamente.
Um solver de linha mais forte ainda pode encontrar um estado forçado que um solver mais barato deixou passar.
5. Detectar contradições
Uma contradição aparece quando as hipóteses atuais tornam alguma restrição impossível.
Exemplos incluem:
- uma linha não possui nenhuma colocação válida;
- um bloco confirmado é maior do que a pista correspondente;
- um bloco obrigatório não cabe em nenhum lugar;
- uma célula foi forçada simultaneamente como preenchida e vazia por ramificações incompatíveis.
Em termos de padrões, uma linha com zero padrões válidos é impossível.
Isso torna a detecção de contradições útil tanto para validar estados do jogador quanto para algoritmos de busca.
6. Usar probing ou busca quando a lógica direta trava
Um solver geral completo pode precisar explorar alternativas.
Uma abordagem simples em profundidade pode:
- escolher uma célula desconhecida ou uma decisão de bloco;
- assumir um estado legal;
- executar a propagação novamente;
- continuar se a ramificação permanecer possível;
- fazer backtracking se ela chegar a uma contradição.
Uma estratégia de probing explora hipóteses candidatas temporariamente e mede suas consequências antes de decidir qual ramificação assumir de forma definitiva. O pbnsolve do WebPBN documenta esse tipo de abordagem em detalhes.
A distinção importante é que um computador pode usar busca para garantir completude mesmo quando a lógica voltada para humanos travou.
7. Verificar unicidade
Para validar um quebra-cabeça, encontrar uma solução não basta.
Um solver pode continuar pesquisando depois da primeira solução e perguntar se existe uma segunda conclusão distinta.
Os resultados são:
- zero soluções → conjunto de pistas inconsistente;
- uma solução → único;
- duas ou mais → ambíguo.
Isso torna solvers automatizados úteis não apenas para jogar, mas também para pipelines de criação e publicação de quebra-cabeças.
Nem todo solver usa o mesmo algoritmo
Nonogramas podem ser modelados em vários frameworks computacionais.
Implementações podem combinar:
- solvers de linha personalizados;
- programação dinâmica;
- programação por restrições;
- restrições booleanas no estilo SAT;
- programação inteira;
- busca em profundidade;
- busca heurística;
- probing e cache.
Pesquisas já compararam solvers especializados e propuseram formulações matemáticas alternativas. Não existe uma única arquitetura obrigatória.
O que define a correção é o algoritmo respeitar as pistas e restrições das células e, quando afirma completude ou unicidade, pesquisar uma parte suficiente do espaço de soluções para justificar essa afirmação.
Lógica de linha rápida vs lógica de linha completa
Uma sutileza de implementação é que uma rotina de linha muito rápida pode não derivar todas as células forçadas disponíveis naquela linha.
O WebPBN observa explicitamente que sua rotina de sobreposição esquerda/direita é rápida, mas não completa; por isso o pbnsolve pode executar uma verificação mais exaustiva quando a resolução comum por linhas trava.
Isso espelha uma diferença humana:
- uma técnica visual barata pode revelar muitas células rapidamente;
- uma análise completa de padrões válidos pode revelar outras células forçadas a um custo maior.
Como um solver pode classificar dificuldade
Quando um solver registra o próprio trabalho, ele pode produzir características como:
- número de resoluções de linha;
- número de rodadas de propagação;
- inferência mais forte necessária;
- quantidade de padrões considerados;
- número de probes ou ramificações;
- profundidade máxima de busca.
Essas características podem alimentar um modelo de dificuldade, embora ainda descrevam a dificuldade em relação à arquitetura daquele solver.
Por que a resolução geral ainda pode ser difícil
Um solver especializado pode fazer nonogramas comuns de livros parecerem triviais e, ainda assim, não existe um método polinomial conhecido que resolva todas as instâncias possíveis de nonogramas, a menos que hipóteses fundamentais da teoria da complexidade colapsem.
Essa é uma afirmação sobre o pior caso, não uma afirmação de que o seu nonograma diário 15×15 deveria precisar de um supercomputador.
O que aprender a seguir
Para a teoria por trás da dificuldade no pior caso, continue em Por que os nonogramas são computacionalmente difíceis. Para o equivalente voltado a humanos de hipóteses temporárias, reveja Raciocínio por contradição.
FAQ
Solvers de nonogramas simplesmente testam todas as grades por força bruta?
Bons solvers não precisam fazer isso. Eles usam restrições de linha e propagação para eliminar enormes quantidades de possibilidades antes da busca, e muitos quebra-cabeças publicados são resolvidos sem ramificação profunda.
Um solver pode provar que um quebra-cabeça é único?
Sim, desde que execute uma busca suficientemente completa para descartar todas as soluções alternativas.
Os métodos de resolução de computadores e pessoas são os mesmos?
Eles se sobrepõem conceitualmente, principalmente em lógica de linha e propagação, mas computadores conseguem acompanhar muito mais estados candidatos e usar busca sistemática que seria tediosa para uma pessoa.