Wielowątkowy algorytm rozwiązywania sudoku?

Wielowątkowość jest przydatna w każdej sytuacji, w której pojedynczy wątek musi czekać na zasób, a w międzyczasie można uruchomić inny wątek. Obejmuje to wątek oczekujący na żądanie wejścia / wyjścia lub dostęp do bazy danych, podczas gdy inny wątek kontynuuje pracę procesora.

Wielowątkowość jest również przydatna Jeśli poszczególne wątki mogą być tworzone na różne procesory (lub rdzenie), ponieważ wtedy działają naprawdę jednocześnie, chociaż zazwyczaj będą musiały udostępniać dane, więc nadal będą spór.

Nie widzę powodu, dla którego wielowątkowy Rozwiązywacz Sudoku byłby bardziej wydajny niż jednowątkowy, po prostu dlatego, że nie ma czekania na zasoby. Wszystko zostanie zrobione w pamięci.

Ale pamiętam niektóre zadania domowe, które zrobiłem na Uni ,i to było podobnie bezużyteczne (Kod Fortran, aby zobaczyć, jak głęboki tunel dostał się, gdy kopałeś w 30 stopni na jedną milę, a następnie 15 stopni na kolejną milę-tak, jestem dość stary : -). Chodzi o to, aby pokazać, że możesz to zrobić, a nie że jest przydatna.

Do algorytmu.

Napisałem pojedynczy gwintowany solver, który w zasadzie uruchomił szereg zasad w każdym przejściu, aby spróbować wypełnić inny kwadrat. Przykładowa zasada brzmiała: jeśli rząd 1 ma tylko jeden kwadrat wolny, liczba jest widoczna ze wszystkich innych liczb w rzędzie 1.

Istniały podobne reguły dla wszystkich wierszy, wszystkich kolumn, wszystkich mini-siatek 3x3. Istniały również reguły sprawdzające przecinanie wierszy/kolumn (np. czy dany kwadrat może zawierać tylko 3 lub 4 ze względu na rząd i 4 lub 7 ze względu na kolumnę, wtedy było 4). Były bardziej złożone zasady, których Nie będę tutaj wyszczególniać, ale są w zasadzie takie same, jak rozwiązujesz je ręcznie.

Podejrzewam, że masz podobne zasady w swojej implementacji (ponieważ poza brute force, nie mogę wymyślić innego sposobu, aby go rozwiązać, a jeśli użyłeś brute force, nie ma dla Ciebie nadziei :-).

Sugerowałbym przydzielenie każdej reguły do wątku i udostępnienie im siatki. Każdy wątek zrobiłby własną regułę i tylko ta zasada.

Update:

Jon, na podstawie Twojej edycji:

[edytuj] zapomniałem wspomnieć, że liczba wątków do wykorzystania jest określona jako argument programu, więc o ile wiem, nie jest ona w żaden sposób związana ze stanem układanki...

Ponadto może nie istnieć unikalne rozwiązanie - poprawnym wejściem może być całkowicie pusta tablica. Muszę zgłosić min (1000, ilość rozwiązań) i wyświetlić jeden z nich (jeśli to exists)

Wygląda na to, że twój nauczyciel nie chce, abyś dzielił się na podstawie reguł, ale zamiast tego na widelce (gdzie może obowiązywać wiele reguł).

Mam przez to na myśli, że w każdym momencie rozwiązania, jeśli są dwa lub więcej możliwych posunięć do przodu, powinieneś przydzielić każdą możliwość do osobnego wątku(nadal używaj swoich reguł dla wydajności, ale jednocześnie sprawdzaj każdą możliwość). To daje lepszą współbieżność (zakładając, że wątki mogą być uruchamiane na oddzielnych Procesory/rdzenie), ponieważ nie będzie sporu o płytę; każdy wątek otrzyma własną kopię.

Ponadto, ponieważ ograniczasz liczbę wątków, będziesz musiał użyć magii puli wątków, aby to osiągnąć.

Proponuję mieć kolejkę roboczą i N wątków. Kolejka robocza jest początkowo pusta, gdy główny wątek uruchomi wszystkie wątki robocze. Następnie główny wątek umieszcza stan początkowy w kolejce roboczej.

Wątki robocze po prostu poczekaj, aż stan zostanie umieszczony w kolejce roboczej, a jeden z nich chwyta go do przetworzenia. Wątek roboczy to Twój jednowątkowy solver z jedną małą modyfikacją: gdy są X możliwości do przodu (X > 1), twój worker umieszcza x-1 z nich z powrotem do kolejki roboczej, a następnie kontynuuje przetwarzanie drugiej możliwości.

Powiedzmy, że jest tylko jedno rozwiązanie (prawdziwe Sudoku: -). Pierwszy wątek roboczy zniknie z rozwiązania bez znalezienia żadnych widelców i będzie dokładnie tak jak w Twojej obecnej sytuacji.

Ale z dwoma możliwościami w move 27 (powiedzmy, 3 lub 4 mogą przejść do lewej górnej komórki), Twój wątek utworzy kolejną planszę z pierwszą możliwością (umieść 3 w tej komórce) i umieść ją w kolejce pracy. Następnie umieścił 4 we własnej kopii i kontynuował.

Kolejny wątek podniesie planszę z 3 w tej komórce i będzie kontynuował. W ten sposób masz dwa wątki działające jednocześnie obsługujące dwie możliwości.

Gdy jakiekolwiek thread decyduje, że jego deska jest nierozpuszczalna, wyrzuca ją i wraca do kolejki pracy po więcej pracy.

Gdy dowolny wątek zdecyduje, że jego plansza jest rozwiązana, powiadamia główny wątek, który może ją przechowywać, nadpisując poprzednie rozwiązanie (pierwsze znalezione To rozwiązanie) lub wyrzucając je, jeśli ma już rozwiązanie (Ostatnie znalezione To rozwiązanie), wtedy wątek roboczy wraca do kolejki zadań po więcej pracy. W obu przypadkach główny wątek powinien zwiększyć liczbę rozwiązań znaleziono.

Gdy wszystkie wątki są bezczynne, a kolejka robocza jest pusta, main albo będzie miał rozwiązanie, albo nie. Będzie również miał liczbę rozwiązań.

Pamiętaj, że cała komunikacja między pracownikami a głównym wątkiem będzie musiała być mutexed (zakładam, że wiesz to na podstawie informacji w twoim pytaniu).

Ideą multi-threading jest wykorzystanie kilku procesorów, co pozwala na wykonywanie kilku obliczeń jednocześnie. Oczywiście każdy wątek będzie potrzebował własnej pamięci, ale zazwyczaj nie stanowi to problemu.

Przede wszystkim, co chcesz zrobić, to podzielić możliwy stan rozwiązania na kilka podzakresów, które są tak niezależne, jak to możliwe (aby uniknąć marnowania zbyt wielu zasobów na tworzenie narzutu wątku), a jednak "dopasować" swój algorytm (aby faktycznie korzyści z posiadania wielu wątków).

Oto chciwy, jednowątkowy solver brute-force:

1. Wybierz następną pustą komórkę. Jeśli nie będzie pustych komórek, zwycięstwo!
2. możliwa wartość komórki = 1
3. sprawdzić nieprawidłowe rozwiązanie częściowe(duplikaty w wierszu, kolumnie lub bloku 3x3).
4. Jeśli rozwiązanie częściowe jest nieprawidłowe, należy zwiększyć wartość komórki i powrócić do kroku 3. W przeciwnym razie przejdź do kroku 1.

Jeśli spojrzeć na powyższy zarys, kombinacja kroków 2 i 3 są oczywistymi kandydatami do wielowątkowości. Bardziej ambitne rozwiązania obejmują tworzenie rekurencyjnej eksploracji, która generuje zadania, które są przesyłane do puli wątków.

Edytuj, aby odpowiedzieć na ten punkt: "nie rozumiem, jak możesz znaleźć różne rozwiązania tego samego problemu w tym samym czasie bez utrzymywania wielu kopii puzzli."

1. Zacznij od przykładu problem.
2. Znajdź pierwszą pustą komórkę.
3. Utwórz 9 wątków, gdzie każdy wątek ma własną kopię problemu z własnym indeksem jako wartością kandydata w pustej komórce.
4. w każdym wątku Uruchom swój oryginalny algorytm jednowątkowy na tym wątku-lokalna zmodyfikowana Kopia problemu.
5. Jeśli jeden z wątków znajdzie odpowiedź, zatrzymaj wszystkie pozostałe wątki.

Jak można sobie wyobrazić, każdy wątek ma teraz nieco mniejszą przestrzeń problemową i każdy wątek może działać na własnym rdzeniu procesora. Dzięki algorytmowi z jednym gwintem nie możesz czerpać korzyści z maszyny wielordzeniowej.

Czy trzeba korzystać z wielowątkowości, czy po prostu korzystać z wielowątkowości, aby móc uczyć się do zadania?

Jeśli używasz algorytmu brute force, łatwo jest podzielić go na wiele wątków i jeśli przypisanie koncentruje się na kodowaniu wątków, które mogą być akceptowalnym rozwiązaniem.

Kiedy mówisz wszystkie rozwiązania danej układanki, masz na myśli ostateczne i jedyne rozwiązanie do układanki? Albo różne sposoby dotarcia do jednego rozwiązania? Zdawałem sobie sprawę, że z definicji Sudoku może mieć tylko jedno rozwiązanie...

Dla tego pierwszego, albo podejście oparte na regułach Pax lub podejście Toma Leysa do wielowątkowości istniejącego algorytmu backtrackingu może być rozwiązaniem.

Jeśli to drugie, można zaimplementuj jakiś algorytm rozgałęzień, który uruchamia nowy wątek (z własną kopią układanki) dla każdego możliwego ruchu na każdym etapie układanki.

W zależności od tego, jak zakodowałeś solver z pojedynczym gwintem, możesz być w stanie ponownie użyć logiki. Możesz zakodować wielowątkowy solver, aby rozpocząć każdy wątek za pomocą innego zestawu strategii do rozwiązania zagadki.

Używając tych różnych strategii, Twój rozwiązywacz wielowątkowy może znaleźć całkowity zestaw rozwiązań w krótszym czasie niż rozwiązywacz jednowątkowy (pamiętaj jednak, że prawdziwa łamigłówka Sudoku ma tylko jedno rozwiązanie...nie tylko ty miałeś do czynienia z tym Bogiem. okropna gra w klasie)

Kilka ogólnych punktów: nie uruchamiam procesów równolegle, chyba że 1) łatwo jest podzielić problem 2) wiem, że skorzystam z tego - np. nie uderzę w kolejne wąskie gardło. Całkowicie unikam dzielenia się zmiennymi wartościami między wątkami-lub minimalizuję je. Niektórzy ludzie są wystarczająco inteligentni, aby bezpiecznie pracować z muteksami. Nie jestem.

Musisz znaleźć punkty w algorytmie, które tworzą naturalne gałęzie lub duże jednostki pracy. Po zidentyfikowaniu jednostki do pracy, upuszczasz ją w kolejce do wątek do poderwania. Jako trywialny przykład. 10 baz danych do aktualizacji. Rozpocznij aktualizację asynchroniczną na wszystkich 10 serwerach. Poczekaj, aż wszystko się skończy. Mogę łatwo uniknąć współdzielenia stanu między wątkami / procesami i mogę łatwo agregować wyniki.

Na myśl przychodzi sudoku, że skuteczne rozwiązanie suduko powinno łączyć 2-3 (lub więcej) strategie, które nigdy nie przekraczają pewnej głębokości. Kiedy robię Sudoku, jest oczywiste, że w danym momencie różne algorytmy dostarczają rozwiązania z najmniej pracy. Możesz po prostu odpalić kilka strategii, pozwolić im zbadać na ograniczoną głębokość, poczekać na raport. / Align = "left" / Pozwala to uniknąć "brutalnego wymuszania" rozwiązania. Każdy algorytm ma swoją własną przestrzeń danych, ale łączysz odpowiedzi.

Sciam.com miałem artykuł na ten temat rok lub dwa wstecz-wygląda na to, że nie jest publiczny, chociaż.

Powiedziałeś, że użyłeś śledzenia wstecznego, by rozwiązać problem. To, co możesz zrobić, to podzielić przestrzeń wyszukiwania na dwa i obsłużyć każdą przestrzeń do wątku, a następnie każdy wątek zrobi to samo, dopóki nie dotrzesz do ostatniego węzła. Zrobiłem rozwiązanie tego, które można znaleźć www2.cs.uregina.ca/ ~ hmer200a ale za pomocą pojedynczego wątku ale mechanizm dzielenia przestrzeni wyszukiwania jest tam za pomocą gałęzi i bound.

Kilka lat temu, kiedy patrzyłem na rozwiązywanie sudoku, wydawało się, że optymalne rozwiązanie wykorzystało kombinację algorytmów analizy logicznej i tylko wtedy, gdy było to konieczne, padło na brute force. Pozwoliło to rozwiązać rozwiązanie bardzo szybko, a także ranking planszy według trudności, jeśli chcesz go użyć do wygenerowania nowej układanki. Jeśli przyjęłbyś takie podejście, z pewnością mógłbyś wprowadzić współbieżność, chociaż posiadanie wątków rzeczywiście może być trudne.

Mam pomysł, który jest tu całkiem fajny.. zrób to z Modelem aktora! Powiedziałbym, że używając Erlanga.. Jak? Zaczynasz od oryginalnej planszy i..

• 1) Najpierw pusta komórka tworzy 9 dzieci o innej liczbie, potem popełnia samobójstwo
• 2) każde dziecko sprawdza, czy jest nieważne, jeśli tak, popełnia samobójstwo, w przeciwnym razie
  • jeśli jest pusta komórka, przejdź do 1)
  • jeśli jest kompletny, ten aktor jest rozwiązaniem

Najwyraźniej każdy żyjący aktor jest rozwiązaniem dla problem =)

Tak na marginesie. Właściwie zaimplementowałem zoptymalizowany solver sudoku i przyjrzałem się wielowątkowości, ale dwie rzeczy mnie powstrzymały.

Po pierwsze, prosty koszt uruchomienia wątku trwał 0,5 milisekundy, podczas gdy cała rozdzielczość trwała od 1 do 3 milisekundy (używałem Javy, innych języków lub środowisk może dać różne wyniki).

Po drugie, większość problemów nie wymaga cofania. A ci, którzy to robią, potrzebują go tylko późno w rozwiązaniu problemu, raz wszystko zasady gry zostały wyczerpane i musimy postawić hipotezę.

Oto mój własny grosz. Mam nadzieję, że to pomoże.

Pamiętaj, że komunikacja między procesorami/między wątkami jest droga. Nie używaj wielu wątków, chyba że Masz do. Jeśli nie ma zbyt wiele pracy/obliczeń do wykonania w innych wątkach, równie dobrze możesz po prostu przejść do jednego wątku.

Staraj się jak najwięcej unikać dzielenia danych między wątkami. Używaj ich tylko wtedy, gdy jest to konieczne

Korzystaj z rozszerzeń SIMD w miarę możliwości. Z wektorem Rozszerzenia możesz wykonywać obliczenia na wielu danych za jednym zamachem. Może Ci pomóc.