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


17

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?


to pytanie zawiera informacje na temat generowania łamigłówek
maniak zapadkowy

3
Ta kwestia została również poproszony o zagadkowych (i ma lepsze odpowiedzi tam): puzzling.stackexchange.com/questions/142/...
congusbongus

Odpowiedzi:


30

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.


Bardzo przydatny post. Czy w jakikolwiek sposób sprawdzasz, czy nasiona, które generujesz, można utworzyć z innych nasion, co oznacza, że ​​masz identyczne nasiona?
VLAS

Tak. Upuszczam je wszystkie w koledze tekstowej i sortuję. Następnie usuń duplikaty. Nie sądzę, żeby to kiedykolwiek zostało usunięte. Nasiona są absolutnie wyjątkowe. Nie można zrobić tej samej układanki z dwóch różnych nasion. Pewnego dnia pokażę dokładny proces, ale nie teraz, kiedy wciąż czerpię zyski z moich metod. :)
badweasel

Właściwie cały mój proces jest prawie tutaj.
badweasel

2
+1 za wgląd w to, że liczby są tylko tokenami, a sposobem dokonywania zmian jest po prostu zmiana liczb przypisanych do liter.
S. Mitchell,

Naprawdę przydatna odpowiedź! Ponieważ masz 3 kolumny i 3 rzędy, powinieneś być w stanie przenieść środkową kolumnę w lewo lub w prawo, a środkowy rząd na górę lub dół, aby wygenerować 4 kolejne warianty. I zamiast odwracać łamigłówkę w pionie lub opadać poziomo, możesz po prostu wymienić lewą i prawą kolumnę (oraz górny i dolny wiersz) na 4 kolejne warianty. Myślę więc, że musisz uzyskać 43 miliony odmian z jednego materiału siewnego.
Roger_S,

4

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”.


3

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.


Upewnij się, że solver nie może znaleźć wielu rozwiązań z tego samego stanu. Zwykle powinno być tylko jedno rozwiązanie. Możesz także sprawdzić, które logiczne kroki solver musiał wykonać, aby znaleźć rozwiązanie w celu ustalenia trudności, np. Czy musiała użyć strategii X-Wing lub ...?
OriginalDaemon

1
@OriginalDaemon dotyczący twojego pierwszego punktu, jest objęty trzecim punktem kropki: jeśli usunięcie tej liczby spowoduje drugie rozwiązanie, wróć.
congusbongus

0

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


Hmm, link jest do solvera sudoku, a nie generatora.
greenoldman

@greenoldman TAK, TO ROZWIĄZANIE. Myślę, że to interesujące dla użytkownika, ponieważ obecnie stosuje metodę usuwania numeru i rozwiązywania. Link podaje strategie szybkiego rozwiązywania częściowych sudoku
David Sánchez

0

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ę.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.