Propagação de restrições e cascatas

A propagação de restrições é o processo repetido de aplicar estados de célula recém-confirmados às linhas que os cruzam, encontrar novas consequências nessas linhas e continuar até que nenhuma dedução imediata produza outra mudança.

Uma cascata é a cadeia visível de deduções criada por esse processo.

Exemplo de cascata em uma grade 5×5

Considere um nonograma monocromático 5×5 com estas pistas:

Linhas: 1, 3, 5, 3, 1

Colunas: 1, 3, 5, 3, 1

A linha 3 é um encaixe exato porque a pista 5 preenche toda a linha. Marque as cinco células como preenchidas.

Agora propague:

1. as colunas 1 e 5 têm pista 1, já satisfeita pela célula central preenchida, então todas as outras células dessas colunas são vazias;
2. a coluna 3 tem pista 5, portanto é preenchida por completo;
3. as linhas 1 e 5 agora já têm sua única célula preenchida necessária na coluna 3, então todas as outras ficam vazias;
4. as colunas 2 e 4, ambas com pista 3, passam a ser forçadas a preencher as linhas 2–4;
5. as linhas 2 e 4 tornam-se blocos completos de três.

Uma única linha de encaixe exato resolve a grade inteira por meio da propagação.

Propagação não é uma fonte de verdade separada

Cada passo individual ainda usa deduções normais e válidas: encaixe exato, blocos concluídos, sobreposição, eliminação de intervalos, filtragem de padrões e assim por diante.

Propagação descreve como essas deduções são agendadas e encadeadas dentro da grade compartilhada.

Por que cascatas são mais eficientes que reexaminar tudo

Quando uma célula muda, apenas sua linha e sua coluna recebem informação nova diretamente.

Então, em vez de começar o quebra-cabeça do topo toda vez, siga as linhas afetadas. Se uma delas alterar outra célula, siga em seguida a linha perpendicular dessa nova célula.

Isso concentra sua atenção exatamente onde o sistema de restrições mudou.

Propague os dois tipos de certeza

Uma cascata pode ser impulsionada por preenchimentos ou por marcas X.

Por exemplo:

• uma célula preenchida pode ancorar um bloco;
• um X pode dividir um segmento;
• essa divisão pode atribuir uma pista;
• a atribuição pode criar um encaixe exato;
• o encaixe exato pode concluir um bloco cruzado;
• seu separador pode eliminar outro intervalo.

Não existe uma hierarquia em que células preenchidas sejam “progresso real” e células vazias sejam secundárias. Os dois estados reduzem o conjunto de padrões legais.

Pare somente em um estado estável

Uma rodada de propagação termina quando todas as linhas afetadas por novos estados foram reconsideradas e nenhuma outra certeza surge.

Solvers de computador costumam chamar isso de ponto fixo: repetir as mesmas deduções de linha não mudaria mais a grade.

Nesse ponto, escolha outra linha não resolvida promissora ou, em quebra-cabeças realmente difíceis, considere um raciocínio mais forte.

Uma cascata pode começar sem nenhuma linha de encaixe exato

O exemplo do diamante começa com uma linha completa óbvia. Cascatas mais interessantes começam com uma dedução de consenso mais fraca.

Considere este quebra-cabeça 5×5:

Linhas: 2 1, 1 1, 2, 2, 1 1

Colunas: 1 2, 1 2, 2, 1, 2

Nenhuma linha ou coluna é um encaixe exato no início. Mesmo assim, a linha 1 com pistas 2 1 possui uma única célula preenchida em todos os padrões iniciais válidos: a célula 2.

Marque R1C2 como preenchida e propague apenas estados de consenso. A nova informação restringe a coluna 2; essa coluna cria novos estados nas linhas 2 e 4; essas linhas restringem mais colunas; o processo continua até que todas as células fiquem determinadas.

A solução única é:

■■××■

××■×■

×■■××

■■×××

■××■×

Esse exemplo mostra por que propagação é mais do que “resolver primeiro as linhas fáceis”. Uma dedução modesta de uma única linha pode se tornar decisiva porque a grade a amplifica repetidamente por meio das restrições perpendiculares.

Use uma fila de linhas alteradas em vez de reexaminar tudo

Uma forma precisa de pensar a propagação manual é como uma fila:

1. quando uma célula mudar, adicione sua linha e sua coluna à fila;
2. pegue uma linha alterada e resolva-a contra os estados atuais;
3. se essa linha mudar células, adicione suas linhas perpendiculares à fila;
4. retire a linha processada;
5. continue até que a fila fique vazia.

A mesma linha pode voltar várias vezes à fila conforme novas informações cruzadas chegam. Isso é normal.

Solvers de computador costumam usar a mesma ideia de agendamento porque uma linha sem mudança não recebeu informação nova e não precisa ser reconsiderada imediatamente.

Um ponto fixo depende da força do seu solver de linha

Há um detalhe avançado importante.

Se sua análise de linha verifica apenas sobreposição simples, você pode chegar a um estado em que a sobreposição simples não produz nada. Isso não significa que o quebra-cabeça atingiu um ponto fixo lógico verdadeiro.

Um solver de linha mais forte, que considere todos os padrões válidos, ainda pode encontrar novas células e reiniciar a propagação.

Portanto, ao dizer que “a propagação se esgotou”, deixe claro qual mecanismo de dedução está sendo propagado:

• ponto fixo de sobreposição básica;
• ponto fixo de padrões válidos completos;
• ou um ponto fixo mais forte de raciocínio multilinha/global.

Isso explica por que um nonograma pode parecer travado mesmo sem exigir qualquer chute.

Propagação e padrões válidos de linha

O raciocínio por padrões oferece uma visão formal limpa.

Cada linha e coluna possui um conjunto de padrões válidos. Quando uma célula passa a preenchida ou vazia:

1. padrões incompatíveis desaparecem da linha cruzada;
2. os padrões sobreviventes podem agora concordar sobre outra célula;
3. essa nova célula forçada filtra outra linha perpendicular;
4. o processo se repete.

Isso é exatamente o que uma cascata lógica faz.

Fluxo prático de propagação

1. mantenha uma pequena fila mental das linhas alteradas pelos últimos movimentos;
2. processe uma linha usando a técnica mais forte apropriada;
3. sempre que marcar uma nova célula, adicione sua linha perpendicular à fila;
4. evite reexaminar repetidamente linhas que não receberam informação nova;
5. continue até que a fila não produza mais estados;
6. só então volte à varredura geral em busca do próximo ponto de entrada.

Em grades grandes, esse fluxo é muito mais eficiente do que voltar à linha 1 depois de cada dedução.

Erros comuns

Parar depois da primeira consequência

Uma nova célula pode desencadear vários passos adicionais. Siga a cadeia até que ela se estabilize.

Propagar uma suposição incerta como se fosse fato

A propagação normal usa estados confirmados. Se você testar deliberadamente uma hipótese, mantenha essa ramificação claramente separada; isso pertence ao raciocínio por contradição.

Ignorar cascatas de células vazias

Marcas X podem ser justamente o passo que divide uma linha ou fecha um bloco.

Reexaminar todas as linhas indiscriminadamente

Dê prioridade às linhas tocadas por células que mudaram.

O que aprender depois

Se a propagação alcançar um estado estável com células ainda não resolvidas, alguns quebra-cabeças de nível especialista exigem uma suposição controlada: testar um estado candidato, propagar apenas consequências lógicas e rejeitá-lo se ele criar uma impossibilidade. Isso é raciocínio por contradição.

FAQ

Propagação de restrições é a mesma coisa que cruzamento de informações?

O cruzamento é uma transferência entre linhas perpendiculares. Propagação é o sistema repetido dessas transferências até não existir mais consequência imediata.

Propagação envolve chute?

Não. A propagação padrão usa estados de célula já demonstrados.

Uma única dedução simples pode resolver um quebra-cabeça inteiro?

Sim. Alguns nonogramas possuem cascatas longas em que uma única linha forçada no início gera consequências suficientes para terminar a grade.