Como faço para resolver o ' sudoku mais difícil do mundo?

Adivinhando valores únicos em uma pesquisa em profundidade está abaixo do ideal.

Então, aqui está uma cadeia de raciocínio baseada em uma hipótese ampla / método de refutação (que meu enteado chama relutantemente de “adivinhação educada”).

Apenas seguir a cadeia incluindo contradições requer para resolver 23 variantes do sudoku, por isso é melhor usado com um solucionador auxiliado por computador. No entanto, não requer nenhum algoritmo sofisticado para segui-lo. (Eu uso meu próprio programa python não otimizado desenvolvido em casa, então não há computação real poder envolvido).

A notação segue as convenções da planilha (coluna = letra, linha = número) (ou xadrez, se preferir).

STA Original Sudoku G8: 3,9 HYP # I8: 3,9 DIS # I8: 3,9 # B1: 1,2 => CTR => B1: 6 STA # I8: 3,9 + B1: 6 DIS # I8: 3,9 + B1: 6 # A2: 1,2 => CTR => A2: 5,9 STA # I8: 3,9 + B1: 6 + A2: 5,9 DIS # I8: 3,9 + B1: 6 + A2: 5,9 # B5: 1,2 => CTR => B5: 3,8 DIS # I8: 3,9 + B1: 6 + A2: 5,9 + B5: 3,8 => CTR => I8: 2,7 STA I8: 2,7 HYP I8: 2,7 # G7: 5 DIS I8: 2,7 # G7: 5 # G4: 6 => CTR => G4: 1,8 STA I8: 2,7 # G7: 5 + G4: 1,8 DIS I8: 2,7 # G7: 5 + G4: 1,8 # C5: 2,9 => CTR => C5: 6 STA I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 # H3: 4,5 => CTR => H3: 8 DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 + H3: 8 => CTR => G7: 3,9 STA I8: 2,7 + G7: 3,9 HYP I8: 2,7 + G7: 3,9 # A8: 3,4,6 DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 # A9: 3 => CTR => A9: 6,7 STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 # D7: 2,7 => CTR => D7: 4,9 STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 PRF I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 => SOL 

Coloquei capturas de tela das etapas e uma explicação rápida do método em World “s Hardest Sudoku . Como estou interessado apenas em resolver quebra-cabeças difíceis por “adivinhação instruída”, descobri que este sudoku não é tão difícil quanto anunciado (1 nível de hipótese + 1 análise à frente = 2 níveis de hipóteses). Na verdade, ainda não encontrei um sudoku que requeira mais de 2 níveis de hipóteses + uma análise à frente (= 3 níveis de hipóteses).

Comentários

• Quão bem seu solucionador se compara a sudoku ‘ s com 17 entradas? Por exemplo. theconversation.com/…
• @SimonStreicher O sudoku de 17 pistas, você está citando é difícil, mas não entre os sudokus mais difíceis no contexto do meu algoritmo. Geralmente, não há correlação entre o número de pistas e a dureza de um sudoku. Coloquei algumas estatísticas sobre o sudokus que analisei.
• @SimonStreicher eu tenho analisou a lista dos 95 principais sudokus (ou seja, os 95 quebra-cabeças difíceis ). Existem 5 sudukos com nível difícil (2 níveis de hipóteses são necessários), que ainda está 2 níveis abaixo do 101 sudokus mais difícil I encontrei.
• Obrigado pela informação, eu ‘ ainda estou tentando entender tudo isso, felizmente seu site é bastante completo.
• @SimonStreicher O cerne disso é reduzir o espaço de busca da ativação de valores únicos para padrões facilmente reconhecíveis (pares) que são usados para gerar decisões binárias com eliminação aumentada de possibilidades. Por exemplo.cell1 permite 2 valores possíveis v1 e v2, cell2 permite os mesmos valores possíveis, mas, adicionalmente, uma ou mais outras possibilidades v3, v4, v5. Portanto, a célula1 e a célula2 são um par (ambas contêm v1 e v2) ou a célula 2 pode ser apenas uma de v3, v4, v5. Esta hipótese é então verificada.

Para este quebra-cabeça, embora tenha uma e apenas uma solução, nenhum padrão conhecido funciona nele, a não ser uma suposição e verificação um pouco mais inteligente. O número de etapas que uma pessoa deve observar para reduzir as pistas é a métrica aqui, e este quebra-cabeça precisa de nove suposições sequenciais para chegar a um estado solucionável.

O solucionador no SudokuWiki não pode obtê-lo porque simplesmente demoraria muito para fazê-lo em Javascript e não está programado para adivinhar números.

A solução requer que se assuma os valores dos quadrados e, em seguida, reduza o quebra-cabeça para ver se você precisa de mais suposições – se precisar, faça outra e continue. É uma busca profunda das soluções possíveis, em essência. O solucionador em sudoku-solutions apresenta a solução para esse quebra-cabeça, mas quando solicitado a fornecer as etapas, declara:

Este solucionador não conseguiu resolver o quebra-cabeça completamente pela lógica, isso não significa que não haja uma solução lógica.

e então prontamente falha em listar qualquer uma das etapas usadas para resolvê-lo. Isso só acontece quando o solucionador deve usar a suposição de ramificação de força bruta para encontrar a solução.

Como resultado, não há como eu mesmo poder fornecer uma resposta “como resolver este quebra-cabeça”, desde que fiz isso envolveria encontrar essas cadeias específicas e explicar por que a outra grande quantidade de cadeias não funciona.

Mas é assim que você faz: suponha que um quadrado é um número, depois outro, depois outro, e continue verificando até que você encontre uma sequência que ainda faça sentido e permita que você resolva o quebra-cabeça, ou você chegue a uma contradição e precise voltar e tentar novamente. Acho que esta é a melhor resposta que você pode obter para esta pergunta.

Já que você pediu uma solução para o quebra-cabeça, no entanto, posso fornecê-la (passe o mouse sobre o bloco de spoiler):

Comentários

• Boa e velha recursão.
• Eu consegui resolvê-lo com profundidade de recursão de no máximo 2 suposições. O ” Naked Singles ” a estratégia foi executada um total de 61812 vezes (depois de algum cache feito em um nível superior, sem que a contagem de execuções fosse de milhões), ” Singles ocultos ” estratégia 32892 vezes (mais outros 28920 que foram servidos de um cache) e uma pesquisa com profundidade apenas 1 foi executada 256 vezes e servido a partir do cache mais 15 vezes (em cada ponto apenas uma suposição foi feita, embora eu acredite que a maioria dessas execuções realmente aconteceram dentro da próxima), e a pesquisa de dois níveis (onde você ‘ d faz 2 suposições) só foi executada uma vez e conseguiu.
• (também este é o único quebra-cabeça que não div id = “8d567e9d73”>

Baixe o solucionador do Sudoku do primeiro-ministro de Cingapura e alimente-o com este quebra-cabeça (SOMENTE se você estiver REALMENTE preso). Acredite ou não, aquele primeiro-ministro fez um programa bastante robusto e, embora pareça que vai ficar preso por um tempo lá, eventualmente chega com a seguinte solução:

862 || 751 || 349
943 || 628 || 157
571 || 493 || 286
============
159 || 387 || 624
386 || 245 || 791
724 || 169 || 835
============
217 || 934 || 568
438 || 576 || 912
695 || 812 || 473

Aparentemente é possível resolver com lógica, porém, segundo o cara que inventou o quebra-cabeça. Os solucionadores levaram apenas 24 horas para fazer isso.

Observação: este quebra-cabeça tem o 1 na 7ª linha em uma posição diferente da pergunta “s. Esse quebra-cabeça tem várias soluções.

Comentários

• Duvido que este quebra-cabeça original tenha várias soluções (se estiver implícito). Sua entrada para o PM ‘ O solucionador provavelmente está errado: linha 3, coluna 7 é fornecida como entrada como ” 1 “, não ” 7 ” (um dos observadores). Dada a entrada correta para o exe, ele produz a solução conhecida.
• @SimonStreicher a entrada errada está na linha 7, coluna 3, onde o 7 deveria ser 1
• Ele travou por mais de 5 segundos? Meu solucionador muito simples consegue resolver isso quantidade de tempo.

Apenas para adicionar outra solução baseada em computador, usando a Linguagem de modelagem MiniZinc você pode escrever o seguinte programa:

int: n; array[1..n, 1..n] of 0..n: initial_grid; int: reg; array[1..n, 1..n] of 1..reg: regions; array[1..n, 1..n] of var 1..n: final_grid; include "alldifferent.mzn"; constraint forall(r, c in 1..n)(initial_grid[r, c] = 0 \/ initial_grid[r, c] = final_grid[r, c]); constraint forall(r in 1..n)(alldifferent([ final_grid[r, c] | c in 1..n ])); constraint forall(c in 1..n)(alldifferent([ final_grid[r, c] | r in 1..n ])); constraint forall(region in 1..reg)(alldifferent([ final_grid[r, c] | r, c in 1..n where regions[r, c] = region ])); solve satisfy; output [ show_int(1, final_grid[r, c]) ++ if c = n then ("\n" ++ if (r mod 3 = 0 /\ r < n) then "---------------------\n" else "" endif ) elseif c mod 3 = 0 then " | " else " " endif | r, c in 1..n ]; 

Junto com os dados apropriados arquivo:

n = 9; reg = 9; regions = array2d(1..9, 1..9, [ 3 * (row div 3) + col div 3 + 1 | row, col in 0..8 ]); initial_grid = [| 8, 0, 0, 0, 0, 0, 0, 0, 0, | 0, 0, 3, 6, 0, 0, 0, 0, 0, | 0, 7, 0, 0, 9, 0, 2, 0, 0, | 0, 5, 0, 0, 0, 7, 0, 0, 0, | 0, 0, 0, 0, 4, 5, 7, 0, 0, | 0, 0, 0, 1, 0, 0, 0, 3, 0, | 0, 0, 1, 0, 0, 0, 0, 6, 8, | 0, 0, 8, 5, 0, 0, 0, 1, 0, | 0, 9, 0, 0, 0, 0, 4, 0, 0 |] ; 

E usando o solucionador padrão em um laptop bastante comum, a solução sai em 100 ms, o que supera a implementação C ++ de PM Lee por um considerável margem.

Comentários

• Este algoritmo é baseado em programação linear?
• It ‘ s no mesmo domínio – o solucionador é um solucionador de programação de restrições, que funciona bem, já que o problema não é ‘ t realmente linear, mas é um monte de restrições. Ele usa um combinação de heurísticas para reduzir o espaço de soluções possíveis com alguns métodos de pesquisa bastante básicos.
• Eu ‘ estou impressionado. Meu manual, muito simples assim Lver em Kotlin supera em cerca de 5 segundos no meu laptop, usando uma profundidade de pesquisa de no máximo 2.