Znaleziono zwycięzcę
Wygląda na to, że mamy zwycięzcę! O ile nikt nie planuje rywalizować z najszybszym na świecie solwerem Sudoku, użytkownik 53x15 wygrywa niesamowicie szybkim solwerem Tdoku. Dla każdego, kto nadal pracuje nad swoimi rozwiązaniami, będę nadal testować nowe zgłoszenia, gdy będę miał czas.
Wyzwanie
Celem gry Sudoku jest wypełnienie planszy cyframi 1-9, po jednej w każdej komórce, w taki sposób, aby każdy wiersz, kolumna i pudełko zawierały tylko jedną liczbę. Bardzo ważnym aspektem układanki Sudoku jest to, że powinno być tylko jedno prawidłowe rozwiązanie.
Cel tego wyzwania jest prosty, powinieneś jak najszybciej rozwiązać zestaw sudoku. Jednak nie będziesz tylko rozwiązywał żadnego starego Sudoku, rozwiążesz najtrudniejsze istniejące sudoku, Sudokus z 17 wskazówkami. Oto przykład:
Zasady
Język
Możesz swobodnie używać dowolnego języka. Jeśli nie mam zainstalowanego kompilatora dla twojego języka, powinieneś być w stanie dostarczyć zestaw instrukcji wiersza poleceń potrzebnych do zainstalowania środowiska, w którym twój skrypt może być uruchamiany w systemie Linux .
Maszyna wzorcowa
Test będzie działał na Dell XPS 9560, Intel Core i7-7700HQ 2,8 GHz (zwiększenie 3,8 GHz) 4 rdzenie, 8 wątków, 16 GB pamięci RAM. GTX 1050 4 GB. Na komputerze działa Ubuntu 19.04. Oto uname
wynik dla wszystkich zainteresowanych.
Linux 5.0.0-25-generic #26-Ubuntu SMP Thu Aug 1 12:04:58 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
Wejście
Dane wejściowe zostaną podane w postaci pliku. Można go znaleźć tutaj . Plik zawiera 49151 łamigłówek Sudoku. Pierwszy wiersz pliku to liczba puzzli, a każda kolejna linia ma 81 znaków i reprezentuje układankę. Nieznane są komórki 0
, a znane są komórki 1-9
.
Twój program powinien móc traktować nazwę pliku jako argument lub mieć plik wejściowy ze STDIN , aby ułatwić ręczne sprawdzenie rozwiązania. Dołącz instrukcję dotyczącą sposobu, w jaki Twój program pobiera dane wejściowe.
Czas / punktacja
Z dyskusji w komentarzach i refleksji zmieniono kryteria punktacji na czas całego programu. Twój program powinien wygenerować plik wyjściowy z poprawnym skrótem, nawet podczas oficjalnej oceny. Nie koliduje to z żadnym istniejącym rozwiązaniem i nie zmienia obecnych rankingów. Doceniamy wszelkie przemyślenia na temat systemu punktacji.
Jeśli dwa rozwiązania mają podobne wyniki dla poszczególnych serii, przeprowadzę wiele testów porównawczych, a średni czas będzie końcowym wynikiem. Jeśli średnie wyniki różnią się o mniej niż 2%, uznam to za remis.
Jeśli twoje rozwiązanie potrwa dłużej niż godzinę, nie zostanie oficjalnie ocenione. W takich przypadkach użytkownik jest odpowiedzialny za zgłoszenie maszyny, na której działa, oraz wyniku. W przypadku zoptymalizowanego rozwiązania nie powinno to stanowić problemu.
EDYCJA : Zwrócono mi uwagę, że choć trudny, postawiony problem nie jest najtrudniejszy. Jeśli będzie dostępny czas, postaram się porównać przedstawione tu rozwiązania z trudniejszym zestawem puzzli i dodać wynik do każdego zgłoszenia. Nie będzie to jednak oficjalna punktacja i jest po prostu dla zabawy.
Weryfikacja
Twoje rozwiązanie zostanie zweryfikowane za pomocą sumy kontrolnej MD5 / SHA256. Twój skrypt powinien być w stanie wygenerować plik zawierający wszystkie łamigłówki i ich rozwiązania. Jednak plik zostanie również ręcznie sprawdzony, więc nie próbuj uzyskać kolizji skrótu. Twój plik wyjściowy powinien pasować:
MD5: 41704fd7d8fd0723a45ffbb2dbbfa488
SHA256:0bc8dda364db7b99f389b42383e37b411d9fa022204d124cb3c8959eba252f05
Plik będzie miał format:
<num_puzzles>
<unsolved_puzzle#1>,<solved_puzzle#1>
<unsolved_puzzle#2>,<solved_puzzle#2>
...
<unsolved_puzzle#n>,<solved_puzzle#n>
z jednym końcowym znakiem nowej linii.
Co jest niedozwolone
W żaden sposób nie możesz wprowadzać rozwiązań na sztywno . Twój algorytm powinien mieć zastosowanie do dowolnego zestawu łamigłówek Sudoku, zarówno łatwych, jak i trudniejszych Sudokus. Jednak jest całkowicie w porządku, jeśli twoje rozwiązanie jest wolne dla łatwiejszych łamigłówek.
Nie możesz mieć programu niedeterministycznego . Możesz używać generatora liczb losowych, ale jego generator powinien zostać naprawiony. Ta zasada ma zapewnić, że pomiary są bardziej precyzyjne i mają mniejszą wariancję. (Podziękowania dla Petera Taylora za wskazówkę)
Podczas wykonywania programu nie wolno używać żadnych zasobów zewnętrznych ani żądań internetowych. Wszystko powinno być samodzielne. Nie dotyczy to zainstalowanych bibliotek i pakietów, które są dozwolone.
Inne informacje
Jeśli chcesz inny zestaw testowy, aby sprawdzić twoje rozwiązanie, oto 10000 łatwiejszych Sudokusów . Oto ich rozwiązania .
MD5: 3cb465ef6077c4fcab5bd6ae3bc50d62
SHA256:0bc8dda364db7b99f389b42383e37b411d9fa022204d124cb3c8959eba252f05
Jeśli masz jakieś pytania, możesz je zadać, a ja postaram się wyjaśnić wszelkie nieporozumienia.
Odpowiedzi:
C ++ - oficjalny wynik 0.201
Użycie Tdoku ( kod ; projekt ; testy porównawcze ) daje następujące wyniki:
Tdoku zostało zoptymalizowane pod kątem trudnych instancji Sudoku. Pamiętaj jednak, w przeciwieństwie do stwierdzenia problemu, że 17 łamigłówek jest dalekie od najtrudniejszego Sudoku. W rzeczywistości należą one do najłatwiejszych, przy czym większość nie wymaga w ogóle cofania się. Zobacz niektóre inne zestawy danych porównawczych w projekcie Tdoku, aby dowiedzieć się, które łamigłówki są naprawdę trudne.
Zauważ też, że chociaż Tdoku jest najszybszym solwerem, jaki znam dla trudnych zagadek, nie jest najszybszy dla 17 zagadek. Dla nich myślę, że najszybszy jest ten rdzawy projekt , pochodna JCZSolve, która została zoptymalizowana pod kątem 17 zagadek podczas opracowywania. W zależności od platformy może być 5-25% szybsza niż Tdoku dla tych zagadek.
źródło
Node.js ,
8.231s6.735s oficjalny wynikTraktuje nazwę pliku jako argument. Plik wejściowy może już zawierać rozwiązania w formacie opisanym w wyzwaniu, w którym to przypadku program porówna je z własnymi rozwiązaniami.
Wyniki są zapisywane w pliku „sudoku.log” .
Kod
Przykładowe dane wyjściowe
Testowany na Intel Core i7 7500U @ 2,70 GHz.
źródło
Python 3 (z dlx ) 4min 46.870s oficjalny wynik
(tutaj pojedynczy rdzeń i7-3610QM)
Oczywiście do pokonania za pomocą skompilowanego języka takiego jak C i korzystania z wątków, ale to początek ...
sudoku
to moduł, który umieściłem na githubie (skopiowanym w stopce tego postu), który używadlx
pod maską.Stosowanie
sudoku.py
gdzieś na swojej ścieżce (z linku git hub lub skopiuj go od dołu)testSolver.py
gdzieś na swojej ścieżceW razie potrzeby przesłać dane wyjściowe do pliku zgodnie ze specyfikacją wyzwania do pliku:
sudoku.py (tak, są tutaj dodatkowe funkcje oprócz rozwiązywania)
źródło
Python 3 + Z3 - 10min 45.657 oficjalny wynik
około tysiąca na moim laptopie.
Zainstaluj zależność
Biegać
Nie jestem pewien, jak poprawić jego wydajność, ponieważ właśnie rozwiązał magicznie ...
źródło
C - oficjalny wynik
2.228s1.690sna podstawie @ Arnauld's
skompiluj i uruchom:
źródło
C - 12 min. Oficjalny wynik 28.374s
działa na około
30m15m na moim i5-7200U i generuje poprawny skrót md5skompiluj (najlepiej z clang v6) i uruchom:
źródło
memcpy
tam dwóch i trwa pewna rekurencja. Spróbuję to dzisiaj zweryfikować.Java - oficjalny wynik 4.056s
Główną ideą tego jest, aby nigdy nie przydzielać pamięci, gdy nie jest ona potrzebna. Jedynym wyjątkiem są operacje podstawowe, które i tak powinny zostać zoptymalizowane przez kompilator. Cała reszta jest przechowywana jako maski i tablice operacji wykonanych na każdym kroku, które można cofnąć po zakończeniu kroku rekurencji.
Około połowa wszystkich sudokusów jest rozwiązana całkowicie bez cofania się, ale jeśli zwiększę tę liczbę, ogólny czas wydaje się być wolniejszy. Planuję om przepisać to w C ++ i zoptymalizować jeszcze bardziej, ale ten solver staje się gigantem.
Chciałem wdrożyć jak najwięcej buforowania, co może prowadzić do pewnych problemów. Na przykład, jeśli w tym samym rzędzie znajdują się dwie komórki, które mogą mieć tylko liczbę 6, osiągnęliśmy niemożliwy przypadek i powinniśmy powrócić do śledzenia wstecznego. Ale ponieważ obliczyłem wszystkie opcje za jednym razem, a następnie umieściłem liczby w komórkach z tylko jedną możliwością, nie sprawdziłem dwukrotnie, czy przedtem umieściłem liczbę w tym samym rzędzie. To prowadzi do niemożliwych rozwiązań.
Ponieważ wszystko jest zawarte w tablicach zdefiniowanych u góry, użycie pamięci przez solver wynosi około 216 kB. Główna część wykorzystania pamięci pochodzi z tablicy zawierającej wszystkie łamigłówki i modułów obsługi We / Wy w Javie.
EDYCJA : Mam wersję, która jest teraz przetłumaczona na C ++, ale nie jest znacznie szybsza. Oficjalny czas wynosi około 3,5 sekundy, co nie jest wielką poprawą. Myślę, że głównym problemem z moją implementacją jest to, że trzymam maski jako tablice, a nie maski bitowe. Spróbuję przeanalizować rozwiązanie Arnauld, aby zobaczyć, co można zrobić, aby to poprawić.
źródło
C ++ z Minisatem (2.2.1-5) - oficjalny wynik 11,735 s
Nie jest to tak szybkie jak wyspecjalizowany algorytm, ale jest to inne podejście, interesujący punkt odniesienia i łatwy do zrozumienia.
$ clang ++ -o rozwiązać -lminisat solver_minisat.cc
źródło