O que torna um nonograma fácil ou difícil

Uma grade maior de fato significa mais linhas para acompanhar e mais verificações cruzadas, então quebra-cabeças grandes levam mais tempo. Mas o comprimento sozinho não torna uma linha difícil — uma fileira de 20 de largura com uma única sequência grande é trivial, enquanto uma fileira curta cheia de sequências pequenas e lacunas apertadas pode exigir reflexão de verdade. O tamanho afeta muito mais quanto tempo um quebra-cabeça leva do que quão difícil é cada passo.

A medida mais fiel da dificuldade é que tipo de raciocínio o quebra-cabeça exige. Os mais fáceis são "solúveis por linha": você pode terminá-los olhando uma fileira ou coluna de cada vez, preenchendo o que aquela única linha força, sem nunca precisar manter duas linhas na cabeça ao mesmo tempo. A maioria dos quebra-cabeças suaves é exatamente assim.

Os mais difíceis exigem combinar informação — perceber que o estado de uma casa só se torna forçado quando você considera uma fileira e uma coluna juntas, ou um pequeno grupo de linhas de uma vez. Quanto mais fundo essa combinação precisa ir antes que a próxima casa seja forçada, mais difícil o quebra-cabeça parece, independentemente de seu tamanho.

Aqui vem a parte tranquilizadora. O trabalho acadêmico sobre a resolução de nonogramas (Batenburg and Kosters, 2012) mediu quanto raciocínio os quebra-cabeças de solução única realmente exigem. Além da simples resolução linha por linha, o próximo passo é uma técnica bem definida e ainda determinística — combinar pares de linhas — e sua enumeração exaustiva descobriu que 93.8–95.5% dos quebra-cabeças não simples são solúveis exatamente com isso, sem nenhum palpite.

Ainda mais impressionante: apenas cerca de 0.06–0.14% de todos os quebra-cabeças de solução única precisam de algo além desse raciocínio de pares de linhas. Em outras palavras, a esmagadora maioria dos nonogramas bem formados — incluindo cada um difícil que você encontrará no jogo normal — pode ser resolvida com lógica pura e limitada. A verdadeira tentativa e erro é raríssima num quebra-cabeça justo, e é por isso que "nunca adivinhe" é um conselho tão confiável.

Sob tudo isso há um resultado teórico. Decidir se um conjunto arbitrário de pistas de fileiras e colunas tem sequer alguma solução foi provado ser NP-completo (Ueda and Nagao, 1996) — a mesma classe de complexidade de problemas notoriamente teimosos como o do caixeiro-viajante. Em termos simples: ninguém conhece um método que resolva rapidamente todo nonograma concebível, e nos piores casos o trabalho necessário explode à medida que a grade cresce.

Isso soa alarmante até você notar a diferença entre "todo nonograma concebível" e "os nonogramas que as pessoas realmente publicam". O resultado de NP-completude trata de conjuntos de pistas arbitrários e adversariais — muitos dos quais não têm solução, ou têm várias. Um quebra-cabeça real é construído ao contrário: parte de uma imagem, e só é publicado se tiver exatamente uma solução que a lógica consiga de fato alcançar. É por isso que os números da seção anterior se sustentam na prática, e por isso o quebra-cabeça à sua frente é quase com certeza justo, mesmo quando parece brutal.

Além da profundidade da dedução, algumas características superficiais empurram a dificuldade. Imagens muito esparsas (na maior parte vazias) e muito densas (na maior parte preenchidas) tendem a ser mais fáceis, porque os extremos oferecem muitas casas forçadas logo no início. Os quebra-cabeças mais complicados costumam ficar no meio, com uma mistura equilibrada de preenchido e vazio e muitas sequências curtas e fragmentadas que resistem às jogadas rápidas de abertura. Um tema limpo e reconhecível também ajuda o solucionador a se manter orientado, mesmo que não mude a lógica subjacente.

Neste site, a classificação de um quebra-cabeça vem de quão fundo vai o raciocínio para resolvê-lo, combinado com estatísticas de forma como o quanto a grade está preenchida. Quebra-cabeças solúveis por linha ficam no fácil; os que exigem verdadeira combinação entre linhas movem-se para o difícil; qualquer coisa que exigisse adivinhação é rejeitada de imediato em vez de publicada. O processo completo é descrito na página "como fazemos nossos nonogramas" — mas a versão curta é que aqui a dificuldade é medida, não adivinhada.