Dificuldade em nonogramas: como é classificada

Não existe uma fórmula universal de dificuldade para nonogramas. Um sistema de classificação precisa primeiro decidir o que entende por “difícil”: mais deduções, deduções mais avançadas, gargalos mais longos, mais busca, tempos maiores de resolução humana ou alguma combinação desses fatores.

É por isso que duas editoras podem atribuir rótulos diferentes ao mesmo quebra-cabeça sem que nenhuma esteja violando as regras.

Diagrama conceitual

A dificuldade é uma propriedade de um modelo de resolução

Imagine dois solvers.

O Solver A conhece apenas sobreposição básica e lógica de blocos concluídos. O Solver B consegue enumerar todos os padrões válidos de linha e usar raciocínio por contradição.

O mesmo quebra-cabeça pode travar para o Solver A e avançar sem grandes problemas para o Solver B.

Portanto, uma pontuação de dificuldade depende em parte de o que o solver usado para medir está autorizado a fazer.

Trabalhos acadêmicos sobre nonogramas tornam isso explícito ao definir classes específicas de raciocínio e depois medir os quebra-cabeças em relação a essas classes.

Técnicas · AvançadoPadrões válidos de linhaAprenda a analisar padrões válidos de uma linha, eliminar arranjos incompatíveis com células conhecidas e identificar preenchimentos e vazios forçados.Técnicas · EspecialistaRaciocínio por contradiçãoAprenda a testar provisoriamente um estado de célula, propagar consequências e provar o estado oposto quando uma ramificação deixa uma linha sem padrões válidos.

Sinais comuns usados para estimar dificuldade

Número de passagens de raciocínio ou deduções

Um modelo simples pode contar quantas varreduras de linhas e colunas são necessárias antes de resolver o quebra-cabeça.

Batenburg e colaboradores estudaram uma classe de nonogramas resolvíveis por raciocínio local de linha e definiram uma medida de dificuldade baseada em varreduras horizontais e verticais repetidas. O modelo é útil justamente porque o procedimento de resolução é definido primeiro.

Mais etapas normalmente significam mais trabalho dentro daquele modelo, mas a contagem de passos sozinha não descreve tudo o que uma pessoa experimenta.

Técnica mais difícil necessária

Um quebra-cabeça resolvido inteiramente com encaixes exatos e sobreposições óbvias tende a ser mais acessível do que um que exige enumeração de padrões de linha ou raciocínio por contradição.

Um produto pode, portanto, atribuir pesos a famílias de técnicas ou usar a técnica mais forte necessária como um componente da classificação.

Técnicas · InicianteLinhas de encaixe exatoAprenda o encaixe exato em nonogramas, calcule a extensão mínima, posicione blocos e separadores e reconheça encaixes exatos em segmentos.Técnicas · InicianteMétodo de sobreposição em nonogramasAprenda a técnica de sobreposição em nonogramas comparando posições extremas de um bloco e encontre preenchimentos forçados sem adivinhar.Técnicas · EspecialistaRaciocínio por contradiçãoAprenda a testar provisoriamente um estado de célula, propagar consequências e provar o estado oposto quando uma ramificação deixa uma linha sem padrões válidos.

Grau de liberdade das pistas

Linhas com pouca folga possuem menos colocações possíveis. Linhas com muitos padrões sobreviventes costumam revelar menos informação.

As medidas podem usar:

extensão mínima;
folga;
número de padrões válidos de linha;
velocidade com que esses padrões colapsam quando chegam informações das linhas cruzadas.

Técnicas · IntermediárioExtensão mínima e folgaCalcule extensão mínima e folga em nonogramas, compare linhas apertadas, encontre encaixes exatos, sobreposições e segmentos restritos.Técnicas · AvançadoPadrões válidos de linhaAprenda a analisar padrões válidos de uma linha, eliminar arranjos incompatíveis com células conhecidas e identificar preenchimentos e vazios forçados.

Comprimento das cadeias de propagação

Alguns quebra-cabeças revelam muitas células imediatamente. Outros dependem de cadeias longas em que uma pequena dedução libera exatamente uma linha cruzada por vez.

Uma cadeia longa de dependências pode aumentar a dificuldade mesmo quando cada passo individual é elementar.

Técnicas · IntermediárioPropagação de restrições e cascatasAprenda propagação de restrições em nonogramas, encadeie deduções entre linhas e colunas e esgote uma cascata lógica antes de buscar outro ponto de entrada.

Gargalos

Um quebra-cabeça pode ser fácil em 90% da grade e ainda parecer difícil porque um único estado exige uma dedução sutil antes de qualquer outra coisa avançar.

Trabalho médio e pico de dificuldade de raciocínio são, portanto, métricas diferentes.

Um sistema de classificação útil deve perceber ambos.

Necessidade de ramificação, probing ou análise por contradição

Se um solver lógico escolhido chega a um ponto fixo com células ainda não resolvidas, um processo mais forte pode explorar provisoriamente hipóteses ou ramificações de busca.

A presença, profundidade e frequência dessa busca podem ser sinais fortes de dificuldade em classificações geradas por computador.

Mas é preciso interpretar isso com cuidado: um solver limitado pode ramificar em um quebra-cabeça para o qual uma pessoa conhece uma técnica direta mais forte.

Referência · Todos os níveisÉ preciso chutar em nonogramas?Veja se nonogramas exigem palpites, como dedução lógica difere de tentativa e erro e onde entram contradição, busca e backtracking.Técnicas · EspecialistaRaciocínio por contradiçãoAprenda a testar provisoriamente um estado de célula, propagar consequências e provar o estado oposto quando uma ramificação deixa uma linha sem padrões válidos.Teoria · AvançadoComo funcionam os solvers informáticos de nonogramasVeja como solvers de nonogramas analisam padrões válidos, propagam restrições entre linhas e colunas, detectam contradições e verificam unicidade.

Por que o tamanho da grade é uma medida fraca quando usado sozinho

Uma grade maior contém mais células e normalmente leva mais tempo para ser concluída, mas isso não é o mesmo que dificuldade lógica.

Um quebra-cabeça grande com pistas longas e informativas pode produzir deduções constantes. Um quebra-cabeça compacto com pistas curtas e muita folga pode criar um gargalo muito mais apertado.

O tamanho é um contexto útil para:

duração esperada;
carga visual;
esforço de varredura;
número de linhas a administrar.

Ele não deve ser tratado como uma pontuação lógica independente.

Dificuldade humana vs dificuldade para computador

Um computador e uma pessoa não vivenciam um quebra-cabeça da mesma maneira.

Um programa pode executar milhões de operações dentro de um algoritmo conceitualmente simples. Uma pessoa pode perceber a mesma dedução visualmente em um instante.

No sentido inverso, um computador consegue comparar centenas de padrões de linha perfeitamente, enquanto uma pessoa pode achar esse controle mental exaustivo.

Classificações voltadas para humanos podem incorporar:

tempos observados de resolução;
taxas de conclusão;
uso de dicas;
taxas de erro;
nível de habilidade do jogador;
quais deduções as pessoas realmente percebem.

Esses dados podem complementar características derivadas do solver, em vez de substituí-las.

A dificuldade pode ser alvo durante a geração

Dificuldade não é apenas algo medido depois que um quebra-cabeça existe.

Pesquisas já usaram solvers semelhantes a humanos como parte de sistemas de geração: nonogramas candidatos são avaliados segundo a forma como o solver modelado progride e, então, a imagem ou o quebra-cabeça subjacente é modificado para se aproximar de uma faixa de dificuldade desejada.

Trabalhos mais recentes também exploram métodos de otimização que procuram quebra-cabeças avaliados como difíceis e agradáveis dentro de um modelo de avaliação escolhido.

Isso reforça um princípio importante:

um rótulo de dificuldade só é significativo em relação a um modelo e a um processo de calibração definidos.

Teoria · Todos os níveisComo os nonogramas são criadosAprenda como nonogramas são feitos a partir de uma grade preenchida, como as pistas são geradas, por que a solução única importa e como testar dificuldade.

O que uma futura classificação da VeyraPlay deveria considerar

Este guia não congela a fórmula de produção da VeyraPlay. Ela deverá ser calibrada com o engine real e com dados de jogadores.

Um sistema futuro robusto poderia combinar:

solvabilidade sob conjuntos progressivamente mais fortes de técnicas;
total de deduções forçadas;
número e severidade dos gargalos;
contagens de padrões de linha;
profundidade de propagação;
exigências de contradição/busca;
tamanho da grade como contexto de carga de trabalho;
comportamento empírico dos jogadores quando houver dados suficientes.

A decisão arquitetônica importante é manter rótulo de dificuldade separado de evidência de dificuldade, para que a classificação possa evoluir sem reescrever a identidade lógica do quebra-cabeça.

Erros de interpretação comuns

“Difícil significa grande”

Grande muitas vezes significa mais demorado. Não significa necessariamente mais difícil em termos lógicos.

“Único significa fácil o bastante para resolver”

Unicidade diz que existe uma única resposta, não quão difícil é provar essa resposta.

“Uma classificação gerada por computador é objetiva”

Ela é reproduzível dentro do seu algoritmo, mas o algoritmo ainda incorpora escolhas sobre quais operações contam e quanto cada uma pesa.

“A técnica mais difícil define toda a classificação”

Dois quebra-cabeças podem exigir a mesma técnica e ainda diferir muito em quantas vezes ela aparece, quão escondida está e quão longa fica a cadeia de dependências.

O que aprender a seguir

Para o lado algorítmico, continue em Como funcionam os solvers informáticos de nonogramas. Para entender por que algumas instâncias se tornam difíceis de forma mais ampla, leia Por que os nonogramas são computacionalmente difíceis.

Referência · Todos os níveisNíveis de dificuldade dos nonogramasEntenda o que torna um nonograma fácil ou difícil, por que o tamanho da grade não define a dificuldade e por que as classificações variam entre apps.Teoria · Todos os níveisComo os nonogramas são criadosAprenda como nonogramas são feitos a partir de uma grade preenchida, como as pistas são geradas, por que a solução única importa e como testar dificuldade.Teoria · AvançadoSoluções únicas e nonogramas ambíguosEntenda quando um nonograma tem solução única, como pistas ambíguas admitem várias soluções e por que unicidade não significa um puzzle fácil.Teoria · AvançadoComo funcionam os solvers informáticos de nonogramasVeja como solvers de nonogramas analisam padrões válidos, propagam restrições entre linhas e colunas, detectam contradições e verificam unicidade.Teoria · EspecialistaPor que os nonogramas são computacionalmente difíceisEntenda por que o problema geral dos nonogramas é computacionalmente difícil, o que NP-completo significa e por que puzzles comuns seguem resolvíveis.

FAQ

Existe um padrão oficial Fácil/Médio/Difícil para nonogramas?

Não existe um padrão universal. Editoras podem definir e calibrar suas próprias escalas.

A dificuldade pode ser calculada antes que jogadores resolvam o quebra-cabeça?

Sim. Um modelo baseado em solver pode estimá-la. Dados reais de jogadores podem melhorar a calibração depois.

Dois nonogramas do mesmo tamanho podem ter dificuldades muito diferentes?

Com certeza. Estrutura das pistas, colocações válidas, caminhos de propagação e raciocínio necessário podem ser completamente diferentes.