Jak rozwiązać najtrudniejsze sudoku na świecie '?

Odgadywanie pojedynczych wartości podczas wyszukiwania w głąb nie jest optymalny.

Oto łańcuch rozumowania oparty na hipotezie wszerz / metodzie obalenia (którą mój pasierb niechętnie nazywa „wyuczonym zgadywaniem”).

Samo śledzenie łańcucha obejmującego sprzeczności wymaga do rozwiązania 23 wariantów sudoku, więc najlepiej jest używać go z solwerem wspomaganym komputerowo. Jednak nie wymaga on żadnych wyszukanych algorytmów, aby go śledzić. (używam własnego, niezoptymalizowanego programu w Pythonie zaangażowana moc).

Notacja jest zgodna z konwencjami arkusza kalkulacyjnego (kolumna = litera, rząd = liczba) (lub szachy, jeśli wolisz).

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 

W World „s Hardest Sudoku zamieściłem zrzuty ekranu z krokami i krótkie wyjaśnienie metody. Ponieważ interesuje mnie tylko rozwiązywanie trudnych łamigłówek przez „wyuczone zgadywanie”, stwierdziłem, że to sudoku nie jest tak trudne, jak w reklamie (1 poziom hipotezy + 1 spojrzenie w przód = 2 poziomy hipotez). W rzeczywistości nie znalazłem jeszcze sudoku, które wymagałoby więcej niż 2 poziomy hipotez + jedno spojrzenie w przód (= 3 poziomy hipotez).

Komentarze

• Jak dobrze Twój solver radzi sobie z sudoku ' z 17 wpisami? Na przykład. theconversation.com/…
• @SimonStreicher Sudoku z 17 wskazówkami, cytujesz jest trudny, ale nie należy do najtrudniejszych sudoku w kontekście mojego algorytmu. Ogólnie rzecz biorąc, nie ma korelacji między liczbą wskazówek a twardością sudoku. Opublikowałem statystyki dotyczące sudoku, które przeanalizowałem.
• @SimonStreicher Mam przeanalizował listę 95 najpopularniejszych sudoku (mianowicie 95 trudnych łamigłówek ). Jest 5 suduk z poziomem trudnym (potrzebne są 2 poziomy hipotez), czyli nadal o 2 poziomy poniżej 101 najtrudniejszych sudoku I znalazłem.
• Dziękuję za informacje, ' wciąż próbuję zrozumieć to wszystko, na szczęście Twoja witryna jest dość dokładna.
• @SimonStreicher Rdzeniem tego jest redukcja przestrzeni wyszukiwania z aktywacji pojedynczych wartości do łatwo rozpoznawalnych wzorców (par), które są używane do generowania decyzji binarnych ze zwiększoną eliminacją możliwości. Na przykład.cell1 pozwala na 2 możliwe wartości v1 i v2, cell2 pozwala na te same możliwe wartości, ale dodatkowo jedną lub więcej innych możliwości v3, v4, v5. Dlatego komórka 1 i komórka 2 są parą (obie zawierają v1 i v2) lub komórka 2 może być tylko jedną z wersji v3, v4, v5. Ta hipoteza jest następnie sprawdzana.

W przypadku tej łamigłówki, która ma jedno i tylko jedno rozwiązanie, nie działają na to żadne znane wzorce, poza nieco bardziej inteligentnym zgadywaniem i sprawdzaniem. Liczba kroków, na które trzeba patrzeć w przyszłość, aby zredukować wskazówki, jest tutaj miarą, a ta łamigłówka wymaga dziewięciu kolejnych zgadnięć, aby osiągnąć stan możliwy do rozwiązania.

Solver w SudokuWiki nie może go pobrać, ponieważ wykonanie go w Javascript zajmie zbyt dużo czasu i nie jest zaprogramowany do odgadywania liczb.

Rozwiązanie wymaga, aby przyjąć wartości kwadratów, a następnie zredukować układankę, aby zobaczyć, czy potrzebujesz więcej założeń – jeśli tak, zrób kolejne i kontynuuj. W istocie jest to najpierw wgłębne poszukiwanie możliwych rozwiązań. Rozwiązujący w rozwiązaniach sudoku znajduje rozwiązanie tej zagadki, ale gdy zostanie poproszony o podanie kroków, deklaruje:

Ten solver nie może całkowicie rozwiązać zagadki logicznie, nie oznacza to, że nie ma logicznego rozwiązania.

, a następnie natychmiast nie podaje żadnych kroków, które wykorzystał do rozwiązania tego problemu. Dzieje się tak tylko wtedy, gdy solver musi użyć odgadywania rozgałęzień metodą brute-force, aby znaleźć rozwiązanie.

W rezultacie nie ma możliwości, abym sam mógł w rozsądny sposób udzielić odpowiedzi „jak rozwiązać tę zagadkę”, ponieważ robiąc wymagałoby więc znalezienia tych konkretnych łańcuchów i wyjaśnienia, dlaczego inna ogromna liczba łańcuchów nie działa.

Ale tak to się robi: załóżmy, że kwadrat to liczba, potem inna, potem kolejna, i sprawdzaj dalej, aż dojdziesz do sekwencji, która nadal ma sens i pozwala na rozwiązanie łamigłówki, albo doszedłeś do sprzeczności i musisz się cofnąć i spróbować ponownie. Obawiam się, że to najlepsza odpowiedź, jaką możesz uzyskać na to pytanie.

Ponieważ poprosiłeś o rozwiązanie zagadki, mogę je jednak udzielić (najedź myszką na blok spoilera):

Komentarze

• Stara dobra rekurencja.
• Udało mi się ją rozwiązać z głębokością rekursji maksymalnie 2 domysłów. ” Strategia nagich singli ” została uruchomiona łącznie 61812 razy (po pewnym buforowaniu na wyższym poziomie, bez tego, że liczba uruchomień jest w milionach), ” Ukryte single ” strategia 32892 razy (plus kolejne 28920, które zostały udostępnione z pamięci podręcznej) i przeprowadzono wyszukiwanie z głębokością tylko 1 256 razy i obsługiwane z pamięci podręcznej kolejne 15 razy (w każdym momencie dokonano tylko jednego przypuszczenia, chociaż sądzę, że większość tych uruchomień faktycznie miała miejsce w następnym), a wyszukiwanie dwupoziomowe (gdzie ' d zrobiłeś 2 przypuszczenia) zostało uruchomione tylko raz i zostało wykonane.
• (także jest to jedyna łamigłówka, która nie ' t złamać mój program tylko na JEDNYM poziomie zgadywania)

Pobierz premiera singapurskiego rozwiązania Sudoku i podaj tę zagadkę (TYLKO jeśli NAPRAWDĘ utkniesz). Wierz lub nie, ale ten premier stworzył całkiem solidny program i chociaż wygląda na to, że utknął na chwilę, w końcu wychodzi z następującym rozwiązaniem:

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

Jednak według gościa, który wynalazł tę zagadkę, najwyraźniej można to rozwiązać za pomocą logiki. Zajęło to rozwiązującym tylko 24 godziny.

Uwaga: ta łamigłówka ma 1 w siódmym wierszu na innej pozycji niż pytanie. Ta łamigłówka ma wiele rozwiązań.

Komentarze

• Wątpię, by ta oryginalna łamigłówka miała wiele rozwiązań (jeśli to jest sugerowane). Twój wkład w PM ' jest prawdopodobnie nieprawidłowy: wiersz 3, kolumna 7 jest podana jako dane wejściowe jako ” 1 „, nie ” 7 ” (jedna z obserwacji). Podając poprawne dane wejściowe do exe, wyprowadza znane rozwiązanie.
• @SimonStreicher błędne dane wejściowe znajdują się w wierszu 7 w kolumnie 3, gdzie 7 powinno być 1
• Czy blokuje się na więcej niż 5 sekund? Mój bardzo prosty solver radzi sobie z tym Ilość czasu.

Wystarczy dodać kolejne rozwiązanie komputerowe, a następnie użyć język modelowania MiniZinc możesz napisać następujący 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 ]; 

Wraz z odpowiednimi danymi 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 używając domyślnego solwera na dość standardowym laptopie, rozwiązanie wychodzi w 100 ms, co znacznie przewyższa implementację C ++ autorstwa PM Lee znacznie margines.

Komentarze

• Czy ten algorytm jest oparty na programowaniu liniowym?
• It ' s w tej samej dziedzinie – solwerem jest program do rozwiązywania ograniczeń, który działa dobrze, ponieważ problem nie jest ' t naprawdę liniowy, ale jest to zestaw ograniczeń. kombinacja heurystyk w celu zmniejszenia przestrzeni możliwych rozwiązań z kilkoma dość podstawowymi metodami wyszukiwania.
• Jestem pod wrażeniem '. Mój podręcznik jest bardzo prosty lver w Kotlin pokonuje go w około 5 sekund na moim laptopie, używając maksymalnej głębokości wyszukiwania 2.