As pistas de um nonograma fazem mais do que indicar comprimentos. Elas também fixam a ordem dos blocos. Essa ordem cria uma posição legal mais cedo e outra mais tarde para cada bloco, mesmo antes de sabermos sua colocação exata.
Exemplo: pistas 2 3 em uma linha de dez células
Considere uma linha vazia de 10 células com pistas 2 3.
O primeiro bloco pode começar já na célula 1. Mas não pode começar arbitrariamente tarde: precisa deixar pelo menos um separador e espaço suficiente para o bloco posterior de três.
Seu início mais tardio é a célula 5, então seu alcance possível vai das células 1–6.
O segundo bloco não pode começar antes da célula 4, porque primeiro precisam caber o bloco de dois e um separador obrigatório. Seu início mais tardio é a célula 8, permitindo alcançar até a célula 10.
Ainda pode não existir nenhum preenchimento forçado, mas os dois blocos já possuem territórios legais diferentes porque a ordem das pistas impede que troquem de posição.
Posição mais cedo
A posição mais cedo de um bloco é a colocação mais à esquerda ou mais acima que ele pode ocupar mantendo possíveis todas as pistas anteriores, os separadores, as células preenchidas conhecidas e as marcas X.
Para blocos posteriores, esse limite depende de tudo o que obrigatoriamente precisa aparecer antes deles.
Posição mais tarde
A posição mais tarde é a colocação mais à direita ou mais abaixo que o bloco pode ocupar sem retirar o espaço legal necessário para todas as pistas que ainda vêm depois.
Para blocos anteriores, esse limite depende fortemente dos blocos posteriores.
Por que a ordem importa em linhas com várias pistas
Se uma linha tem pistas 2 5 3, elas não são três blocos intercambiáveis. O 2 precisa vir primeiro, o 5 em segundo e o 3 por último.
Um fragmento preenchido perto da borda direita pode fisicamente caber em um bloco de tamanho 2, mas não pode ser a pista 2 se isso deixar as pistas 5 3 sem espaço depois.
Por isso, o alcance dos blocos deve ser calculado preservando identidade e ordem, e não apenas o tamanho.
Exemplo trabalhado: células conhecidas apertam três intervalos ordenados
Considere uma linha de 12 células com pistas 2 4 2. A célula 4 está confirmada vazia e a célula 8 confirmada preenchida:
???×???■????
Exatamente seis padrões completos de linha continuam compatíveis com esses estados.
Entre esses seis padrões, as posições de início legais são:
| Bloco de pista | Início mais cedo | Início mais tarde |
|---|---|---|
primeiro 2 | 1 | 2 |
4 central | 5 | 6 |
último 2 | 10 | 11 |
A identidade dos blocos importa. Não estamos perguntando onde “um bloco 2” pode ficar; estamos perguntando onde o primeiro e o último blocos 2 podem ficar enquanto o 4 permanece entre eles.
Esses limites já implicam várias células por consenso:
- a célula 2 é coberta pelo primeiro bloco em todos os padrões válidos;
- as células 6–8 são cobertas pelo bloco central em todos eles;
- a célula 11 é coberta pelo último bloco em todos eles;
- a célula 4 permanece vazia pela restrição dada.
Portanto, limites não são apenas intervalos descritivos. Quando ficam estreitos o bastante, expõem a sobreposição de cada bloco ordenado.
Os limites são acoplados, não intervalos independentes
É tentador calcular um intervalo para cada pista e depois tratá-los separadamente. Em linhas com várias pistas, isso pode estar errado.
Mover um bloco para mais tarde pode empurrar o seguinte para mais tarde porque um separador obrigatório precisa continuar entre eles. Mover o bloco final para mais cedo pode puxar o anterior para mais cedo pelo mesmo motivo.
Pense nos blocos ordenados como uma cadeia de intervalos acoplados:
- blocos anteriores empurram os posteriores para a direita/baixo;
- blocos posteriores empurram os anteriores para a esquerda/cima;
- marcas X e limites de segmento podem cortar a cadeia em subproblemas menores;
- fragmentos preenchidos conhecidos podem fixar um bloco e apertar os dois vizinhos.
Por isso, recalcular limites a partir dos dois extremos é mais confiável do que estimar o alcance de cada pista isoladamente.
Limites versus análise completa de padrões válidos
Duas linhas podem ter os mesmos limites mais cedo/mais tarde e ainda diferir nas combinações intermediárias que são legais. As colocações extremas comprimem informação, portanto podem deixar escapar deduções que só aparecem quando todos os padrões completos são considerados.
Use limites quando eles dão uma prova limpa. Passe para padrões válidos quando os extremos deixam ambiguidade demais ou quando células conhecidas criam possibilidades de colocação não contínuas.
Os limites apertam conforme a linha é resolvida
Cada estado confirmado pode mudar os intervalos:
- uma marca X pode empurrar um bloco para dentro;
- um fragmento preenchido pode obrigar um bloco a cobrir determinada região;
- um bloco concluído pode fixar a identidade de uma pista e dividir a sequência restante;
- uma atribuição a segmento pode restringir uma pista a uma região menor;
- deduções de linhas cruzadas podem remover colocações antes possíveis.
Recalcule os limites sempre que a linha ganhar informação importante.
Limites criam sobreposição
Quando você conhece a colocação mais cedo e mais tarde do mesmo bloco de pista, compare-as.
As células ocupadas pelo bloco em toda colocação legal são preenchidas forçadas. Essa é a forma mais geral do método de sobreposição apresentado anteriormente.
Limites também podem criar vazios forçados
Se uma célula fica fora do alcance legal de todos os blocos, ela é forçadamente vazia.
Assim, limites de colocação sustentam os dois lados da resolução de linha:
- interseção das colocações legais de um bloco → preenchimento forçado;
- fora da união do alcance de todos os blocos → vazio forçado.
Análise passo a passo de limites
- preserve a identidade das pistas na ordem fixa;
- coloque todas as pistas anteriores o mais cedo possível para encontrar o limite mais cedo de um bloco;
- coloque todas as pistas posteriores o mais tarde possível para encontrar seu limite mais tarde;
- respeite marcas X e fragmentos preenchidos conhecidos nos dois cálculos;
- compare o intervalo legal de cada bloco;
- marque apenas estados compartilhados por toda colocação válida;
- repita depois de novas deduções.
Esse raciocínio é muito próximo da abordagem left-most/right-most usada por solvers de nonogramas.
Erros comuns
Tratar pistas do mesmo tamanho como intercambiáveis
Mesmo duas pistas com o mesmo número têm identidades diferentes porque sua ordem é fixa.
Calcular um limite sem reservar espaço para pistas posteriores
Um bloco não pode usar células que tornem impossível completar o restante da sequência.
Usar apenas as células extremas de início
O bloco inteiro ocupa várias células. Os limites descrevem intervalos para todo o bloco, não apenas seu primeiro quadrado.
Preencher todas as células entre o alcance mais cedo e mais tarde
Esse intervalo representa ocupação possível, não garantida. Use a interseção para obter preenchimentos forçados.
O que aprender depois
Limites de colocação são uma representação compacta de muitas possibilidades. Padrões válidos de linha vão além, considerando todo arranjo completo que satisfaz as pistas e os estados conhecidos.
FAQ
As posições mais cedo e mais tarde bastam para resolver toda linha?
Não. Métodos de colocações extremas são fortes, mas não completos em toda linha restrita. Algumas deduções exigem considerar o conjunto completo de padrões válidos.
Os limites funcionam igualmente em linhas e colunas?
Sim. “Mais cedo” significa mais à esquerda em linhas e mais acima em colunas; “mais tarde” significa mais à direita ou mais abaixo.
Os limites de um bloco podem convergir para uma única colocação?
Sim. Se a posição mais cedo e a mais tarde coincidirem, a posição exata do bloco está fixada.