O problema geral dos nonogramas é computacionalmente difícil: resultados formais demonstram NP-completude para formulações padrão de decisão, e pesquisas posteriores descrevem com frequência a resolução geral de nonogramas como NP-hard.
Isso não significa que todo nonograma seja difícil, que computadores não consigam resolvê-los ou que um quebra-cabeça 10×10 precise de tempo exponencial na prática. A teoria da complexidade descreve o comportamento das instâncias mais difíceis à medida que o tamanho do problema cresce.
Qual problema a teoria da complexidade está analisando?
Um resultado de complexidade precisa de uma pergunta computacional precisa.
Uma versão simplificada de decisão é:
Dadas as pistas das linhas e colunas de um nonograma, existe pelo menos uma grade preenchida/vazia que satisfaça todas elas?
Uma grade completa proposta pode ser verificada de forma eficiente: basta percorrer cada linha e coluna e comparar os comprimentos dos seus blocos com as pistas.
A parte difícil é encontrar uma solução ou decidir se ela existe para todos os conjuntos possíveis de pistas.
O que NP-completo significa aqui?
De forma informal, um problema de decisão é NP-completo quando:
- uma solução proposta pode ser verificada de forma eficiente; e
- o problema é pelo menos tão difícil quanto todos os problemas da classe de complexidade NP por meio de reduções em tempo polinomial.
O relatório técnico de Ueda e Nagao de 1996 estabeleceu resultados de NP-completude para nonogramas usando reduções parcimoniosas. Pesquisas posteriores sobre nonogramas citam esse resultado ao discutir a dificuldade do problema geral.
Você não precisa de teoria da complexidade para jogar. O resultado importa porque explica por que não se pode esperar que uma simples coleção de truques locais resolva eficientemente toda instância possível.
NP-completo não significa “sempre difícil”
Esse é o erro de interpretação mais importante a evitar.
Sudoku, SAT e muitos outros problemas NP-completos possuem enormes famílias de instâncias fáceis. Com nonogramas acontece o mesmo.
Editoras de quebra-cabeças constroem deliberadamente instâncias com estrutura útil:
- pistas informativas;
- sobreposições fortes;
- propagação produtiva entre linhas e colunas;
- gargalos controlados;
- frequentemente, um caminho lógico amigável para humanos.
Batenburg e Kosters contrastam explicitamente os nonogramas comuns de livros, muitas vezes resolvíveis por raciocínio local repetido de linhas, com o problema geral difícil.
Por que o espaço de busca pode ficar tão grande?
Cada linha pode admitir vários arranjos legais. Em uma grade, essas escolhas interagem por meio das células compartilhadas.
Uma decisão que parece legal em uma linha pode restringir várias colunas; essas colunas restringem outras linhas; e uma contradição pode aparecer somente depois de uma cadeia longa.
No pior caso, um solver pode precisar distinguir entre muitas combinações de padrões de linha ou ramificar entre alternativas.
O número bruto de grades binárias completas já é enorme: uma grade r × c possui 2^(r·c) atribuições preenchida/vazia antes que as pistas eliminem a maior parte delas.
Bons solvers nunca enumeram tudo isso às cegas, mas o número ilustra por que restrições e poda são importantes.
Por que a lógica de linha resolve tantos quebra-cabeças reais
Nonogramas feitos por humanos não são instâncias aleatórias de pior caso.
Criadores normalmente querem um quebra-cabeça que revele uma imagem reconhecível e possa ser resolvido com deduções satisfatórias. Essa pressão de design seleciona estruturas que o raciocínio comum de linha consegue explorar.
Um solver pode repetir:
- resolver linhas restringidas;
- transferir células forçadas para as colunas;
- resolver as colunas alteradas;
- propagar novamente.
Para muitos quebra-cabeças publicados, isso é suficiente.
A teoria da complexidade diz apenas que algumas entradas válidas escapam de toda estratégia universalmente eficiente, assumindo a conjectura padrão P ≠ NP.
O que NP-hard significa em comparação com NP-completo?
Você encontrará os dois termos na literatura sobre nonogramas.
- NP-hard significa que um problema é pelo menos tão difícil quanto os problemas mais difíceis de NP.
- NP-completo acrescenta que o próprio problema de decisão pertence a NP.
Para o problema usual de decisão sobre existência de solução, a descrição mais forte NP-completo é apropriada no resultado citado. Trabalhos que discutem resolução de forma mais ampla frequentemente usam NP-hard como termo guarda-chuva mais seguro.
Unicidade torna o problema mais fácil?
Não automaticamente.
Um quebra-cabeça prometido como tendo uma única solução ainda pode ser difícil de resolver. Determinar se existe outra solução também está intimamente relacionado a problemas difíceis de “outra solução” estudados em teoria da complexidade.
Para fins editoriais, a conclusão prática é mais simples:
único, resolúvel por humanos e fácil são três afirmações diferentes.
Por que solvers informáticos ainda funcionam bem
Dificuldade no pior caso não impede algoritmos práticos fortes.
Solvers exploram:
- propagação de restrições no nível de linha;
- programação dinâmica ou filtragem de padrões;
- agendamento inteligente de linhas alteradas;
- cache;
- verificações de contradição;
- heurísticas de ramificação;
- probing;
- tecnologia geral de resolução de restrições.
Coleções reais de quebra-cabeças também possuem muito mais estrutura do que instâncias teóricas adversariais.
Como resultado, um solver pode resolver rapidamente muitos quebra-cabeças grandes projetados por humanos mesmo sem existir uma garantia polinomial para o caso geral.
Por que isso importa para o design de quebra-cabeças
Resultados de complexidade não são apenas curiosidade abstrata.
Eles explicam por que um gerador precisa validar os candidatos em vez de assumir que todo conjunto de pistas vai se comportar bem. Um candidato pode ser:
- inconsistente;
- ambíguo;
- único, mas dependente de muita busca;
- único e resolvível de forma fluida.
Por isso, sistemas de construção combinam geração com verificações baseadas em solver e estimativas de dificuldade.
Erros de interpretação comuns
“NP-completo significa que ninguém consegue resolver nonogramas eficientemente”
Não. Significa que não se conhece um algoritmo em tempo polinomial para todas as instâncias, e que um algoritmo assim teria grandes consequências para a teoria da complexidade.
“Uma grade maior é exponencialmente difícil por definição”
Não. O tamanho expande o espaço de busca possível, mas a estrutura específica das pistas pode tornar até uma instância grande fácil.
“Se um quebra-cabeça pode ser resolvido sem chute, nonogramas não podem ser NP-hard”
Subclasses fáceis podem existir dentro de um problema geral difícil. Quebra-cabeças publicados são frequentemente escolhidos de propósito dentro dessas regiões mais amigáveis.
“NP significa não polinomial”
Não. NP é o nome de uma classe de complexidade; ela é normalmente caracterizada por soluções que podem ser verificadas em tempo polinomial.
O que aprender a seguir
Para os algoritmos que tornam a resolução prática possível, leia Como funcionam os solvers informáticos de nonogramas. Para os blocos combinatórios por trás das possibilidades de linha, leia Nonogramas e matemática.
FAQ
Nonogramas são NP-completos?
A forma padrão de decisão do problema geral possui resultados de NP-completude na literatura. Ao discutir resolução de forma mais ampla, ela também é frequentemente resumida como NP-hard.
Isso prova que todo quebra-cabeça exige chute?
Não. Muitos nonogramas publicados são projetados para serem resolvidos por deduções lógicas locais e propagação.
Um computador ainda consegue resolver nonogramas difíceis?
Sim. NP-completude não impede resolver instâncias individuais de forma eficaz; ela impede uma garantia eficiente conhecida para todas as instâncias sob as hipóteses padrão da teoria da complexidade.