Como resolver um puzzle Sudoku se todos os campos vazios restantes têm múltiplas possibilidades? Será que adivinhar é a única maneira

Como resolver um quebra-cabeça Sudoku se todos os campos vazios restantes têm múltiplas possibilidades? Adivinhar é a única maneira?

Eu estou escrevendo sobre sudoku todos os dias, em Sudoku_meta - r/Sudoku_meta Esta pergunta é bastante comum, e também é bastante comum que as respostas sejam incompletas ou mesmo incorretas. "Adivinhação" não foi definida, e as pessoas usam a palavra sem defini-la. Vamos estabelecer isto desde o início:

Todos os sudoku próprios têm uma única solução, por definição de "próprio". Além disso, há muito tempo existem programas de computador que podem resolver rapidamente qualquer sudoku próprio - ou, para sudoku impróprio, mostrar que não tem solução, ou listar várias soluções, o SW Solver irá aparecer até 500. Estes programas não adivinham. Em geral, os computadores não adivinham, ponto final. Em vez disso, eles processam listas, e são rápidos o suficiente para começar com uma lista de resoluções possíveis e escolher a primeira e ver o que acontece, e eles podem fazer escolhas adicionais, e depois fazer backup quando encontrarem contradições. Este é o Thread de Ariadne, e é uma técnica lógica, não é um "palpite"

Foi descrita uma falange de padrões lógicos que podem ser usados para resolver sudoku, mas existem puzzles onde todos os padrões conhecidos não são suficientes. Estes são chamados de "unsolvables", e você raramente verá um, a menos que você os procure. Eles ainda podem ser resolvidos, e isso não envolve adivinhar, o que levaria muito tempo. Em vez disso, o método que temos usado é recursivo, eu o chamo de Bivalue Ariadne's Thread (BAT). Ele escolhe uma resolução proposta a partir de um par. Isso é muito mais eficiente do que fazer qualquer escolha (que seria mais apropriadamente chamada de "adivinhação"). E então ele usa técnicas normais dentro dessa escolha para encontrar contradição ou resolução, e se isso chegar a um impasse, então ele faz uma escolha adicional de BAT. E assim por diante. Quando encontra uma contradição, ela faz marcha atrás. ("backtracking") Para quebrar um grande insolúvel desta forma parece demorar cerca de quatro horas com até quatro horas além de provar "solução única"

Olhar para um par e experimentar um membro dele é uma velha técnica de resolução, chamada Nishio. Um Nishio também pode ser sugerido por um padrão de candidato. Se um candidato está mostrando um "ciclo de caixa", com dois candidatos em cada caixa de quatro em um ciclo, e uma caixa tem três candidatos, eu sei que um deles pode ser eliminado. Qual deles? Bem, eu tento a "célula do cotovelo" e vejo o que acontece, e ou ela cria uma contradição ou resolve o ciclo. Se isso acontecer, posso ver como mover essa escolha para uma das outras três possibilidades irá criar uma contradição. Assim, isso eliminará esse candidato. Isto pode resolver todo o ciclo ou pode deixá-lo como um "ciclo perfeito" que não pode ser resolvido em si mesmo. Ele será resolvido por alguma célula que não seja o candidato a ser examinado.

Tem sido dadas poucas atenções, em geral, à resolução da heurística. Descobri que quando um quebra-cabeça tem um número de pares (pares de células ou regiões), e pondo de lado "insolváveis", correntes de coloração de qualquer par de sementes geralmente geram resultados, seja eliminações mútuas ou resoluções mútuas.

A coloração é feita sem escolher ou preferir qualquer um dos candidatos. Não é um palpite. É uma análise lógica, mas muitas vezes mais complexa do que pode ser feita na cabeça de alguém. O que as pessoas chamam de "lógica", em resolver sudoku, é muitas vezes apenas o que elas podem ver imediatamente.

Se uma análise de solução é muito complicada para ser vista sem documentação escrita, ela é chamada de "ruim". "Demasiado difícil." "Requer adivinhação", e outros pejorativos. Mas isto não tem nada a ver com lógica, no sentido comum. A coloração pode ser feita com tinta no papel, eu faço-o todos os dias. Acho que foi assim chamado porque as pessoas usavam lápis de cor, mas realmente significa marcar os candidatos distintamente, e pode ser feito com símbolos. Eu faço um círculo e "triângulo" entre os candidatos. Ultimamente, faço esta parte a lápis, com os candidatos marcados com tinta, então se eu decidir abandonar uma coloração, posso apagá-la facilmente, deixando os candidatos intocados.

Não é necessário "retroceder" se a coloração for usada. Ao invés disso, avança-se para a solução.

Guardar no sentido comum com sudoku pode ser uma estratégia pobre, ou uma estratégia poderosa e eficaz, dependendo de como é feita. E se um "palpite" é escolhido com base na análise mostrando que vai descobrir uma solução, não é realmente um palpite. É uma escolha informada.

Sudoku são puzzles lógicos, mas as pessoas misturam lógica com reatividade e julgamento e "bom" e "mau".

Mas uma resposta simples para a pergunta aqui: Não, adivinhar não é a única maneira. Não há sudoku que não possa ser resolvido pela análise lógica, e pelos humanos, não apenas pelo computador.