Złożoność algorytmu (Big-O) sudoku solver

Question

Szukam "jak to znaleźć", ponieważ nie mam pojęcia, jak podejść do znalezienia algorytmu złożoności mojego programu.

Napisałem solver sudoku przy użyciu języka Java, bez wydajności w umyśle (chciałem spróbować, aby to działało rekurencyjnie, co udało mi się!)

Niektóre tła:

moja strategia zatrudnia backtracking do określenia , dla danej sudoku, czy puzzle mają tylko jedno unikalne rozwiązanie, czy nie. Więc zasadniczo czytam w danej łamigłówce i rozwiązuję ją. Kiedy znalazłem jedno rozwiązanie, niekoniecznie muszę to zrobić, muszę kontynuować poszukiwania dalszych rozwiązań. Na koniec następuje jedno z trzech możliwych rezultatów: układanka nie jest w ogóle możliwa do rozwiązania, zagadka ma unikalne rozwiązanie lub układanka ma wiele rozwiązań.

Mój program odczytuje współrzędne puzzli z pliku, który ma jedną linię dla każdej cyfry, składającą się z wiersza, kolumny i cyfry. Przez własnej konwencji, górny lewy kwadrat 7 jest napisane jak 007.

Realizacja:

załadować wartości z pliku i przechowywać je w tablicy 2-D idę w dół tablica do znalezienia Blank (wartość niewypełniona) i ustaw ją na 1. I sprawdź, czy nie ma konfliktów (czy wprowadzona wartość jest poprawna czy nie). Jeśli tak, przechodzę do następnej wartości. Jeśli nie, zwiększam wartość o 1, dopóki nie znajdę cyfry, która działa, lub jeśli żadna z nich nie działa (od 1 do 9), cofam się o 1 krok do ostatniej wartości, którą skorygowałem i zwiększam ją (używając rekursja). Zrobiłem rozwiązanie, gdy wszystkie 81 elementów zostało wypełnionych, bez konfliktów. Jeśli zostaną znalezione jakieś rozwiązania, wydrukuję je na terminalu. W przeciwnym razie, jeśli spróbuję "cofnąć się o jeden krok" od elementu PIERWSZY, który początkowo zmodyfikowałem, oznacza to, że nie było żadnych rozwiązań.

W jaki sposób złożoność algorytmu mojego programu? Pomyślałem, że może to być liniowa [O (n)], ale mam dostępu do tablicy wiele razy, więc nie jestem pewien :(

Każda pomoc jest mile widziana

Answer 1

O (nm^) gdzie n jest wiele możliwości dla każdego kwadratu (czyli 9 w klasycznym Sudoku) i m jest liczba miejsc, które są puste.

można to zaobserwować przez pracę wstecz od tylko jednego Jeśli jest tylko jeden pusty, masz n możliwości, które musisz spełnić w najgorszym przypadku. Jeśli są dwa blanki, musisz najpierw przeanalizować możliwości pierwszego blanku i możliwości drugiego półfabrykatu dla każdej z możliwości pierwszego blanku. Jeśli istnieją trzy spacje, musisz najpierw przeanalizować możliwości pierwszego pustego pola. Każda z tych możliwości przyniesie puzzle z dwoma półfabrykatami, które mają różne możliwości.

Algorytm ten przeprowadza pierwsze wyszukiwanie w głąb możliwych rozwiązań. Każdy poziom wykresu reprezentuje wybory dla pojedynczego kwadratu. Głębokość wykresu to liczba kwadratów, które należy wypełnić.Z rozgałęziającą czynnik n i głębokości m, znalezienie rozwiązania w wykres ma występ najgorszy przypadek O (n^m).

Answer 2

W wielu Sudokach będzie kilka numerów, które można umieścić bezpośrednio przy odrobinie myśli. Umieszczając numer w pierwszej pustej komórce, rezygnujesz z wielu okazji, aby zmniejszyć możliwości. Jeśli pierwszych dziesięć pustych komórek ma wiele możliwości, dostajesz wykładniczy wzrost. Chciałbym zadać następujące pytania:

Gdzie w pierwszym wierszu może iść numer 1?

Gdzie w pierwszym wierszu może być numer 2?

...

Gdzie w ostatniej linii numer 9 może udać?

To samo, ale z dziewięcioma kolumnami?

To samo, ale z dziewięcioma pudełkami?

Który numer może zostać umieszczony w pierwszej komórce?

Który numer może trafić do 81. komórki?

To jest 324 pytania. Jeśli dowolne pytanie ma dokładnie jedną odpowiedź, wybierz tę odpowiedź. Jeśli jakiekolwiek pytanie nie ma odpowiedzi, cofasz się. Jeśli każde pytanie ma dwie lub więcej odpowiedzi, wybierasz pytanie z minimalną liczbą odpowiedzi.

You może uzyskać wykładniczy wzrost, ale tylko dla problemów, które są naprawdę trudne.