Jak vyřeším nejtvrdší sudoku na světě '?

Hádání jednotlivých hodnot v hloubkovém hledání je neoptimální.

Tady je tedy logický řetězec založený na metodě hypotézy / vyvrácení první šíře (kterou můj nevlastní syn neochotně nazývá „poučené hádání“).

Pouhé sledování řetězce včetně rozporů vyžaduje k vyřešení 23 variant sudoku, takže se nejlépe používá u počítačově podporovaného řešiče. K jeho dodržování však není třeba žádných vymyšlených algoritmů. (Používám svůj vlastní domácí neoptimalizovaný program pythonu, takže neexistují žádné skutečné výpočty zapojená síla).

Zápis se řídí konvencemi tabulky (sloupec = písmeno, řádek = číslo) (nebo šachy, pokud chcete).

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 

Na stránce Nejtěžší sudoku na světě jsem uvedl snímky obrazovky s kroky a rychlé vysvětlení metody. Jelikož se zajímám pouze o řešení tvrdých hádanek pomocí „poučeného hádání“, zjistil jsem, že toto sudoku ve skutečnosti není tak těžké, jak je inzerováno (1 úroveň hypotézy + 1 lookahead = 2 úrovně hypotéz). Ve skutečnosti jsem zatím nenašel sudoku, které vyžaduje více než 2 úrovně hypotéz + jeden lookahead (= 3 úrovně hypotéz).

Komentáře

• Jak dobře řeší váš řešitel proti sudoku ‚ s 17 položkami? Např. theconversation.com/…
• @SimonStreicher Sudoku se 17 stopami, citujete je tvrdý, ale nepatří mezi nejtěžší sudokus v kontextu mého algoritmu. Obecně neexistuje žádná korelace mezi počtem stop a tvrdostí sudoku. Zveřejnil jsem nějaké statistiky o analyzovaném sudokusu.
• @SimonStreicher Mám analyzoval seznam top 95 sudokus (konkrétně 95 tvrdých hádanek ). Existuje 5 sudukosů s úrovní tvrdou (jsou nutné 2 úrovně hypotéz), což je stále 2 úrovně pod 101 nejtvrdším sudokusem I našel.
• Děkuji za informace, ‚ se stále snažím toto všechno pochopit, naštěstí je váš web docela důkladný.
• @SimonStreicher Jádro je o zmenšení prostoru hledání z aktivace jednotlivých hodnot na snadno rozpoznatelné vzory (páry), které se používají ke generování binárních rozhodnutí se zvýšenou eliminací možnosti. Např.cell1 umožňuje 2 možné hodnoty v1 a v2, cell2 umožňuje stejné možné hodnoty, ale navíc jednu nebo více dalších možností v3, v4, v5. Cell1 a cell2 jsou tedy dvojice (obě obsahují v1 a v2) nebo buňka 2 může být pouze jedna z v3, v4, v5. Tato hypotéza je poté zkontrolována.

U této hádanky, i když má jedno a jediné řešení, na tom nefungují žádné známé vzory, kromě o něco inteligentnějšího odhadu a kontroly. Počet kroků, které je třeba hledat dopředu, aby se snížily stopy, je zde metrika a tato hádanka potřebuje devět postupných odhadů, aby se dosáhlo řešitelného stavu.

Řešitel na SudokuWiki jej nemůže získat, protože by to v Javascript jednoduše trvalo příliš dlouho a není naprogramován tak, aby hádal čísla.

Řešení vyžaduje, aby jeden převzal hodnoty čtverců, a poté zmenšil hádanku, aby zjistil, zda potřebujete více předpokladů – pokud ano, vytvořte další a pokračujte. Jedná se v zásadě o hloubkové hledání možných řešení. Řešitel v sudoku-solutions přijde s řešením této hádanky, ale když bude požádán o poskytnutí kroků, prohlásí:

Tento řešitel logiku nedokázal vyřešit úplně, to neznamená, že neexistuje logické řešení.

a poté neprovede seznam žádných kroků, které k jeho vyřešení použil. K tomu dojde, pouze když řešitel musí k nalezení řešení použít hádání větvení hrubou silou.

Ve výsledku neexistuje způsob, jak bych sám mohl rozumně poskytnout odpověď „jak vyřešit tuto hádanku“, protože zahrnovalo by to nalezení těchto konkrétních řetězců a vysvětlení, proč ostatní obrovské množství řetězců nefunguje.

Ale takhle to děláte: předpokládejme, že čtverec je číslo, pak další, pak další, a pokračujte v kontrole, dokud nedojdete k posloupnosti, která má stále smysl a umožňuje vám vyřešit hádanku, nebo nedojde k rozporu a budete muset couvnout a zkusit to znovu. Obávám se, že si myslím, že je to nejlepší odpověď, kterou na tuto otázku můžete získat.

Protože jste požadovali řešení hádanky, mohu ji poskytnout (myší přes blok spoileru):

Komentáře

• Stará dobrá rekurze.
• Dokázal jsem to vyřešit s hloubkou rekurze maximálně 2 odhady. Naked Singles “ proběhla celkem 61812krát (po nějakém ukládání do mezipaměti na vyšší úrovni, bez toho je počet běhů v milionech), “ Hidden Singles “ strategie 32892krát (plus dalších 28920, které byly poskytovány z mezipaměti) a bylo provedeno vyhledávání pouze s hloubkou 256 krát a obsluhováno z mezipaměti dalších 15krát (v každém bodě byl proveden pouze jeden odhad, i když se domnívám, že většina z těchto běhů se skutečně stala v příštím), a dvouúrovňové vyhledávání (kde ‚ d provedete 2 odhady) proběhlo pouze jednou a dostalo ho.
• (také toto je jediná hádanka, která ‚ t crack s mým programem pouze s JEDNOU úrovní hádání)

Stáhněte si předsedu vlády singapurského řešení sudoku a nahrajte jej touto hádankou (POUZE, pokud jste opravdu uvízli). Věřte tomu nebo ne, ten premiér vytvořil docela robustní program, a ačkoli to vypadá, že se tam na chvíli zasekne, nakonec přijde s následujícím řešením:

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

Zdá se, že je to možné vyřešit logicky, podle toho, kdo vymyslel tuto hádanku. Řešitelům to trvalo jen 24 hodin.

Poznámka: Tato skládačka má 1 na 7. řádku v jiné pozici jako otázka. Tato skládačka má několik řešení.

Komentáře

• Pochybuji, že tato původní logická hra má několik řešení (pokud z toho vyplývá). Váš vstup do PM ‚ s řešič je pravděpodobně špatný: řádek 3, sloupec 7 je uveden jako vstup jako “ 1 „, ne “ 7 “ (jeden z pozorovatelů). Při správném vstupu do souboru exe vygeneruje známé řešení.
• @SimonStreicher špatný vstup je na řádku 7 sloupci 3, kde 7 by měla být 1
• Zasekne se na déle než 5 sekund? Můj velmi jednoduchý řešitel to zvládne množství času.

Stačí přidat další počítačové řešení a poté použít MiniZinc modeling language můžete napsat následující program:

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 ]; 

Spolu s příslušnými údaji file:

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 |] ; 

A pomocí výchozího řešiče na poměrně standardním notebooku vychází řešení za 100 ms, což značně překonává implementaci C ++ PM Leeho značným okraj.

Komentáře

• Je tento algoritmus založen na lineárním programování?
• Je ‚ s ve stejné sféře – řešič je řešitel programování omezení, což funguje dobře, protože problém není ‚ opravdu lineární, ale je to spousta omezení. Využívá kombinace heuristiky ke zmenšení prostoru možných řešení s některými poměrně základními metodami vyhledávání.
• Jsem ‚ m ohromen. Můj manuál, velmi jednoduchý, takže lver v Kotlinu to na mém notebooku překoná asi za 5 sekund, při použití hloubky vyhledávání maximálně 2.