Extensão mínima e folga em nonogramas

Extensão mínima é o menor número de células necessário para posicionar um conjunto ordenado de blocos de pista com todos os intervalos obrigatórios. Folga é o espaço extra que sobra quando esse arranjo mínimo é colocado dentro da linha ou do segmento disponível.

Juntas, essas duas medidas mostram quão restrita está uma linha antes mesmo de você conhecer a posição exata dos blocos.

Diagrama conceitual

Como calcular a extensão mínima

Para pistas monocromáticas padrão:

some os comprimentos de todos os blocos;
acrescente uma célula vazia obrigatória entre cada par de blocos consecutivos.

Para as pistas 3 2 4:

células dos blocos: 3 + 2 + 4 = 9;
intervalos obrigatórios: 2;
extensão mínima: 11.

Se a linha tiver comprimento 12, a sequência de pistas possui apenas uma célula de folga.

Exemplo de linha

Pistas324

Estado inicial

11min

1±

Como calcular a folga

A folga é:

comprimento disponível − extensão mínima

Para a linha de 12 células acima:

12 − 11 = 1

Isso significa que toda a sequência possui apenas uma célula extra para distribuir antes, depois ou entre os blocos além dos separadores mínimos.

Uma linha com folga zero é um encaixe exato.

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.

Por que pouca folga importa

Quanto menor a folga, menor a liberdade de movimento dos blocos.

Isso costuma tornar a linha uma boa candidata a:

sobreposição;
deduções de borda;
limites de colocação baseados na ordem dos blocos;
encaixes exatos em segmentos criados por marcas X.

Pouca folga não significa automaticamente que todas as células já são conhecidas. Significa que os arranjos legais estão comprimidos, o que frequentemente cria células forçadas quando são comparados.

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 · IntermediárioSobreposição com várias pistasAprenda sobreposição com várias pistas, compare posições extremas de cada bloco e evite falsas deduções quando blocos diferentes cobrem a mesma célula.

Exemplo: uma linha solta e uma linha apertada

Compare duas linhas de 15 células.

Pistas `4 4`

Extensão mínima:

4 + 1 + 4 = 9

Folga:

15 − 9 = 6

Os blocos possuem bastante liberdade.

Pistas `5 4 4`

Extensão mínima:

5 + 1 + 4 + 1 + 4 = 15

Folga:

0

A segunda linha é um encaixe exato e pode ser resolvida imediatamente.

Os números das pistas não são dramaticamente maiores, mas a sequência completa está muito mais restrita.

Use o comprimento do segmento disponível, não sempre o da linha inteira

Conforme o quebra-cabeça avança, células vazias confirmadas podem dividir a linha em segmentos abertos.

Se um grupo específico de pistas ainda não resolvidas já foi atribuído a um segmento, calcule extensão mínima e folga dentro desse segmento.

Por exemplo, 2 3 precisa de uma extensão mínima de 6. Se essas pistas pertencem a um segmento de sete células, há apenas uma célula de folga ali, mesmo que a linha original tenha 20 células.

Esse cálculo local costuma ser muito mais útil do que o número global da linha.

Técnicas · IntermediárioSegmentação de linhasAprenda como marcas X dividem linhas de nonogramas em segmentos abertos, reduzem a liberdade de colocação e criam problemas menores de pistas.Técnicas · IntermediárioAtribuição de pistas a segmentosAprenda a atribuir blocos de pistas a segmentos abertos usando ordem, capacidade, blocos concluídos e células preenchidas sem fazer chutes sem prova.

A folga é distribuída, não fica presa em um único lugar

Um erro comum é imaginar todas as células extras como uma região vazia no fim da linha.

A folga pode aparecer:

antes do primeiro bloco;
depois do último bloco;
como espaço vazio adicional entre blocos, além do separador obrigatório de uma célula.

Com várias pistas, distribuições diferentes alteram o intervalo de posição de blocos diferentes. É por isso que o raciocínio de colocação mais cedo/mais tarde é tão útil.

Uso passo a passo durante a resolução

Ao escolher uma linha para analisar:

determine o comprimento disponível da linha ou do segmento atribuído;
calcule a extensão mínima das pistas ainda não resolvidas;
subtraia para obter a folga;
priorize linhas com pouca folga;
verifique encaixe exato se a folga for zero;
verifique sobreposição e limites de colocação quando a folga for pequena;
recalcule depois que novas marcas X ou blocos concluídos reduzirem o espaço disponível.

Você não precisa calcular a folga de todas as linhas em toda varredura. Ela é mais útil como forma de reconhecer linhas que concentram informação.

A extensão mínima pode revelar atribuições impossíveis

Suponha que um segmento aberto tenha comprimento 5, mas um bloco de pista de comprimento 6 precisaria caber totalmente dentro dele. Essa atribuição é impossível.

Com várias pistas vale a mesma ideia: se a extensão mínima delas ultrapassa o comprimento disponível do segmento, elas não podem todas pertencer àquela região naquele arranjo.

Isso se torna central ao atribuir pistas a segmentos e eliminar regiões pequenas demais.

Técnicas · InicianteEliminação de intervalosAprenda a eliminar intervalos impossíveis em nonogramas, comparando o tamanho dos segmentos abertos com as pistas restantes para confirmar células vazias.Técnicas · IntermediárioAtribuição de pistas a segmentosAprenda a atribuir blocos de pistas a segmentos abertos usando ordem, capacidade, blocos concluídos e células preenchidas sem fazer chutes sem prova.

Erros comuns

Esquecer os intervalos obrigatórios

Para 3 2 4, a extensão mínima é 11, não 9.

Adicionar um intervalo obrigatório depois da última pista

A fórmula exige intervalos entre blocos consecutivos, não automaticamente antes do primeiro ou depois do último.

Assumir que as células de folga devem permanecer vazias

Folga representa liberdade de colocação. Uma posição de folga pode estar preenchida em um arranjo legal e vazia em outro.

Usar a folga da linha inteira depois que ela foi segmentada

Quando as restrições isolam pistas em um segmento menor, o comprimento relevante pode ser o desse segmento e não o da linha original.

Tratar pouca folga como prova por si só

Pouca folga indica onde olhar. Células forçadas ainda precisam de uma dedução específica, como encaixe exato, sobreposição ou limites de colocação.

O que aprender depois

Extensão mínima e folga sustentam quase todas as técnicas de linha mais profundas. O passo seguinte mais direto é usá-las com sobreposição e depois com ordem dos blocos e limites de colocação, onde cada pista recebe seu próprio intervalo legal de posições.

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 · IntermediárioSobreposição com várias pistasAprenda sobreposição com várias pistas, compare posições extremas de cada bloco e evite falsas deduções quando blocos diferentes cobrem a mesma célula.Técnicas · AvançadoOrdem dos blocos e limites de colocaçãoAprenda como a ordem das pistas cria limites mais cedo e mais tarde para cada bloco e como esses intervalos revelam células forçadas.

FAQ

Qual é a extensão mínima de uma única pista?

É simplesmente o valor da pista, pois não existem intervalos internos entre vários blocos.

O que significa folga zero?

As pistas consomem exatamente toda a linha ou segmento disponível depois de incluir os intervalos obrigatórios. Isso é um encaixe exato.

Mais folga sempre significa uma linha mais difícil?

Não. Células preenchidas e vazias já conhecidas podem restringir fortemente uma linha mesmo quando a sequência original tem bastante folga. Folga é uma medida de restrição, não uma classificação completa de dificuldade.