Generowanie sudoku o zadanej liczbie cyfr

Question

Cześć

Ostatnio siedzę nad algorytmem generowania sudoku o podanej przez użytkownika liczbie widocznych cyfr na starcie gry. Problemem jest wygenerowaniem planszy z liczbą cyfr mniejszą niż 21, do tej pory ani razu taka plansza się nie utworzyła. Przy liczbie 20 program szukał ok. godziny i nie udało się, natomiast dla 21 trwa to ok. minuty. Dodam, że minimalna liczba cyfr to 17, żeby plansza mogła mieć tylko jedno rozwiązanie.

Zasada generowania:

1. utworzenie losowej poprawnej planszy (wszystkie liczby)

2. wylosowanie 'randnum' liczb, które maja być widoczne, czyli ich współrzędnych na planszy z pkt.1 ('randnum' podane przez użytkownika)

3. utworzenie planszy z widocznymi liczbami i sprawdzenie czy taka plansza ma jedno rozwiązanie, jeśli nie, to wróć do pkt. 1

sprawdzenie planszy - algorytm rozwiązuje po kolei puste pola od [1][1], [1][2] ... do ...  [9][8],[9][9] sprawdza liczby 1->9, potem rozwiązuje dla liczb 9->1, następnie rozwiązuje pola od [9][9], [9][8] ... do ...  [1][2],[1][1] sprawdza liczby 1->9, potem rozwiązuje dla liczb 9->1

po każdym rozwiązaniu następuje sprawdzenie czy rozwiązana plansza jest identyczna z planszą z pkt1. - jeżeli NIE, to znaczy, że jest więcej rozwiązań niż 1 i powrót do pkt 1; jeżeli TAK - to sprawdza dalej

Zakładam, że takie czterokrotne sprawdzenie planszy jest wystarczające, ale pewności nie mam. Może ktoś z Was ma inny pomysł na sprawdzenie czy dana plansza ma tylko jedno rozwiązanie?

4. Do tego momentu metoda działała zadowalająco tylko dla liczb >= 30, a dla 25 plansza nie chciała się utworzyć.

Konieczne było wprowadzenie algorytmu sprawdzającego (czy ma jedno rozwiązanie) po usunięciu pojedynczej liczby z planszy (dla liczb mniejszych od założonego limitu (stała LIMIT=35)).

Udało się uzyskać akceptowalne wyniki nawet dla liczby 23 (ale to zależy od szczęścia, hehe).

 

Generalnie dla wartości przy których generowanie planszy trwa zbyt długo (powyżej 2s) można wygenerowane wcześniej plansze zapisać do pliku, a w finalnej aplikacji wczytać taką planszę, tylko takie rozwiązanie mnie nie satysfakcjonuje. No i pozostaje brak plansz <21.

Czy może ktoś wie jak sobie z tym poradzić? 

Żeby chociaż program dał radę takie plansze wygenerować.

 

A to link do githuba, jakby ktoś chciał zobaczyć kod: 

https://gist.github.com/chemikos/477bf33fc7d3b6dd2c60e3137f5aff08

 

 

pozdrawiam

chemikos