Generowanie planszy w Sudoku

Witam. Ostatnio nie mogąc spać grałem na Nokii w Sudoku i pomyślałem sobie, że mimo że są dostępne w sieci różne gry
napisane w różnych językach - w tym w Delphi, to spróbuje napisać własne. No i utknąłem przy tym jak poprawnie stworzyć
unikalną planszę. To znaczy żeby cyfy od 1 do 9 w 81 polach nie powtarzały się ani w wierszu ani w kolumnie. Pomyślałem
sobie, że jak będę konwertował wylosowaną liczbę na tekst, a później dodawał ją do StringListy (SL_X odpowiedzialnej za
wiersze), a później sprawdzał Pos'em czy wylosowana ponownie liczba jest już w wierszu o zerowym indeksie StringListy.
Jeżeli nie to dodawał bym kolejne kolumny, a po uzyskaniu 9 zapełnionych kolumn czyścił Stringlistę, zwiększał Indeks wierszy
o jeden, a indeks kolumn zerował. No i to działa w wierszach losuje mi unikalne liczby, ale chciałem to samo zrobić dla kolumn,
z tym że jak widać w kodzie, użyłem tablicy 9 stringlist. Jednak kiedy do kodu dodaję (dla Wiesza o indeksie większym od zera):

      if (Pos(S, SL_X[0]) = 0)
      and (Pos(S, SL_Y[W][0]) = 0) then

To pęrla zamrąża aplikację. Może macie jakieś pomysły na skuteczny algorytm. Prosił bym o jakiś przykładowy kod. I czy w ogóle
mój sposób da prawidłowe rezultaty to znaczy inikalne liczby we wszystkich wierszach i kolumnach (o ile uporam się z tym że
teraz program się zawiesza). A może są jakieś inne sposóby? Googlowałem za źródłami w Delphi, ale znalazłem tylko program,
do rozwiązywania układu, ale z jego źródeł niewiele się dowiedziałem, bo on przy pustej planszy generuje jeden stały układ, a
chyba można takich uzyskać więcej? Z góry dziękuję za wszelkie wskazówki, przykłądowe kody i spsoób poprawienia mojej
merody - o ile w ogóle jest dobra - tak aby można było uzyskać poprawnie wypełnioną planszę do gry w standardowe Sudoku.
Dodam, że użyłem akurat StringList, bo można je łatwo wyświetlić, czego nie umiem ze zbiorami, tablice też mi śie tutaj zbyt
skomplikowane wydały, bo trzeba by było inaczej sprawdzać czy już liczba wylosowana, a tak to tę robotę odwala tutaj Pos().

var
  K, W, I : Byte;
  S : string;
  SL_X : TStringList;
  SL_Y : array[0..8] of TStringList;
begin
  CzyscSG; // Ustawia tekst wszystkich komórek StringGrid na '':
  SL_X := TStringList.Create;
  SL_X.Add('');
  for I := Low(SL_Y) to High(SL_Y) do
  begin
    SL_Y[I] := TStringList.Create;
    SL_Y[I].Add('');
  end;

  K := 0;
  W := 0;
  repeat
    S := IntToStr(Random(9) + 1);
    if (W = 0) then
    begin
      if (Pos(S, SL_X[0]) = 0) then
      begin
        SL_X[0] := SL_X[0] + S;
        SG1.Cells[K, W] := S;
        SL_Y[K][0] := SL_Y[K][0] + S;
        K := K + 1;
      end;
    end
    else
    begin
      if (Pos(S, SL_X[0]) = 0)
      then
      begin
        SL_X[0] := SL_X[0] + S;
        SG1.Cells[K, W] := S;
        SL_Y[K][0] := SL_Y[K][0] + S;
        K := K + 1;
      end;
    end;

    if K = SG1.ColCount then
    begin
      K := 0;
      W := W + 1;
      SL_X[0] := '';
    end;
  until W = SG1.RowCount;
end;

Z tym Stringlist'em to zaszalałeś. Procedura sprawdzania wystąpienia jakiegoś elementu w wierszu
(array[0..8,0..8] of byte) zajmuje aż 6 LOC ale to nie powód aby zaraz wymyślać jakieś kosmiczne struktury danych.

Poza tym, algorytm który generuje na początku pełną i wypełnioną tablicę 9x9 a dopiero później wybiera które z elementów tej tablicy mają być pokazane w zagadce wydaje mi się być nietrafiony.
Ja zrobił bym to mniejwięcej tak:

sudoku:=Tsudoku.new();
while sudoku.iloscrozwiazan<>1 do
begin
  if sudoku.iloscrozwiazan>1 then
    sudoku.dodaj_komorke(random(9),random(9),random(9))
  else 
     sudoku.usun_ostatnio_dodana_komorke;
end;
sudoku.wyswietl;

Czyli problem sprowadza się do zaimplementowania sudoku.iloscrozwiazan , ale i tak musiał byś napisać coś podobnego aby sprawdzić czy twoja zagadka ma dokładnie jedno rozwiązanie. (Poprawna łamigłowka ma tylko jedno rozwiązanie).

TIntegerList zamiast TStringList. Ewentualnie TList. Masz liczby, masz robić operacje na liczbach, nie babraj się w szambie stringów.

Generowanie pelnej tablicy będącej poprawnym rozwiązaniem to dobry pomysł, ale kombinacji do sprawdzenia jest naprawde wiele. Proponuje pomyśleć nad jakąś funkcją rekurencyjną, która sprawdzałaby całą planszę (przyda się poźniej do wykrywania prawidłowego rozwiązania).

Jeszcze pokopmbinuję, chociaż na razie dałem sobie spokój. Mam źródło Sudoku Solvera, ale jak dla
mnie jest zbyt "zakręcone" autor jego też właśnie sprawdza ilość rozwiązań ale tam używa TList, która
przechowuje 81 MaskEditów i przy pustej planszy gneruje zawsze taki sam układ, a dopiero jak coś w
MaskEditach z liczb się znajduje to sprawdza jakie liczby można wstawić o ile się da aby było "solved".

Odświeżam temat, bo nadal da się znaleźć go poprzez google, poszukałem tam gdzie najciemniej czyli pod
latarnią, a więc na www.torry.net i okazuje się że jest tam Solver, ktory w zależności od tego, jakie już do
StringGrida wprowadzimy liczby wygeneruje (o ile się uda) poprawną planszę. Trzeba przeanalizować tylko
na spokojnie jego źródła, co póki co robię, bo trochę brzydko sformatowany jest kod, ale idzie się połapać.
Dla zainteresowanych podaje dokładny link http://www.torry.net/apps/games/gameslogical/Sudoku.zip

Ojej, przez 0.5 roku Cię to męczy?
Aż postanowiłem to napisać specjanie dla ciebie

type TSudoku=class(TObject)
  protected
    Ctr:integer;
  public
    X:array[1..9,1..9] of byte;
    function IsProper:boolean;
    function Solutions:Byte;
    procedure PrintMe;
    constructor Create(Fill:Boolean);
  end;

procedure TSudoku.PrintMe;
var a,s:integer;
Str:String;
begin
  For a:=1 to 9 do
  begin
    str:='';
    For s:=1 to 9 do
    begin
      if X[a,s]=0 then
        str:=str+' '
      else
        str:=str+inttostr(X[a,s]);
      if s mod 3=0 then str:=str+'|';
    end;
    Form1.Memo1.Lines.Add(Str);
    if a mod 3=0 then
      Form1.Memo1.Lines.Add('---+---+---');
  end;
end;

function TSudoku.IsProper:boolean;
var a,s:integer;
  Rows,Cols,Boxes:array[1..9,0..9] of byte;
begin
  for s:=1 to 9 do
    for a:=1 to 9 do
    begin
      Rows[a,s]:=0;
      Cols[a,s]:=0;
      Boxes[a,s]:=0;
    end;
  for a:=1 to 9 do
    for s:=1 to 9 do
    begin
      inc(Rows[a,X[a,s]]);
      inc(Cols[s,X[a,s]]);
      inc(Boxes[1+(a-1) div 3+((s-1) div 3)*3,X[a,s]]);
    end;
  Result:=False;
  For a:=1 to 9 do
    For s:=1 to 9 do
      if (Rows[a,s]>1) or (Cols[a,s]>1) or (Boxes[a,s]>1) then
        Exit;
  result:=True;
end;

function TSudoku.Solutions:Byte;
var a,s,i,Temp:integer;
begin
  if IsProper then
  begin
    inc(Ctr);
    for a:=1 to 9 do
      for s:=1 to 9 do
        if X[a,s]=0 then
        begin
          Result:=0;
          For i:=1 to 9 do
          begin
            X[a,s]:=i;
            Temp:=Solutions;
            if Ctr>50000 then
            begin
              X[a,s]:=0;
              Result:=0;
              Exit;
            end;
            if Temp>1 then
            begin
              X[a,s]:=0;
              Result:=Temp;
              Exit;
            end;
            if Temp=1 then
            begin
              if Result=1 then
              begin
                Result:=2;
                X[a,s]:=0;
                Exit;
              end
              else
                Result:=1;
            end
          end;
          X[a,s]:=0;
          Exit;
        end;
    Result:=1;
  end
  else
    Result:=0;
end;

constructor TSudoku.Create(Fill:Boolean);
var a,s:integer;
begin
  for a:=1 to 9 do
    for s:=1 to 9 do
      X[a,s]:=0;
  While True do
  begin
    Ctr:=0;
    Case Solutions of
    2:
      begin
        repeat
          a:=1+Random(9);
          s:=1+Random(9);
        until X[a,s]=0;
        X[a,s]:=Random(9)+1;
      end;
    0:
      X[a,s]:=0;
    1:
      Exit;
    end;
  end;
end;

Pozdr.

Dzięki za rozwiązanie, przyda się, a tak specjalnie mnie to nie męczyło, tylko wróciłem do starego projektu i
po prostu kombinowałem jak to zrobić żeby działało. Twoj kod na pewno się przyda nie tylko mi, ale także i
innym osobom, bo szukając frazy Delphi sudoku Polak trafi między innymi na ten wątek no i go przeczyta :)

Jeżeli zajmujesz się sudoku, musisz wiedzieć, że generowanie losowej zapełnionej planszy to nic innego jak rozwiązywanie nieoznaczonego(mającego wiele rozwiązań) układu sudoku. Istnieje bardzo dużo algorytmów rozwiązywania sudoku. Można je podzieliś na dwie klasy:

Brute Force - na podstawie bardzo prostych zasad generuje się bardzo losową planszę po czym sprawdza się czy jest poprawna.

Generic - na podstawie bardziej skomplikowanych reguł generuje się planszę, która niemal na pewno jest poprawna, tutaj możliwe jest zakleszczenie - im trudniejszy algorytm rozwiązujący, tym częściej plansza będzie poprawna.

Usuwanie losowych pól z pełnej planszy, też nie może być losowe, musisz je usuwać tak, aby po usunięciu plansza była oznaczona(miała jedno rozwiązanie)

Zapewne interesuje Cię prosty przykład klasy Generic. Do stworzenia takiej, potrzebny Ci będzie typ danych przechowujących wszystkie pola. Pole powinno przechowywać następujące informacje - wszystkie możliwe liczby, które można wpisac w to pole, liczba tych możliwości(później nazywana stopniem swobody) oraz ewentualnie wartość, która znajduje się w polu (1-9 oraz 'pusty'). Logiczne jest, że na początku wszystkie elementy na pustej planszy mają stopień swobody równy 9. Po wprowadzeniu jednej, losowej wartości, swoboda innych pól powinna się zmienić, to w jaki sposób obliczasz tą swobodę jest kluczowe. Dla prostego przykładu załóżmy, że będziemy obliczać swobodę tylko na podstawie, tego, czy któraś liczba znajduje się w tej samej kolumnie, obszarze, czy wierszu. Jeżeli w wierszu/kolumnie/obszarze znajduje się liczba usuwamy ją z dziedziny możliwości tego pola i zmniejszamy swobodę. Swoboda jest równa 1, jeżeli jest w polu jest niepusta wartość - zbiór możliwości składa się tylko z tej liczby.

(Jako, że mam gotowy, autorski, o wiele potężniejszy projekt, niż to co napiszę, w C#, kod będzie C#'owy)

Klasa dziedzina i pole

    class dziedzina
    {
        public int[] zbior;
        public int moc;
//------KONSTRUKTOR
        public dziedzina()
        {
            moc = 9;
            zbior = new int[9];
            for (int i = 1; i < 10; i++)
                zbior[i - 1] = i;
        }
//------USUN WARTOSC O INDEKSIE ARG
        public int wybierz(int arg)
        {
            int ret;       
            moc--;
            ret = zbior[arg];
            for (int i = arg; i < 8; i++)
                zbior[i] = zbior[i+1];
            if (moc >= 0)
                zbior[moc] = 0;
            else
                ret = 10;
            return ret;
        }
//------USUN WARTOSC ARGI
        public void usun(int argi)
        {
            int ret = 0;
            bool flag = false;
            
                for (int i = 0; i < 9; i++)
                if (zbior[i] == argi && argi!=0)
                {
                    flag = true;
                    ret = i;
                }
                if (flag)
                {
                    moc--;
                    
                    for (int i = ret; i < 8; i++)
                        zbior[i] = zbior[i + 1];
                    zbior[moc] = 0;
                }
        }

    }

    class pole
    {
        public dziedzina swoboda;
        public int wartosc;
        public int kolumna;
        public int wiersz;
        public int obszar;
//------KONSTRUKTOR
        public pole(int numer, int wartosc)
        {
            swoboda = new dziedzina();
            this.wartosc = wartosc;
            this.wiersz = numer / 9;
            this.kolumna = numer % 9;
            this.obszar = (numer%9)/3 + 3*(numer/27);
        }
    }

Plansza składa się z 81 takich pól zapisanych w tablicy o nazwie war[]

Sposób liczenia swobody

//------SPOSOBY LICZENIA SWOBODY
        public void licz_swobode_t1(int arg)
        {
            war[arg].swoboda = new dziedzina();
            if (war[arg].wartosc != 0)
            {
                for (int i = 1; i < 10; i++) if (i != war[arg].wartosc) war[arg].swoboda.usun(i);
            }
            else
            {
                for (int i = 0; i < 81; i++)
                {

                    if (war[i].kolumna == war[arg].kolumna && war[i].wartosc!=0)
                        war[arg].swoboda.usun(war[i].wartosc);
                    if (war[i].wiersz == war[arg].wiersz && war[i].wartosc != 0)
                        war[arg].swoboda.usun(war[i].wartosc);
                    if (war[i].obszar == war[arg].obszar && war[i].wartosc != 0)
                        war[arg].swoboda.usun(war[i].wartosc);
                }
            }
        }

Generując losową planszę postępuj tak:

Znajdź pole o najniższym stopniu swobody
Wylosuj wartość z dziedziny tego pola i wpisz ją w wartość tego pola
Oblicz swobodę wszystkich pól

Mniej więcej jedna plansza na trzy nie ulegnie zaklaszczeniu, plansza będzie losowana bardzo szybko

Metoda wypełniania planszy

        private void randomize_Click(object sender, EventArgs e)
        {
           nowa = new plansza();
            for (int j = 0; j < 81; j++)
                {
                    for (int i = 0; i < 81; i++)
                    {
                        nowa.licz_swobode_t1(i);
                        if (nowa.war[i].wartosc == 10)
                        {
                            nowa = new plansza();
                            j = 0;
                        }
                    }
                    nowa.wypelnij();    // metoda wpisująca w pola o swobodzie 1 wartości 
                }
            
        }

To może w dziale DELPHI niech ktoś kod w asemblerze jeszcze poda. to będzie ciekawiej ;]