Generator losowych Sudoku

13

Chcę wygenerować całkowicie losowe Sudoku .

Zdefiniuj siatkę Sudoku jako siatkę liczb całkowitych od 1 do 9, w której niektóre elementy można pominąć. Siatka jest poprawną łamigłówką, jeśli istnieje wyjątkowy sposób jej wypełnienia, aby dopasować ją do ograniczeń Sudoku (każda linia, kolumna i wyrównany kwadrat 3 × 3 nie ma powtarzającego się elementu) i jest pod tym względem minimalna (tj. Jeśli już pominiesz element ma wiele rozwiązań).9×9193)×3)

Jak mogę wygenerować losową łamigłówkę Sudoku, tak aby wszystkie łamigłówki Sudoku były dostępne?

algorithms randomness sudoku Justin
źródło
To wygląda na realne rozwiązanie: dryicons.com/blog/2009/08/14/…
Joe
1
Istnieje teraz meta pytanie dotyczące tego. Porozmawiaj tam lub na czacie.
Kevin

Odpowiedzi:

15

Generowanie dokładnego równomiernego rozkładu wszystkich łamigłówek sudoku można zrobić w ten sposób: możesz po prostu losowo wygenerować siatkę 9x9, a następnie zachować ją tylko, jeśli jest to poprawna siatka sudoku, w przeciwnym razie spróbuj ponownie.

917

[1,2),..9]9!

Może widzisz, dokąd zmierzam: sprytne rozwiązanie tego problemu prawdopodobnie doprowadzi cię do zastanowienia się nad podstawowymi symetriami siatek sudoku. Dużo pracy wykonano w tym kierunku, aby udowodnić fakt, że 17 to minimalna liczba wskazówek do sudoku ( zobacz ten artykuł ) i możesz przejść tutaj, aby zobaczyć dokładne wyliczenie 5 472 730 538 klas 3 359 233 podobnych siatek, które wykorzystują te symetrie:

  1. Permutacje cyfr
  2. Permutacje rzędów (pasma i rzędy wewnątrz każdego pasma)
  3. To samo dotyczy kolumn
  4. Transpozycja

9!,64,64,2)

EDYCJA: aby dostosować to do niekompletnych łamigłówek, możesz losowo wybrać podzbiór swojej siatki, sprawdzić, czy rozwiązanie jest unikalne dzięki rozwiązaniu sudoku i spróbować ponownie, jeśli nie. To nie jest jednolity rozkład, ponieważ liczba niekompletnych łamigłówek z unikalnym rozwiązaniem może być różna dla dwóch siatek. (Inaczej byłbym bardzo zaskoczony)

jmad
źródło
Ale Justin prosi o sposób wygenerowania niekompletnej układanki, tak aby istniał wyjątkowy sposób jej rozwiązania. Nawet jeśli wygenerujesz siatkę 9x9 spełniającą ograniczenia Sudoku, nie jest jasne, dlaczego usunięcie określonego podzbioru komórek dałoby ci puzzle, które można wykonać w unikalny sposób.
Janoma
1
@Janoma: och, mój zły, będę edytować. Nie ma to jednak większego znaczenia, jeśli nie zdefiniuje się właściwej łamigłówki. (Czy siatka z tylko jedną pustą komórką jest łamigłówką?). Czy chcemy minimalnej siatki (tzn. Jeśli usuniesz cyfrę, rozwiązanie nie jest już unikalne?) To interesujące pytanie.
jmad
„Niektóre elementy można pominąć” jest wystarczająco precyzyjne (tzn. „Jeden lub więcej” elementów można usunąć). Na przykład poprawną łamigłówkę z jedną pustą komórką można ukończyć w unikalny sposób, a pustej łamigłówki nie można, ponieważ istnieje więcej niż jedna poprawna łamigłówka. Ukończoną ważną łamigłówkę można również ukończyć w unikalny (trywialny, pusty) sposób. Pytanie o minimalną siatkę jest również interesujące, ale różni się od tego.
Janoma,
@Janoma, jmad: ważna łamigłówka jest zwykle minimalna, zapomniałem o tym wspomnieć.
Gilles „SO- przestań być zły”
@Gilles Czy to definicja? Zastanawiam się, czy to rzeczywiście jest zamierzone znaczenie OP. Sprawia, że ​​problem jest znacznie trudniejszy :-)
Janoma