Um computador pode resolver o sudoku sem simplesmente substituir os números e verificar?

Sudoku significa Sudoku bem formado (isto é, com uma e apenas uma solução).

Substituir apenas todos os números indecisos e verificar levaria muito tempo.

O método de pesquisa mais rápido combina a pesquisa de profundidade-primeiro (adicionar possíveis números um por um) com a propagação de restrições elementares (ECP): cada vez que você testar um número possível, exclua todos os candidatos que estão ligados a ele por uma contradição direta (de acordo com as regras).

A pesquisa de profundidade-primeiro aceita uma solução assim que ela for encontrada. Pode encontrar várias soluções, se houver. Mas se parar na primeira solução (como geralmente é feito quando o puzzle é conhecido por ser bem formado), não prova a sua singularidade. Neste sentido, a busca em profundidade permite alguma forma de adivinhação.

Eu mostrei que outro procedimento de busca muito simples sem adivinhação, Trial-and-Error (T&E), requer apenas dois níveis de hipóteses para todos os Sudokus 9x9 conhecidos (e provavelmente para todos os Sudokus 9x9) e que apenas um nível é suficiente para todos, exceto uma proporção muito pequena de puzzles 9x9 (~ 1 em 30.000.000).

Agora, para responder sua pergunta: sim, a maioria dos Sudokus 9x9 pode ser resolvida sem usar a busca de profundidade-primeiro ou mesmo T&E, usando uma abordagem "baseada em padrões" de satisfação de constrangimento. Basicamente, isso significa usar regras que podem ser usadas por solucionadores humanos. Uma questão é, que tipos de regras se considera como aceitáveis ou não. Todos os quebra-cabeças no nível 0 ou 1 do T&E podem ser resolvidos por um tipo de corrente que chamei de "trança".

Para detalhes, veja meu livro "Pattern-Based Constraint Satisfaction and Logic Puzzles" (a 1ª edição é gratuita.)