O raciocínio por contradição testa uma suposição controlada e segue apenas deduções válidas até que a ramificação continue possível ou se torne impossível. Se uma suposição inevitavelmente viola as restrições do nonograma, o estado oposto fica provado.
Essa é lógica avançada. Ela deve vir depois de esgotar a resolução normal de linhas e a propagação de restrições.
A regra central
Suponha que uma célula não resolvida só possa estar preenchida ou vazia.
Teste temporariamente que ela é vazia.
Se essa suposição acabar fazendo uma linha ou coluna ficar com zero padrões válidos, ela não pode pertencer a nenhuma solução válida. Portanto, a célula precisa estar preenchida.
A mesma lógica funciona no sentido contrário.
A prova é a contradição, não o fato de uma ramificação “parecer pior”.
Exemplo: uma suposição errada destrói uma pista
Considere este estado parcialmente resolvido de um nonograma 5×5.
Linhas:
1 21241 1
Colunas:
1 11 11 21 21 1
Depois da propagação normal, a grade é:
???■?
???.?
.. ?■?
?■■■?
?.?.?
Para a ramificação de exemplo, suponha que R1C1 seja vazia.
Essa hipótese força a linha 1 ao único padrão restante e altera várias colunas. Continuando apenas com lógica comum, a linha 2 acaba precisando de duas células preenchidas separadas apesar de sua única pista ser 1.
A linha 2 passa então a ter zero padrões válidos. A ramificação é impossível.
Portanto, R1C1 = vazia é falso e R1C1 precisa estar preenchida.
O ponto importante é que todos os passos depois da suposição são deduções forçadas normais. Apenas a primeira escolha é provisória.
Contradição é diferente de chute cego
Chutar significa escolher um estado porque parece plausível e continuar como se ele fosse verdadeiro.
O raciocínio por contradição mantém a suposição explicitamente provisória:
- escolha um único estado candidato específico;
- propague apenas consequências logicamente forçadas;
- procure uma impossibilidade definida;
- se ela aparecer, desfaça a ramificação e confirme o estado oposto;
- se ela não aparecer, não declare a hipótese correta apenas porque sobreviveu a algumas deduções.
Uma ramificação continuar possível não significa que ela seja a solução.
O que conta como contradição?
Exemplos válidos incluem:
- uma linha não possui nenhum arranjo que satisfaça suas pistas e estados conhecidos;
- um run contínuo preenchido ultrapassa o tamanho de toda pista compatível;
- os blocos restantes já não possuem espaço suficiente;
- uma célula preenchida confirmada não pode ser coberta por nenhuma pista;
- a ordem das pistas se torna impossível;
- a mesma célula teria de ser simultaneamente preenchida e vazia.
A imagem resultante “parecer estranha” não é contradição.
Use a menor suposição útil
Um bom teste costuma começar em uma célula ou colocação de bloco altamente restrita, e não em uma longa cadeia especulativa.
Prefira candidatos em que os dois estados tenham consequências imediatas fortes. Assim uma contradição tende a aparecer cedo e o raciocínio fica mais fácil de auditar.
Propague fundo o suficiente, mas mantenha a ramificação controlada
Depois de assumir um estado, use as mesmas ferramentas de sempre:
- padrões válidos de linha;
- limites de blocos;
- atribuição de pistas a segmentos;
- blocos concluídos;
- cruzamento de informações;
- propagação de restrições.
Não adicione uma segunda suposição sem prova dentro da primeira. Se a ramificação parar sem contradição, volte ao estado inicial, a menos que você esteja entrando deliberadamente em busca/backtracking.
Escolha ramificações informativas, não apenas incertas
Toda célula desconhecida possui dois estados, mas a maioria é uma má candidata para ramificar.
Uma boa ramificação costuma ficar onde qualquer um dos estados mudaria imediatamente uma linha muito restrita. Bons candidatos incluem:
- uma célula compartilhada por apenas dois padrões restantes;
- a extremidade de um bloco com duas colocações legais;
- uma atribuição pista-segmento com exatamente duas alternativas;
- uma célula cujo estado concluiria ou romperia um bloco quase fixado.
Evite ramificar sobre uma célula livre dentro de uma grande região aberta. Os dois estados podem preservar dezenas de possibilidades e gerar uma busca longa sem pressão lógica.
Separe lookahead curto de busca completa
Um teste por contradição pode ser muito pequeno:
suponha X → uma linha cruzada perde seu último padrão válido → rejeite X.
Ou pode exigir uma cascata mais longa por várias linhas e colunas.
O status lógico é o mesmo enquanto quatro condições forem respeitadas:
- existe uma única suposição provisória claramente identificada;
- toda marca posterior é forçada sob essa suposição;
- a contradição final é explícita;
- nenhuma segunda adivinhação foi escondida dentro da ramificação.
Quando você começa a adicionar decisões arbitrárias porque a primeira ramificação travou, já está se aproximando de busca geral ou backtracking.
Mantenha um registro da ramificação
Em quebra-cabeças manuais difíceis, ajuda distinguir mentalmente três grupos:
- fatos raiz: estados permanentes provados antes da suposição;
- consequências da ramificação: estados válidos apenas enquanto a hipótese estiver ativa;
- conclusão da ramificação: contradição explícita ou ausência de conclusão.
Se a ramificação falhar, descarte todas as suas consequências juntas. O único novo fato permanente é a negação da suposição que falhou.
Se a ramificação simplesmente parar, descarte suas consequências e volte ao estado raiz sem mudança.
Essa disciplina impede que estados hipotéticos vazem para o tabuleiro real.
Consequências compartilhadas pertencem à análise multilinha por casos
Se os dois estados exaustivos de uma proposição continuam possíveis, mas ambos forçam a mesma célula posterior, essa consequência comum é válida.
É uma técnica avançada útil, mas a prova já não é “uma ramificação contradisse”. A VeyraPlay trata isso como raciocínio multilinha/two-way de consequência compartilhada, desenvolvido na G-040.
Método passo a passo
- esgote primeiro a propagação normal;
- escolha uma célula ou caso de bloco muito restrito;
- copie ou isole mentalmente o estado atual;
- assuma um dos estados candidatos;
- propague somente consequências forçadas;
- pare assim que uma linha ficar sem padrões ou surgir outra contradição dura;
- rejeite a hipótese e marque o estado oposto no quebra-cabeça real;
- reinicie a propagação normal a partir desse novo fato.
Erros comuns
Tratar “fiquei travado” como contradição
Uma ramificação que deixou de produzir deduções ainda pode ser válida.
Fazer vários chutes dentro da mesma ramificação
Nesse caso você já não sabe qual suposição provocou a contradição.
Rejeitar uma ramificação porque a imagem parece errada
Somente as restrições das pistas podem provar impossibilidade.
Usar contradição cedo demais
Muitos aparentes becos sem saída desaparecem depois de revisar padrões, marcas X, segmentos e linhas cruzadas alteradas.
Manter como fato uma suposição que apenas sobreviveu
Não encontrar contradição não é prova, a menos que você tenha demonstrado de forma exaustiva que a alternativa é impossível.
Onde isso fica na hierarquia de resolução
Uma ordem útil é:
- lógica direta de linha;
- segmentos e intervalos de blocos;
- padrões válidos de linha;
- cruzamento de informações e propagação;
- raciocínio multilinha e consequências compartilhadas;
- contradição/lookahead controlado;
- busca ou backtracking completo apenas quando o quebra-cabeça ou o solver realmente exigir.
Bons nonogramas projetados para pessoas normalmente tentam manter a maior parte do progresso antes da etapa de busca.
O que aprender depois
O raciocínio por contradição conecta a resolução humana a ideias usadas por solvers: testar candidatos, detectar ramificações impossíveis e, quando a propagação pura não basta, recorrer finalmente à busca.
FAQ
Raciocínio por contradição é chute?
Ele utiliza uma suposição temporária, mas a conclusão só é dedutiva quando uma ramificação é demonstrada impossível. É diferente de se comprometer com uma opção e torcer para funcionar.
E se as duas suposições continuarem possíveis?
Nesse caso, a célula escolhida ainda não foi demonstrada. Volte ao estado original ou procure uma consequência compartilhada pelas duas ramificações.
Iniciantes devem usar raciocínio por contradição?
Normalmente não como primeiro recurso. Lógica forte de linha e propagação resolvem uma grande parte dos nonogramas comuns e são muito mais fáceis de verificar.