Conjuntos quase fechados

Conjuntos quase fechados

Especialista

O que é um Conjunto Quase Fechado?

Um ALS são N células numa única casa com exatamente N+1 candidatos distintos. Está "quase fechado" -- remova um candidato e torna-se um subconjunto nu. O ALS mais simples é um célula de dois valores (1 célula, 2 candidatos). Todas as células devem partilhar uma casa.

O que é um Candidato Comum Restrito?

O RCC é um dígito que aparece tanto no ALS A como no ALS B, em que cada instância desse dígito em A vê cada instância desse dígito em B. Como os dois ALS não podem usar o RCC ao mesmo tempo, pelo menos um ALS tem de perder o RCC e tornar-se um conjunto fechado.

É essa pressão de conjunto fechado que cria as eliminações. Se os dois ALS também partilharem outro dígito Z, então Z tem de aparecer em pelo menos um dos ALS. Qualquer célula externo que veja todas as localizações possíveis de Z em ambos os ALS não pode conter Z.

ALS-XZ: A Regra Central dos Dois ALS

ALS-XZ usa dois ALS. Partilham um candidato comum restrito X e um segundo candidato comum Z. Como X não pode ocupar ambos os ALS, pelo menos um ALS é forçado a resolver-se sem X. Quando isso acontece, Z fica fechado nesse ALS, a menos que já esteja forçado no outro.

Portanto, Z tem de aparecer em algum lugar dos dois ALS. Elimine Z de qualquer célula que veja todos os candidatos Z em ambos os ALS. Nível 10 (Mestre).

Conjuntos quase fechados: Encontrar os ALS

A aplicação também lista Conjuntos quase fechados como técnica, porque reconhecer ALS é útil por si só. Um ALS não é uma eliminação até interagir com outro ALS, um célula de base ou uma interseção bloco-linha. A competência prática é aprender a identificar pequenos grupos de células cuja união de candidatos é apenas um dígito maior do que o número de células.

A maioria das técnicas baseadas em ALS começa por catalogar estes conjuntos e depois verifica se os seus candidatos partilhados têm a visibilidade necessária para um RCC.

Cadeia ALS: Ligar Vários Conjuntos quase fechados

Um Cadeia ALS liga vários ALS através de RCCs. Cada par vizinho tem um candidato comum restrito, e a cadeia alterna qual ALS é forçado a ficar fechado à medida que cada RCC é considerado.

O alvo de eliminação aparece tanto no primeiro como no último ALS. Se um célula externo vê todas as localizações possíveis do alvo em ambas as extremidades da cadeia, pode ser eliminado. Nível 11 (Extremo). ALS-XZ é a versão útil mais curta desta ideia.

Sue de Coq: O Padrão de Interseção de ALS

Sue de Coq explora a interseção de um bloco com uma linha ou coluna. Essa interseção contém duas ou três células que pertencem a ambas as casas. Os candidatos nessas células de interseção devem ser fornecidos pelo lado da linha, pelo lado do bloco ou pela própria interseção.

A técnica procura dois conjuntos auxiliares: um no resto da linha ou coluna, e outro no resto do bloco. Seus candidatos são disjuntos e, juntos, respondem pelos candidatos que podem ocupar a interseção. Quando a contagem está completa, os candidatos correspondentes podem ser removidos de outras células da mesma linha ou bloco.

Nível 9 (Mestre).

Flor da Morte: A Técnica ALS Caule-e-Pétala

Flor da Morte começa com um caule célula que tem N candidatos. Para cada candidato do caule, há uma pétala ALS correspondente. Se o caule assume um candidato, sua pétala pareada perde esse candidato e fica travada.

Independentemente do valor que o caule acabe assumindo, uma das pétalas é forçada ao seu estado travado. Se o mesmo dígito de eliminação aparece em todas as pétalas, então esse dígito deve ser fornecido por pelo menos uma pétala. Qualquer célula externo que veja todas as instâncias possíveis desse dígito nas pétalas pode eliminá-lo.

Nível 11 (Extremo).

Como Encontrar Padrões ALS

Catalogar os ALSs em cada casa. Procurar pares que compartilham candidatos com RCCs válidos. Para Sue de Coq, focar nas interseções bloco-linha. Para Flor da Morte, começar pelas células do caule com poucos candidatos.

Classificações de Dificuldade

Conjuntos quase fechados: Nível 9, Mestre

Sue de Coq: Nível 9, Mestre

ALS-XZ: Nível 10, Mestre

Cadeia ALS: Nível 11, Extremo

Flor da Morte: Nível 11, Extremo

Resumo

As técnicas ALS baseiam-se em dois conceitos: o Conjunto Quase Travado (N células, N+1 candidatos) e o Candidato Comum Restrito. Conjuntos quase fechados fornecem os blocos de construção; ALS-XZ, Cadeias ALS, Sue de Coq e Flor da Morte usam esses blocos em configurações diferentes. Juntas, formam uma das famílias mais poderosas para enfrentar os quebra-cabeças mais difíceis.