Hogyan tudom megoldani a világ ' legnehezebb sudoku-t?

Egyetlen érték kitalálása mélységes keresésben nem optimális.

Tehát itt van egy érvelési lánc, amely a legelső hipotézis / disszidens módszeren alapul (amelyet mostohafim vonakodva hív fel “képzett találgatásnak”).

A lánc csak az ellentmondásokat is követve megköveteli a sudoku 23 változatának megoldására, így a legjobban számítógéppel segített megoldóval használható. Ennek követéséhez azonban nem kell semmilyen fantasztikus algoritmus. (Saját otthoni, nem optimalizált python programomat használom, így nincs valós számítástechnika vagy az érintett erő).

A jelölés a táblázatkezelési szokásokat követi (oszlop = betű, sor = szám) (vagy ha akarja, sakkozni).

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 

A World legnehezebb Sudoku-jánál képernyőképeket készítettem a lépésekről és a módszer gyors ismertetéséről. Mivel csak a nehéz rejtvények megoldása érdekel “művelt találgatással”, rájöttem, hogy ez a sudoku valójában nem olyan nehéz, mint amennyit hirdetnek (1 szint hipotézis + 1 kinézet = 2 hipotézis szint). Valójában még nem találtam olyan sudokut, amelyhez több mint két szint hipotézis + egy tekintet (= 3 szint hipotézis) szükséges.

Megjegyzések

• Mennyire sikerül a megoldója a sudoku ‘ sekkel szemben 17 bejegyzéssel? Például. theconversation.com/…
• @SimonStreicher Az Ön által hivatkozott 17 nyomból álló sudoku nehéz, de algoritmusom összefüggésében nem tartozik a legnehezebb sudokusok közé. Általában nincs összefüggés a nyomok száma és a sudoku keménysége között. Tettem néhány statisztikát az általam elemzett sudokusokról.
• @SimonStreicher van elemezte a 95 legnépszerűbb sudokus listáját (nevezetesen a 95 kemény rejtvényeket ). 5 sudukó van hard szinttel (2 szint hipotézis szükséges), ami még mindig 2 szint alatt van a 101 legnehezebb sudokus I alatt találtam.
• Köszönöm az információt, én ‘ még mindig próbálom értelmezni ezt az egészet, szerencsére a webhelye elég alapos.
• @SimonStreicher Ennek lényege az, hogy csökkentse a keresési teret az egyes értékek aktiválásától a könnyen felismerhető mintákig (párokig), amelyeket bináris döntések generálásához használnak, a lehetőségeket. Például.a cell1 2 lehetséges v1 és v2 értéket tesz lehetővé, a cell2 ugyanazokat a lehetséges értékeket teszi lehetővé, de emellett egy vagy több más lehetőséget v3, v4, v5. Ezért az 1. és a 2. cella vagy egy pár (mindkettő tartalmaz v1 és v2), vagy a 2. cella csak a v3, v4, v5 egyik lehet. Ezt a hipotézist ezután ellenőrizzük.

Erre a rejtvényre, miközben egyetlen és egyetlen megoldása van, egyetlen ismert minta sem működik rajta, csak egy kissé intelligensebb tippelés és ellenőrzés. Az a lépésszám, amelyet az embernek előre kell tekintenie annak érdekében, hogy csökkentse a távoli nyomokat, itt mérőszám, és ennek a rejtvénynek kilenc egymást követő találgatásra van szüksége a megoldható állapot eléréséhez.

A SudokuWiki megoldója nem tudja megszerezni, mert egyszerűen túl sokáig tartana a Javascriptben, és nincs programozva számok kitalálása.

A megoldás megköveteli, hogy az egyik felvegye a négyzetek értékét, majd csökkentse a rejtvényt, hogy lássa, szükség van-e további feltételezésekre – ha mégis, készítsen még egyet, és folytassa. Lényegében a lehetséges megoldások mélységbeli keresése. A (z) sudoku-solutions megoldója megoldást talál erre a rejtvényre, de amikor felkérik a lépések megadására, kijelenti:

Ez a megoldó nem tudta teljesen megoldani a rejtvényt logikával, ez nem azt jelenti, hogy nincs logikai megoldás.

, majd azonnal nem sorolja fel a megoldás megoldásához használt lépések bármelyikét . Ez csak akkor fordul elő, ha a megoldónak nyers erővel történő elágazó találgatásokat kell használnia a megoldás megtalálásához.

Ennek eredményeként én magam semmiképpen sem tudnám ésszerűen megadni a “hogyan oldjam meg ezt a rejtvényt” választ, mivel ez magában foglalja ezen speciális láncok megkeresését és annak megmagyarázását, hogy miért nem működik a másik nagy mennyiségű lánc.

De ezt így csinálod: tegyük fel, hogy egy négyzet szám, majd egy másik, majd egy másik, és addig ellenőrizze, amíg eljut egy olyan sorrendhez, amelynek még van értelme és amely lehetővé teszi a rejtvény megoldását, vagy ellentmondásba kerül, és biztonsági másolatot kell készítenie, és újra kell próbálnia. Attól tartok, hogy szerintem ez a legjobb válasz erre a kérdésre.

Mivel megoldást kértél a rejtvényre, mégis meg tudom adni (egérrel a spoiler blokkot):

Megjegyzések

• Régi jó rekurzió.
• Legfeljebb 2 találgatás rekurziós mélységével sikerült megoldanom. A meztelen egyedülállók ” stratégia összesen 61812-szer futott (némi magasabb szintű gyorsítótárazás nélkül, anélkül, hogy a futások száma millióban lenne), ” Rejtett Singles ” stratégia 32892 alkalommal (plusz egy másik 28920, amelyet gyorsítótárból szolgáltak ki), és csak egy mélységű keresést futtattak 256 és még 15-ször szolgáltak gyorsítótárból (minden ponton csak egy tippet hajtottak végre, bár úgy gondolom, hogy a legtöbb ilyen futás a következőn belül történt meg), és a kétszintes keresés (ahol ‘ 2 tippet tesz) csak egyszer futott és kapta meg.
• (ez is az egyetlen rejtvény, amely nem sikerült ‘ csak egy szintű találgatással repedezzek a programommal)

Töltse le a szingapúri miniszterelnök Sudoku-megoldóját , és töltse be ezt a rejtvényt (CSAK ha valóban elakad). Akár hiszed, akár nem, az a miniszterelnök elég robusztus programot készített, és bár úgy tűnik, hogy egy ideig ott akad, végül a következő megoldással áll elő:

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

Nyilvánvalóan logikailag is megoldható, a srác szerint, aki kitalálta ezt a rejtvényt. A megoldóknak csak 24 óra kellett hozzá.

Megjegyzés: Ennek a rejtvénynek az 1. pontja a 7. sorban más helyzetben van, mint a kérdés. Ennek a rejtvénynek több megoldása van.

Megjegyzések

• Kétlem, hogy ennek az eredeti rejtvénynek több megoldása lenne (ha erre utal). A PM ‘ megoldó valószínűleg hibás: a 3. sor 7. oszlopa bemenetként ” 1 “, nem ” 7 ” (az egyik megfigyelés). Az exe helyes bemenetét figyelembe véve kiadja az ismert megoldást.
• @SimonStreicher a rossz bemenet a 7. sor 3. oszlopában található, ahol a 7-nek 1-nek kell lennie.
• 5 másodpercnél hosszabb időre elakad? Nagyon egyszerű megoldómnak sikerül ezt megközelítőleg bevinni időt.

Csak egy másik számítógépes megoldás hozzáadásához, majd a MiniZinc modellezési nyelv írhatja a következő programot:

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

A megfelelő adatokkal együtt fájl:

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

És az alapértelmezett megoldó használata meglehetősen szokásos laptopon, a megoldás 100 ms alatt jelenik meg, ami jelentősen megveri a PM Lee C ++ megvalósítását margó.

Megjegyzések

• Ez az algoritmus lineáris programozáson alapul?
• Ez ‘ s ugyanabban a tartományban – a megoldó egy kényszer programozó megoldó, ami jól működik, mivel a probléma nem igazán lineáris, de egy csomó korlátozás. a heurisztika kombinációja a lehetséges megoldások terének csökkentése érdekében néhány meglehetősen alapvető keresési módszerrel.
• Lenyűgözött. id = “8d567e9d73”>