Nonogramas usam muito pouca aritmética durante o jogo, mas por baixo do quebra-cabeça existe um problema combinatório compacto de restrições.
Cada pista descreve blocos ordenados de células preenchidas em uma linha. As restrições das linhas e das colunas se cruzam nas mesmas células, e resolver significa encontrar a grade binária que satisfaz todas elas ao mesmo tempo.
As pistas são descrições de comprimentos de blocos
Uma sequência de pistas registra os comprimentos dos blocos consecutivos preenchidos.
Por exemplo:
■■■ ×× ■■ × ■
3 2 1Os números não dizem onde os blocos começam. Eles informam:
- comprimentos dos blocos;
- ordem dos blocos;
- que blocos monocromáticos vizinhos precisam ser separados por pelo menos uma célula vazia.
É por isso que uma sequência de pistas é mais do que uma soma.
Extensão mínima
Suponha que uma linha tenha m blocos de pistas com comprimentos:
c1, c2, ..., cmAs células preenchidas exigem:
c1 + c2 + ... + cmcélulas, e as m - 1 fronteiras entre blocos consecutivos exigem pelo menos uma célula vazia cada.
Portanto, o menor espaço capaz de conter todas as pistas é:
extensão mínima = soma(pistas) + (número de pistas - 1)Para uma linha de 10 células com pistas 3 2:
extensão mínima = 3 + 2 + 1 = 6A linha possui então quatro células de liberdade extra de colocação.
Esse espaço adicional é a folga.
Quantas colocações uma sequência de pistas pode ter em uma linha vazia?
Em uma linha monocromática sem outras restrições, a folga pode ser distribuída:
- antes do primeiro bloco;
- depois do último bloco;
- como células vazias adicionais em qualquer intervalo obrigatório entre blocos.
Se existem m blocos e uma folga s, o número de colocações completas é:
C(s + m, m)onde C é o coeficiente binomial.
Exemplo: comprimento 10 com pistas 3 2
Já encontramos:
extensão mínima = 6
folga = 10 - 6 = 4
m = 2Portanto, o número de padrões completos legais em uma linha totalmente desconhecida é:
C(4 + 2, 2) = C(6, 2) = 15Essa contagem descreve a linha inicial sem restrições. Quando algumas células já são conhecidas como preenchidas ou vazias, muitos desses 15 padrões podem ser eliminados.
Por que a sobreposição funciona matematicamente
Uma célula é forçada como preenchida quando todo padrão válido sob as restrições atuais preenche essa célula.
Da mesma forma, uma célula é forçada como vazia quando todo padrão válido a deixa vazia.
A sobreposição é um atalho humano rápido para encontrar algumas dessas células comuns sem listar explicitamente todos os padrões possíveis.
A técnica mais avançada de padrões válidos de linha torna a mesma ideia explícita: gerar ou raciocinar sobre o conjunto completo de padrões legais e manter os estados em que todos eles concordam.
Linhas e colunas formam restrições que se cruzam
Uma pista de linha, por si só, restringe uma sequência binária horizontal. Uma pista de coluna restringe uma sequência binária vertical.
Cada célula pertence exatamente a uma linha e a uma coluna, então os dois sistemas estão acoplados.
Quando uma linha prova que uma célula está preenchida, isso vira um valor fixo na coluna cruzada. Alguns padrões dessa coluna desaparecem. A coluna reduzida pode então forçar outra célula, que altera outra linha.
Essa redução repetida é propagação de restrições.
Um nonograma não é resolvido somando os números das pistas
Somas são úteis para extensão mínima e contagens de ocupação, mas o quebra-cabeça depende de posições e ordem.
Duas sequências de pistas podem ter o mesmo total de células preenchidas e se comportar de forma muito diferente:
6
3 3
2 2 2Todas descrevem seis células preenchidas, mas seus intervalos obrigatórios e identidades de blocos criam espaços de colocação diferentes.
Por isso, “as pistas somam o comprimento da linha” só é suficiente em casos de encaixe exato nos quais os separadores obrigatórios também foram contabilizados corretamente.
A combinatória cresce rapidamente
Mesmo linhas individuais podem ter muitos arranjos legais quando contêm vários blocos pequenos e muita folga.
Em uma grade completa, as possibilidades das linhas não podem ser escolhidas de forma independente, porque cada coluna também precisa corresponder às suas pistas.
O quebra-cabeça é, portanto, um problema de restrições sobre muitas variáveis binárias que interagem, e não apenas uma coleção de exercícios separados de colocação em linhas.
É dessa interação que podem surgir instâncias computacionalmente difíceis.
Por que essa matemática ajuda jogadores humanos
Você não precisa calcular coeficientes binomiais enquanto joga.
Mas a matemática subjacente explica várias regras práticas:
- pouca folga significa menos colocações;
- encaixe exato significa uma única colocação;
- sobreposição encontra células comuns às colocações extremas ou válidas;
- marcas X removem colocações candidatas;
- células preenchidas restringem quais identidades de bloco podem alcançá-las;
- cruzamento de informações transfere restrições entre os dois sistemas de linhas;
- contradição prova que uma ramificação possui zero conclusões válidas.
As técnicas do restante do corpus transformam essas restrições em deduções amigáveis para humanos, sem exigir a enumeração manual de todo o espaço de busca.
Nonograma é um quebra-cabeça matemático?
É razoável chamá-lo de quebra-cabeça de lógica matemática, mas você não precisa de matemática avançada para resolver nonogramas publicados comuns.
A maior parte do jogo envolve:
- contar células;
- comparar comprimentos;
- preservar ordem;
- eliminar colocações impossíveis;
- propagar consequências.
A combinatória mais profunda se torna útil ao analisar algoritmos, geradores, dificuldade e complexidade no pior caso.
O que aprender a seguir
Para uma versão prática da ideia de conjunto de colocações, leia Padrões válidos de linha. Para resolução algorítmica, continue em Como funcionam os solvers informáticos de nonogramas. Para teoria da complexidade, leia Por que os nonogramas são computacionalmente difíceis.
FAQ
Qual é a fórmula de extensão mínima para pistas de nonogramas?
Para pistas monocromáticas padrão, some todos os valores das pistas e depois acrescente uma célula vazia obrigatória para cada fronteira entre blocos consecutivos.
A fórmula de contagem de colocações sempre se aplica?
A fórmula simples C(s + m, m) vale para uma linha sem outras restrições e com separação monocromática padrão. Células preenchidas/vazias conhecidas e atribuições a segmentos reduzem ainda mais o conjunto.
Preciso de combinatória para resolver nonogramas?
Não. As técnicas padrão transformam as consequências úteis em deduções visuais muito mais fáceis de aplicar manualmente.