Jak generować plansze Sudoku z unikalnymi rozwiązaniami

Oto jak robi to mój własny program SuDoKu:

1. Zacznij od kompletnej, ważnej planszy (wypełnionej 81 liczbami).

2. Stwórz listę wszystkich 81 pozycji komórek i losowo przetasuj ją.

3. Dopóki lista nie jest pusta, należy zająć następną pozycję z listy i usunąć numer z powiązanej komórki.

4. Przetestuj wyjątkowość za pomocą szybkiego rozwiązania do backtrackingu. Mój solver jest - teoretycznie-w stanie policzyć wszystkie rozwiązania, ale za testując wyjątkowość, zatrzyma się natychmiast, gdy znajdzie więcej niż jedno rozwiązanie.

5. Jeśli bieżąca płyta ma jeszcze tylko jedno rozwiązanie, goto Krok 3) i powtórz.

6. Jeśli bieżąca tablica ma więcej niż jedno rozwiązanie, Cofnij Ostatnie Usunięcie (krok 3) i kontynuuj Krok 3 z następną pozycją z listy

7. Zatrzymaj się, gdy przetestujesz wszystkie 81 pozycji.

To daje nie tylko unikalne tablice, ale tablice, gdzie nie można Usuń kolejne liczby bez niszczenia wyjątkowości rozwiązania.

Oczywiście jest to tylko druga połowa algorytmu. Pierwsza połowa polega na znalezieniu kompletnej ważnej planszy (losowo wypełnionej!) Działa bardzo podobnie, ale "w innym kierunku":

1. Zacznij od pustej planszy.

2. Dodaj losowy numer na jednej z wolnych komórek (komórka jest wybierana losowo, a numer jest wybierany losowo z listy numerów ważnych dla tego komórki zgodnie z zasadami SuDoKu).

3. Użyj narzędzia backtracking solver, aby sprawdzić, czy na bieżącej płytce znajduje się co najmniej jedno poprawne rozwiązanie. Jeśli nie, Cofnij Krok 2 i powtórz z innym numerem i komórką. Zauważ, że ten krok może tworzyć pełne ważne tablice samodzielnie, ale nie są one w żaden sposób losowe.

4. Powtarzaj, aż plansza będzie całkowicie wypełniona liczbami.

Możesz oszukiwać. Zacznij od istniejącej planszy Sudoku, którą można rozwiązać, a następnie majstrować przy niej.

Możesz zamienić dowolny wiersz z trzech bloków 3x3 z dowolnym innym wierszem. Możesz zamienić dowolną kolumnę z trzech bloków 3x3 z inną kolumną. W każdym wierszu bloku lub kolumnie bloku można zamieniać pojedyncze wiersze i pojedyncze kolumny. Wreszcie można permutować liczby, więc istnieją różne liczby w wypełnionych pozycjach, o ile permutacja jest spójna na całej planszy.

Brak zmiany te sprawią, że rozwiązywalna tablica będzie nierozwiązywalna.

Chyba że P = NP, nie ma algorytmu czasu wielomianowego do generowania ogólnych problemów Sudoku z dokładnie jednym rozwiązaniem.

Przepraszam, że psuję wam nadzieje na szybki algorytm!

Nie jest łatwo podać ogólne rozwiązanie. Musisz wiedzieć kilka rzeczy, aby wygenerować konkretny rodzaj Sudoku... na przykład, nie można zbudować Sudoku z więcej niż dziewięcioma pustymi 9-liczbowymi grupami (wiersze, bloki 3x3 lub kolumny). Minimalne podane liczby (tj." wskazówki") w Sudoku z pojedynczym rozwiązaniem są uważane za 17, ale pozycje liczbowe dla tego Sudoku są bardzo specyficzne, jeśli się nie mylę. Średnia liczba wskazówek do Sudoku to około 26, i nie jestem pewien, ale jeśli zrezygnujesz z liczb ukończona siatka do 26 i pozostawić je w sposób symetryczny, możesz mieć poprawne Sudoku. Z drugiej strony, możesz po prostu losowo zamknąć numery z ukończonych siatek i testować je za pomocą CHECKERA lub innych narzędzi, aż pojawi się OK.

Myślę również, że będziesz musiał wyraźnie sprawdzić wyjątkowość. Jeśli masz mniej niż 17 givenów, unikalne rozwiązanie jest bardzo mało prawdopodobne: nie znaleziono jeszcze żadnego, chociaż nie jest jeszcze jasne, czy może ono istnieć.)

Ale możesz również użyć SAT-solvera, w przeciwieństwie do pisania własnego algorytmu backtrackingu. W ten sposób możesz do pewnego stopnia regulować, jak trudno będzie znaleźć rozwiązanie: jeśli ograniczysz reguły wnioskowania, których używa SAT-solver, możesz sprawdzić, czy możesz łatwo rozwiązać zagadkę. Wystarczy wpisać w google "SAT solving sudoku".

Oto sposób na klasyczne łamigłówki sudoku (sudoku z jednym i jedynym rozwiązaniem; wstępnie wypełnione kwadraty są symetryczne wokół środkowego kwadratu R5C5).

1) Zacznij od kompletnej siatki (używając wypełnienia grupowego i kołowego przesunięcia, aby łatwo ją uzyskać)

2) Usuń liczby z dwóch symetrycznych kwadratów, jeśli wyczyszczone kwadraty można wywnioskować za pomocą pozostałych wskazówek.

3) Powtórz (2), aż wszystkie liczby zostaną sprawdzone.

Za pomocą tej metody można utworzyć bardzo łatwa łamigłówka sudoku z programowaniem lub bez. Możesz również użyć tej metody do tworzenia trudniejszych łamigłówek Sudoku. Możesz wyszukać "Utwórz klasyczne sudoku" na YouTube, aby uzyskać przykład krok po kroku.