Jak mogę wygenerować łamigłówki Sudoku?

Próbuję stworzyć generator łamigłówek Sudoku. Jest to o wiele trudniejsze niż się spodziewałem, a im bardziej się w to pakuję, tym trudniej jest!

Moje obecne podejście polega na podzieleniu problemu na 2 kroki:

1. Wygeneruj kompletną (rozwiązaną) łamigłówkę Sudoku.
2. Usuwaj liczby, aż da się rozwiązać i ma tylko 1 rozwiązanie.

W kroku 1, ponieważ używam metod brutalnej siły, mam problemy z czasem wykonywania. Czy istnieje optymalny sposób wypełnienia pełnej łamigłówki Sudoku?

W kroku 2 jakiego algorytmu powinienem użyć do „puzzlowania” rozwiązanego sudoku?

Mam najlepiej sprzedającą się grę Sudoku w sklepie z aplikacjami na iOS. Oto jak wygenerowałem puzzle.

Najpierw mam aplikację generatora puzzli. Ale to nie jest część kodu gry. Jest to samodzielna aplikacja, której używam do układania puzzli. Jest wysoce zmodyfikowany, więc mogę ustawić go tak, aby tworzył różne typy wzorów, stopnie trudności, liczbę dawców itp. Generowanie zagadek i uzyskanie stałego poziomu trudności jest trudne w locie i zajmuje więcej czasu, niż gracz chciałby czekać. Generuję więc coś, co nazywam „łamigłówkami źródłowymi” i właśnie tego używa kod gry do generowania łamigłówek, w które grają ludzie.

Nie odpowiadam tutaj, jak zakodować generator. Możesz google i znaleźć mnóstwo kodu generatora puzzli online. Zacznij tam. Ale aby stworzyć dobrą grę, musisz stworzyć dobrą grę. Moja gra nie generuje puzzli w locie.

Moja aplikacja do generowania puzzli działa w ten sposób, że generuje tysiące puzzli na minutę, ale nie wszystkie są dobre i nie wszystkie odpowiadają konkretnemu poziomowi trudności. Generator tworzy układankę, a następnie rozwiązuje ją i oblicza stopień trudności, a następnie ocenia układankę na podstawie technik potrzebnych do rozwiązania układanki i określa, czy należy ją zgadnąć (co zwykle jest złe). Wyrzuca wszystkie łamigłówki, które nie spełniają kryteriów. W przypadku trudnych, ale nie niemożliwych łamigłówek na szybkiej maszynie wygenerowanie 100 łamigłówek zgodnych z moją dokładną specyfikacją może zająć godzinę. Dlatego nie robię tego w aplikacji. Generowanie puzzli w locie przy tych trudnych specyfikacjach nie działałoby dla jakości puzzli, które mam w mojej aplikacji.

Łamigłówki to ciągi znaków, długość 162 znaków, 81 znaków z cyframi i myślnikami lub kropkami w miejscu pustych znaków, a następnie kolejne 81 z rozwiązaniem. Następnie kolumny dla każdej statystyki, takie jak liczba pojedynczych, podwójnych itp.

Moje wyniki ze wszystkich sesji generowania to rozdzielone przecinkami wiersze ze statystykami w postaci kolumn. Wezmę może 10 000 zagadek, sprowadzę je do doskonałości i posortuję według trudności. Następnie przenieś je do aplikacji, aby zobaczyć je na planszy. Patrzę też na nie pod względem wizualnym i widocznych wzorów układanki. Następnie ręcznie wybieram spośród nich.

Nazywam je łamigłówkami i oto co mam na myśli. Liczby w grze sudoku to tak naprawdę tylko tokeny. Zamiast być cyframi 1-9, mogą to być kolory, symbole lub litery. Więc moje łamigłówki nasienne nie są liczbami, to litery ai. Każda łamigłówka nasienna zmienia się w locie, tworząc układankę do gry:

1. Losuj liczby / tokeny. Kiedy zamieniam litery ai z powrotem na cyfry 1-9, tabela wyszukiwania jest losowa. Oznacza to, że nie zawsze 1. To samo tworzy około 300 000 odmian każdej układanki.
2. Obróć układankę o 90, 180 lub 270 stopni. To dodaje 4 kolejne warianty.
3. Układaj puzzle poziomo, pionowo lub oba. To dodaje 4 kolejne warianty.

Każda łamigłówka nasienna może zatem utworzyć 5 806 080 odmian. Przetestowałem to w terenie z prawdziwymi graczami. Ludzie nie wiedzą, że grają w tę samą łamigłówkę. To właściwie niemożliwe. Tylko jeśli zauważą, że wzór, w którym są dane, są za każdym razem takie same. Ale nawet przy 100 różnych nasionach nikt tego nie zauważy. Milion użytkowników mojej gry tego nie zrobił. Przetestowałem to również z aplikacjami solver. Aplikacja solver nie rozwiąże układanki w ten sam sposób, gdy zostanie obrócona lub wyrzucona. Czasami nawet analizuje to jako inny stopień trudności, chociaż technicznie jest to ta sama łamigłówka.

Jednak książka Big Bad Sudoku Book zawiera 10 z 1000 łamigłówek z nasionami na 5 poziomach trudności i wiele rodzajów wzorów puzzli. Oznacza to, że w mojej grze są miliardy łamigłówek. Na każde 10 000 łamigłówek nasiennych jest 58 060 800 000 różnych łamigłówek.

W Sudoku Book w wersji 4 (wydanej w 2016 roku) wymyśliłem sposób, aby móc określić dokładną łamigłówkę z tych 58 miliardów i uzyskać tę samą łamigłówkę na urządzeniu każdego gracza.

W kroku (1) Wygeneruj kompletną (rozwiązaną) łamigłówkę Sudoku, ponieważ używam metody brutalnej siły, mam problemy z czasem wykonywania. Czy istnieje optymalny sposób wypełnienia pełnej łamigłówki Sudoku?

Istnieje prosty sposób na wypełnienie kompletnej łamigłówki Sudoku - wypełnianie grupowe i cykliczne przesunięcie.

1. Wypełnij pierwszy wiersz dziewięcioma różnymi liczbami.
2. Wypełnij drugi rząd, który jest przesunięciem pierwszego wiersza o trzy miejsca.
3. Wypełnij trzeci rząd, który jest przesunięciem drugiej linii o trzy miejsca.
4. Wypełnij czwarty rząd, który jest przesunięciem trzeciego o jedno miejsce.

line 1: 8 9 3  2 7 6  4 5 1
line 2: 2 7 6  4 5 1  8 9 3 (shift 3)
line 3: 4 5 1  8 9 3  2 7 6 (shift 3)

line 4: 5 1 8  9 3 2  7 6 4 (shift 1)
line 5: 9 3 2  7 6 4  5 1 8 (shift 3)
line 6: 7 6 4  5 1 8  9 3 2 (shift 3)

line 7: 6 4 5  1 8 9  3 2 7 (shift 1)
line 8: 1 8 9  3 2 7  6 4 5 (shift 3)
line 9: 3 2 7  6 4 5  1 8 9 (shift 3)

Aby uniemożliwić użytkownikowi zauważenie oczywistego wzorca, dobrym pomysłem może być losowa kolejność wierszy i kolumn, aby nie było już żadnego wzorca. Tak długo, jak wszystkie 9 liczb w każdym rzędzie / kolumnie przesunie się razem jako jedna jednostka atomowa, plansza Sudoku zawsze pozostanie ważna.

Otrzymasz kompletnie wypełnioną łamigłówkę Sudoku. Aby uzyskać więcej informacji, możesz wyszukać „make Sudoku”.

Nie jest to zbyt trudne, pod warunkiem, że masz solver sudoku.

Tworzenie sudoku to trudny / interesujący problem, więc najlepiej zachować go na inne pytanie. Lub możesz po prostu przeczytać to i zobaczyć, jak sobie radzisz.

1. Aby wygenerować rozwiązaną łamigłówkę, po prostu uruchom solver na pustej planszy. Jedynym zastrzeżeniem jest to, że powinieneś losowo „zgadywać”, których używa solver, w przeciwnym razie możesz skończyć z tą samą łamigłówką za każdym razem. Oznacza to, że w pewnym momencie solver wypróbuje liczbę dla komórki; może spróbować w następującej kolejności:1, 2, 3, 4, ... i wybierz pierwszy, który działa. Trzeba przetasować że kolejność tak, że stara, powiedzmy 4, 7, 2, 9, .... Ten proces powinien przebiegać tak szybko, jak twój solver.
2. Aby usunąć liczby, użyj tego algorytmu:
   • Wybierz losową liczbę, której wcześniej nie próbowałeś usunąć
   • Usuń numer, uruchom solver z dodanym warunkiem, że nie może tutaj użyć usuniętego numeru
   • Jeśli solver znajdzie rozwiązanie, nie możesz usunąć numeru
   • Powtarzaj, dopóki nie usuniesz wystarczającej liczby numerów (lub nie będziesz mógł usunąć więcej)

Jest to bardzo prosta (i naiwna) metoda, więc nie ma gwarancji, że otrzymasz łamigłówki o określonej trudności - oprócz liczby brakujących liczb - lub jeśli możesz nawet usunąć liczbę liczb, którą chcesz. Mam nadzieję, że i tak to pomaga.

Myślę, że interesujące jest wskazanie tej strony , ponieważ bardzo pomogło mi to w rozwoju naszych projektów. Tworzenie sudoku z unikalnym rozwiązaniem jest dalekie od prostego zadania. W linku można znaleźć, w jaki sposób autor (naprawdę wykonał świetną robotę, to nie ja, eh!), Znalazł kilka różnych strategii. Możesz mieć pomysł na wygenerowanie własnego solwera Sudoku.

Teraz, przechodząc do tematu, istnieje również sposób na wygenerowanie podobnego sudokusa, tuż

1. Permutacja wierszy.
2. Innym prostym rozwiązaniem jest rozpoczęcie od wypełnienia sudoku z minimalnym 17-cyfrowym wypełnieniem (jest to sprawdzone minimun w celu znalezienia unikalnego rozwiązania) i wypełnienie następujących strategii (np. W poprzednim linku strategie są podzielone według trudności, ty może zrobić coś podobnego), dopóki nie osiągniesz unikalnego rozwiązania.
3. Była lista matematyków próbujących znaleźć 16-cyfrowe unikalne rozwiązanie sudoku, z listą OGROMNYCHEEE z 17 cyframi sudokus. Nie pamiętam, czy ma on jakąkolwiek kopię zapisu, ale jestem prawie pewien, że jeśli zaoferujesz mu inne 17 unikalne rozwiązanie, sudoku z przyjemnością pozwoli ci użyć jego danych.

Pozdrawiam i powodzenia z algorytmem: D

Mój solver używa brutalnej siły i może znaleźć rozwiązanie w ciągu 20 milisekund. Używając opisanej powyżej metody usuwania, mój generator generuje układankę w ciągu 200 milisekund.

Zwykle generuje układankę z około 24-34 cyframi, a ja nadal nie wiem, jak na świecie udało im się stworzyć 17-cyfrową układankę.