Jaka może być różnica w złożoności między znalezieniem rozwiązania łamigłówki Sudoku a POTWIERDZENIEM, że jest to rozwiązanie unikalne?

Zwykle więc Sudoku ma , ale to pytanie rozciąga się również na zagadek o . Istnieje wiele reguł wielomianowego odliczania czasu, które mogą poczynić postępy w znalezieniu rozwiązania łamigłówki Sudoku. Ale czasem wartości odgadnięcia i następujące łańcuchy wniosków mogą być wymagane w celu wyeliminowania wartości komórki lub kombinacji wartości komórek. Jednak po znalezieniu prawidłowego rozwiązania nie gwarantuje to, że jest ono UNIKALNE. Prawidłowa łamigłówka Sudoku powinna mieć tylko jedno prawidłowe rozwiązanie, ale podczas generowania losowych łamigłówek może to wymagać dodatkowych obliczeń w celu weryfikacji.$9 \times 9$$n^2 \times n^2$$n > 3$

Moje pytanie brzmi: jeśli pozwolimy na pewien zestaw reguł wielomianowego odliczania czasu (powiedzmy, najczęstszy zbiór opisany w strategii Sudoku), wraz z wartościami zgadywania i podążaniem za wnioskami, to o ile trudniej będzie ustalić, czy istnieje unikalne rozwiązanie danej łamigłówki, a nie znalezienie tylko jednego rozwiązania pod względem liczby nie unikalnych rozwiązań? Czy istnieje asymptotyczna różnica dla niektórych klas puzzli?

Yato i Seta pokazują, że dla każdego stałego , biorąc pod uwagę rozwiązań łamigłówki Sudoku, NP-zupełne jest ustalenie, czy istnieje inne rozwiązanie. Pokazują, że tę samą właściwość spełniają również inne układanki.$m$$m$

Jeśli dobrze cię rozumiem, próbujesz sprawdzić łamigłówki Sudoku wygenerowane przez twoje oprogramowanie, aby sprawdzić, czy są poprawne.

Jeśli interesująca jest tylko „ważność”, Yuval Filmus już wskazał ci dowód, że jest ona NP kompletna.

Jednak jeśli celem jest znalezienie nowych łamigłówek sudoku, które dana osoba z przyjemnością rozwiąże, problem nie będzie tak trudny. (Konieczność odgadnięcia wielu wartości, ponieważ nie można rozwiązać układanki za pomocą „logiki”, nie jest zabawą!) Dlatego osobiście ograniczyłem liczbę zgadnięć do maksymalnie 4 i odrzuciłbym każdą układankę, której nie można udowodnić, że ma unikalne rozwiązanie w granicach tego, co uważasz za uzasadnione.

Robiąc powyższe, używając standardowego śledzenia wstecznego, aby odwiedzić wszystkie możliwe domysły (w ramach twojego limitu) i pokazując, że istnieje tylko jedno rozwiązanie, jest znacznie łatwiejsze niż NP kompletne.

Dodatkowo możesz ocenić, jak trudna jest łamigłówka, na podstawie złożoności potrzebnych reguł dedukcyjnych i liczby potrzebnych zgadnięć.

Aby udowodnić, że układanka jest wyjątkowa, każda komórka, w której należało zgadywać, musi być rozgałęziona. Podczas wyszukiwania w celu znalezienia odpowiedzi zazwyczaj wykonuje się to za pomocą śledzenia wstecznego, gdzie rozwiązaniem jest pierwsza ścieżka w drzewie decyzyjnym, która prowadzi do kompletnej tablicy. Aby udowodnić wyjątkowość, musisz pokazać, że tylko jedna ścieżka prowadzi do prawidłowego rozwiązania. To jest bardzo trudne do zdefiniowania pod względem czasu działania. Złożoność jest niezwykle związana z rzeczywistym problemem. Jeśli patrzysz na scenariusz najgorszego przypadku, który jest bardzo mało prawdopodobny, można je uznać za taką samą złożoność.

W najgorszym przypadku, podczas rozwiązywania, rozwiązanie znajduje się w końcowej możliwej gałęzi drzewa, którą można przeszukać. Aby je znaleźć, trzeba było przeszukać całe drzewo, podczas gdy poszukiwanie wyjątkowości wymagałoby również tego samego wyszukiwania, idąc dokładnie tymi samymi ścieżkami.

Realistycznie jednak tak nie jest i przy prawie wszystkich przypadkach obejmujących poszukiwanie projektów kombinatorycznych poszukiwanie jednego rozwiązania jest zawsze szybsze niż poszukiwanie wszystkich rozwiązań.

Zasadniczo oba te problemy są mocno zakorzenione w czasach wykładniczych, jeśli nie gorsze.