The Dancing Links Algorithm - wyjaśnienie, które jest mniej wyjaśniające, ale bardziej na temat implementacji?

Question

Pracowałem nad Solugem Sudoku, mój obecny solver używa algorytmu cofania, ale nadal trwa to zbyt długo.

Mam nadzieję, że w większości przypadków uda się zmniejszyć tę liczbę do mniej niż sekundy. W związku z tym postanowiłem przerobić go na algorytm tańczących linków, rozumiejąc, że jest to jedna z lepszych metod bruteforce, która sprawdza się szczególnie w przypadku problemów z ograniczeniami, takich jak Sudoku Puzzle.

Próbowałem przeczytać na Wiki i Knuth's paper na tym, jednak oba są nieco trudne do zrozumienia i bardzo szczegółowe.

Przeczytałem także wersję Sudopedii i wydaje się, że kiedy dotarło to do implementacji Sudoku, stało się zbyt abstrakcyjne.

Czy ktoś może próbować wyjaśnić algorytm tańczących linków nie pod względem wyprowadzenia, ale jego implementacji? (byłoby świetnie wykorzystać Sudoku jako przykład)

Dzięki!

Answer 1

Możesz być zainteresowany my implementation in javascript.

---

Po pierwsze musisz zrozumieć Dokładną osłonę. Dokładny problem z okładką to problem polegający na tym, że dostajesz kilka wyborów, a zestaw ograniczeń i twoje wyzwanie polega na wybraniu kilku opcji, które wypełnią każde ograniczenie dokładnie raz.

Weźmy na przykład przypadek kogoś, kto tworzy swój rutynowy taniec taneczny. Mają wiele sztuczek, które muszą pokazać sędziom i nie chcą wykonywać żadnej sztuczki więcej niż raz. Mają wiele sekwencji, które są grupami sztuczek, które można połączyć, i które chcą wybrać idealny wybór sekwencji, aby zakryć wszystkie triki raz. W tym przykładzie ograniczenia polegają na tym, że muszą wykonać każdą lewę. Wybory są możliwymi sekwencjami, które mogą włączyć do swojej rutyny.

Dobrym sposobem na reprezentowanie problemów tego rodzaju jest narysowanie tabeli, w której wiązania są kolumnami, a wybory są rzędami, a w komórce znajduje się duże X, w którym określony wybór spełnia to ograniczenie.

Okazuje się, że przy odpowiednich ograniczeniach i wyborach sudoku można opisać jako problem z dokładną osłoną.

---

Ok, zakładając, że masz, teraz trzeba zrozumieć X. Algorytm Knuth powiedział o nim „Algorytm X to po prostu stwierdzenie oczywistej metody prób i błędów. (Faktycznie, mogę myśleć o jakimkolwiek innym rozsądnym sposobie wykonywania tej pracy, ogólnie.) ". Oto mój opis algorytmu X:

1. Jeśli Twoja tabela nie ma kolumn, zatrzymaj się - rozwiązałeś. Jeśli masz zapisane częściowe rozwiązanie, to w rzeczywistości jest to prawdziwe rozwiązanie, zwróć je.
2. Wybierz kolumnę (reprezentującą ograniczenie).
3. Znajdź wiersz z krzyżem w tej kolumnie (oznaczający wybór, który spełnia to ograniczenie). Dodaj go do jakiejś struktury, w której przechowujesz potencjalne rozwiązania. Jeśli nie możesz znaleźć wiersza, poddaj się - nie ma rozwiązań.
4. Załóżmy, że wiersz znaleziony w 3 znajduje się w rozwiązaniu, więc usuń wszystkie kolumny, które mają X w tym wierszu.Usuwając wszystkie te kolumny, usuń również wszystkie wiersze, które mają X w kolumnach, które usuwasz (ponieważ już spełniłeś ograniczenie, więc nie masz możliwości wyboru czegoś, co by je usatysfakcjonowało).
5. Teraz rekursywnie próbuj rozwiązać zredukowany stół. Jeśli nie możesz, usuń wybrany rząd z potencjalnej struktury rozwiązania, przywróć wszystkie wiersze i kolumny usunięte w krokach 3 i 4 i wypróbuj inny wiersz. Jeśli zabraknie Ci wierszy, poddaj się - nie ma rozwiązań.

---

Teraz, że rozumie, że można zrozumieć łączy taniec. Dancing Links to sposób na sprawne wdrożenie tego algorytmu. Kluczowym punktem tańczących linków jest to, że na połączonej liście, po usunięciu węzła (który można wykonać skutecznie, modyfikując wskaźniki sąsiadów), usunięty węzeł ma wszystkie informacje potrzebne do jego ponownego dodania do połączonej listy (w przypadku, gdy okaże się, że myliłeś się, gdy zgadłeś, że to część rozwiązania). To plus fakt, że jeśli utworzysz wszystkie powiązane listy, a potem nagle stracisz wiele specjalnych przypadków, to prawie wszystkie tańczące linki są.

Answer 2

Choć kwestia ta jest bardzo stara, pomyślałem, że dodam:

Ta strona sprawia, że ​​algorytm bardzo łatwy do zrozumienia: Zendoku writeup. Dopóki nie przeczytałem o tym przy tym łączu, pomyślałem, że to musi być super zaawansowany algorytm, ale tak naprawdę, kiedy można go sobie wyobrazić, jest to po prostu genialne, ale proste rozwiązanie.

Również my implementation w języku C# powinno być dość łatwe do odczytania ... byłoby pomocne podzielenie różnych klas na różne pliki, które na pewno.
Jest to w dużej mierze bezpośrednia implementacja z pdf Knutha, ale z kilku zorientowane obiektowo optymalizacje (właściwie od Zrobiłem to kilka miesięcy temu nie bardzo pamiętam, ile ja skorzystałam z pdf)