Força
Força
Técnicas associadas
É adivinhação? A controvérsia das Cadeias forçadas
As Cadeias forçadas não são adivinhação quando usadas como técnica de prova. Você examina temporariamente todos os ramos a partir de um ponto de partida escolhido, propaga cada ramo logicamente e mantém apenas as conclusões que todos os ramos sustentam ou as conclusões forçadas por uma contradição.
A diferença fundamental em relação à adivinhação é o compromisso. Uma adivinhação escolhe um ramo e continua como se ele fosse verdadeiro. Uma cadeia de forçamento compara todos os ramos relevantes a partir do ponto de partida e age apenas quando a comparação prova algo.
As Cadeias forçadas são menos elegantes que as técnicas baseadas em padrões, mas suas conclusões são comprovadamente corretas quando todos os ramos foram verificados com precisão.
Cadeia de Forçamento Célula
Comece por uma célula de dois valores {A, B}. Propague as implicações de cada ramo. Compare os resultados.
Contradição: um ramo é inválido, então a célula deve ser o outro candidato.
Convergência na colocação: ambos os ramos forçam o mesmo dígito na mesma célula distante.
Convergência na eliminação: ambos os ramos eliminam o mesmo candidato da mesma célula.
Cadeia de Forçamento por Região (Cadeia de Forçamento por Dígito)
Comece pelas 2-3 posições de um dígito numa casa. Explore cada posição como um ramo. Os mesmos três tipos de dedução.
O forçamento Célula é eficaz quando as células de dois valores têm implicações de longo alcance. O forçamento por região é eficaz quando a posição de um dígito tem fortes efeitos em cascata.
Rede de Forçamento: Ampliando o Número de Ramos
Rede de Forçamento Célula: células com 3-6 candidatos. Rede de Forçamento por Região: casas com 4-6 posições para um dígito. Mais ramos, mais custoso, mas pode encontrar deduções que Cadeias forçadas não consegue.
A lógica é idêntica. Só o número de ramos difere.
O Motor de Propagação
Cada ramo se propaga por singulares nus, singulares ocultos, Candidatos Trancados e pares nus, iterativamente até estabilizar. Uma única suposição pode se propagar por dezenas de etapas intermediárias em todo o tabuleiro.
Quando dois ramos chegam à mesma conclusão por caminhos completamente diferentes, a convergência prova a conclusão com certeza.
Os Três Tipos de Dedução
Contradição: Um ramo produz um estado inválido. Essa suposição é falsa. O tipo mais comum.
Convergência na Colocação: Todos os ramos forçam o mesmo dígito na mesma célula. Menos comum, mas decisivo.
Convergência na Eliminação: Todos os ramos eliminam o mesmo candidato da mesma célula. O tipo mais subtil.
Quando Usar Técnicas de Força
Último recurso lógico. Aplicado depois de falharem as técnicas baseadas em padrões e as cadeias mais limpas.
Cadeias forçadas com 2-3 ramos são tentados primeiro. As Redes de Força com 3-6 ramos são mais dispendiosas e costumam ser reservadas para mais tarde. Ambas são Nível 12 (Extremo).
Para solucionadores de computador, a força limitada é um poderoso motor de prova, mas não é automaticamente completa. A completude só surge se a busca puder expandir-se o suficiente para cobrir as suposições necessárias, o que se aproxima do retrocesso exaustivo. Na prática, a força descreve-se melhor como uma busca lógica controlada do que como uma garantia de que qualquer solucionador de profundidade fixa resolva todos os puzzles válidos.
Uma Nota Filosófica sobre Elegância e Completude
As técnicas baseadas em padrões revelam relações estruturais e são mais elegantes. Mas existem puzzles válidos que exigem lógica ao nível da força. As técnicas de força são a rede de segurança que apanha todos os puzzles que as técnicas baseadas em padrões não conseguem resolver.
A abordagem mais satisfatória: tentar primeiro todas as técnicas baseadas em padrões e só recorrer à força quando o puzzle o exigir genuinamente.
Resumo
Cadeias forçadas e as redes de força estão entre as técnicas lógicas mais poderosas, ao Nível 12 (Extremo). Exploram todos os ramos a partir de um ponto de partida escolhido, propagam consequências e comparam resultados. As deduções surgem por contradição, convergência na colocação ou convergência na eliminação. São o último recurso antes do retrocesso por força bruta; se expandidas sem limites práticos, tornam-se uma prova de busca completa, mas a força limitada ao estilo humano continua a ser uma técnica avançada direcionada.
Técnicas associadas