Como resolver esse quebra-cabeça Loopy de forma eficiente com poucos retrocessos?

Question

Eu gostaria de resolver este quebra - cabeça Loopy (Cairo) :

Mas eu gostaria de fazer isso com o mínimo de retrocesso possível. Com isso, quero dizer que quero ter no máximo uma estimativa pendente de cada vez; Não quero fazer mais suposições, se já fiz uma que ainda não foi refutada. Acredito que seja possível usar alguns padrões locais, mas ou não encontrei padrões locais suficientes para me ajudar, ou é na verdade mais difícil fazer isso do que apenas adivinhar mais e retroceder mais. Consegui resolver esse quebra-cabeça, mas demorei muito para encontrar caminhos de pesquisa adequados que só tinham uma estimativa pendente por vez.

Para colocar minha pergunta de outra forma, qual é a solução puramente lógica mais curta que você pode apresentar para encontrar a solução para esse quebra-cabeça e provar que ele é único?

Aqui está um ponto em que não pude prosseguir localmente:

Em seguida, usei o backtracking de 1 suposição para obter o seguinte (ou seja, em cada um dos 3 lugares, a remoção dessas arestas levaria a uma contradição):

Answer 1

Ok, resolvi todo o quebra-cabeça :) Vou usar esse quebra-cabeça específico para mostrar várias deduções interessantes. Cada imagem mostrará uma dedução que considero não trivial e, entre as imagens, farei deduções triviais. Nesta postagem, as deduções "triviais" são:

• se uma célula tem todas as suas bordas definidas (por exemplo, um 3 que tem uma borda sombreada), eu removo todas as outras bordas
• se uma célula tem apenas o número mínimo de bordas restantes (por exemplo, um 3 que tem 2 bordas removidas), eu marco todas as outras bordas como usadas
• se uma linha tem apenas uma outra linha para a qual ela poderia se estender, eu a estendo
• se uma borda criar uma bifurcação no loop, eu a removo
• se uma borda fechasse o laço, eu removo

Cada dedução terá sua área circulada. Alguns também têm setas apontando para linhas importantes. Se você quiser calcular as deduções sozinho, clique apenas no primeiro spoiler de cada par para ver onde será a dedução. Em minhas explicações, um dígito se refere a um número de pista e um número soletrado se refere a uma quantidade . Alguma terminologia que utilizo aqui:

• "lados" e "bordas" são usados ​​indistintamente para se referir às bordas de uma única célula-pista
• "paredes" e "linhas" são termos genéricos para uma seção confirmada de loop
• "canto" é um local onde várias fronteiras possíveis se encontram
• Lados "descobertos" são aqueles que devem ser usados ​​juntos para fins de conectividade - por exemplo, qualquer um dos lados da fronteira externa

Para as deduções!

A dedução:

Os 4 podem ter apenas 1 borda não utilizada. Essa borda tem que ser uma daquelas adjacentes à linha que vem do 3; se ambas as bordas adjacentes são usadas, isso cria uma bifurcação no loop. Portanto, cada borda não adjacente à linha 3 deve ser usada

A dedução:

Isso é semelhante à dedução anterior. O 3 tem que usar um, e apenas um, de seus lados restantes. Não importa qual lado seja usado, o lado 3 agirá da mesma forma que o tamanho da dedução anterior. Portanto, todos os lados do 4 que não são adjacentes ao 3 devem ser usados.

A dedução:

Aqui, a mesma dedução pode ser usada duas vezes. Ambos os 2s precisam usar exatamente um dos dois lados restantes. Ambos os lados usarão o canto "do meio". A linha que não faz fronteira com o 2, mas conectada ao canto "do meio", deve ser usada para evitar o uso de ambas as bordas restantes do 2.

A dedução:

Esta é uma dedução semelhante à anterior. Um, e apenas um, dos lados restantes do 1 deve ser usado, portanto, o lado externo que se conecta ao "canto" do meio deve ser usado. Eu marquei com uma seta para maior clareza. Uma vez que é usado, então podemos aplicar o inverso desta dedução ao 3. Um, e apenas um, dos 3 lados restantes deve ser usado - e o lado que colorimos deve ser o conector de "canto" externo, já que apenas um lado externo pode ser usado. (Se ambos forem usados, os lados do 3 criarão uma bifurcação)

As deduções (duas relacionadas):

Existem duas paredes "nuas" de um lado do 3 que devem ser usadas juntas e, em seguida, três outras. Se as paredes "nuas" não forem usadas, uma bifurcação é criada com as outras três paredes e a linha do 1. Portanto, as paredes "nuas" são usadas. Agora, apenas mais uma parede pode ser usada. Se a parede para a qual a seta está apontando for usada, a linha do 1 não pode ser estendida. Portanto, essa parede não é usada.

As deduções (duas relacionadas):

Existem duas linhas que conduzem ao 2. Estender qualquer um deles usará um dos dois lados atribuídos. São todos os lados que podem ser usados, portanto a linha com uma seta apontando para ela não pode ser usada. Dado que esse lado não é usado, as duas bordas do vizinho 2 agora estão "nuas" e devem ser usadas juntas. Exceto que não podem ser, uma vez que um lado desse 2 já está sendo usado. Portanto, nenhuma dessas bordas pode ser usada.

A dedução:

O 3 circulado tem dois lados "nus". Se não forem usados, restam apenas dois lados, o que é muito pouco. Portanto, os lados "nus" são usados.

As deduções (duas relacionadas):

O lado esquerdo circulado 1 tem dois lados "nus". Eles não podem ser usados, pois os dois lados são demais para um 1 usar. O lado direito circulado 1 tem uma linha que conduz a ele. Se qualquer um dos lados não adjacentes a essa linha for usado, a linha não terá para onde se estender. Portanto, todos os lados não adjacentes não são usados.

As deduções (duas relacionadas):

O lado esquerdo com um círculo 3 tem apenas duas maneiras de usar exatamente três lados: os dois superiores "nus" e o lado direito, ou os dois inferiores "nus" e o lado direito. Disto é claro que o lado direito deve ser usado, e o lado que conduz a ambos os lados "nus" da esquerda deve ser usado. O lado direito com um círculo 4 tem uma linha que leva ao topo e à base (porque pelo menos um dos dois lados restantes para o 3 inferior deve ser usado). Apenas uma de cada borda adjacente a essas linhas de entrada pode ser usada, para evitar uma bifurcação no loop. Para usar três bordas, então, o único lado não adjacente deve ser usado.

A dedução:

A linha que leva a esta seção inferior (seta preta) deve subir em algum ponto para se conectar ao resto do loop. Para subir, deve-se utilizar a linha apontada pela seta vermelha.

Para completar, a solução:

Em resposta aos comentários:

Parece que você estava pedindo uma solução lógica para sua segunda foto, não para a terceira. Abaixo, apresento essa solução. Desta vez, pulo todas as deduções triviais, bem como as deduções que cobri nas fotos acima.

As deduções (duas relacionadas)

O 2 circulado tem apenas três lados disponíveis e um canto entre dois desses lados tem uma linha que conduz a ele. Apenas uma borda de cada lado dessa linha pode ser usada, portanto, a única borda não adjacente deve ser usada. Além disso, o lado de entrada não pode dobrar para fora do 2, pois isso removeria ambas as bordas do 2 em torno desse canto, portanto, o lado inferior de 2 não pode ter seu lado superior usado

A dedução:

O 2 pode usar seus dois lados "descobertos" juntos ou seus outros dois lados. De qualquer maneira, o 4 deve usar seus 3 lados inferiores.

As deduções (duas relacionadas):

Tanto o 1 quanto o 4 têm a mesma dedução, abordada acima: o "canto do meio" deve ter um lado que sai dele, para conectividade. Isso também significa que os lados não "descobertos" do 2 da última dedução devem ser usados, em vez dos lados "descobertos".

A dedução:

Nem o 2 nem o 3 podem usar seus cantos compartilhados sozinhos. Se o 2 fizesse, então o 3 seria forçado a fazer um garfo, e se o 3 fizesse, então o 2 teria apenas um lado para usar. Portanto, o 2 deve usar seu lado que não seja de canto e o 3 deve usar seus dois lados "descobertos".

A dedução:

Se o 4 não usar seus lados "descobertos", ele terá apenas três lados restantes. Portanto, ele usa seus lados "nus".

A dedução:

Se o 2 usar seu lado inferior, haverá três extremidades na área circulada. Três extremidades não podem se conectar entre si para formar um loop. Portanto, o 2 não usa seu lado inferior.

A partir daí, a solução é trivial.

Se algo for muito confuso, sinta-se à vontade para pedir esclarecimentos nos comentários.