Generowanie sudoku

13.01.2010 @ 13:24:59 by Rafał Kozik | gamedev freedoku

Największym (choć wcale nie tak dużym) wyzwaniem podczas robienia sudoku jest generowanie planszy. Musimy zadbać o to, żeby plansz było dużo, żeby były poprawne (i miały jedno, unikalne rozwiązanie) i żeby można było wybrać poziom trudności. Okazuje się, że rozwiązanie jest bardzo proste i powinno zadowolić każdego.

Jak więc wygląda to proste rozwiązanie? Weźmy dowolną planszę o odpowiednim poziomie trudności i przeróbmy ją tak, żeby wyglądała na unikalną. Gracze nie powinni zauważyć różnicy. Jeszcze tylko trochę terminologii -- grupami pionowymi (poziomymi) będę nazywał grupy trzech kolejnych kolumn (wierszy) na planszy. Mamy więc trzy grupy pionowe i trzy grupy poziome. Sposób w jaki należy przerabiać planszę:

  • zrobić permutację cyfr -- 9! możliwości
  • spermutować kolejność grup pionowych i poziomych -- 3!^2 możliwości
  • spermutować kolumny w grupach pionowych i wiersze w grupach poziomych -- 3!^6 możliwości

Zatem planszę można przerobić na 609 499 054 080 sposobów. Sporo, prawda? Oczywiście nie wszystkie są unikalne (np. gdy plansza ma dwie puste kolumny), ale jest tego wystarczająco dużo. Łatwo zauważyć, że plansza będzie wciąż poprawna i poziom trudności zostanie zachowany. Teraz wystarczy dla każdego poziomu trudności przypożądkować kilka plansz 'startowych' i mamy kompletny system generowania sudoku. Pozostaje tylko jedno pytanie -- skąd wziąć plansze startowe i jak ocenić ich poziom trudności? W sieci można znaleźć różnego rodzaju strony, które rozwiązują sudoku, niektóre z nich podają też ocenę trudności. Pozwala to już na dość dobre zbudowanie bazy plansz 'startowych' i zapewnienie, że żadne z nich nie są izomorficzne ;)



Komentowanie zostało tymczasowo wyłączone.