generowanie sudoku w teorii

0

Witam!

Wziąłem się ostatnio za pisanie sudoku w C++.
I szczerze pisząc, to zacząłem po swojemu - kciałem dobrze, a wyszło jak zawsze :P
Więc pokornie wróciłem do wypróbowanych metod i postarałem się najpierw zrozumieć, jak powstają diagramy sudoku..
I tu pojawił się problem - bo nie mogę tego nigdzie znaleźć..
Szperałem po sieci i dokopałem się tylko do takich info:

  1. sudoku może być symetryczne i asymetryczne
  2. na początq generowania planszy należy opracować sobie symetryczny układ tych cyfr, które będą widoczne na początq gry - i tu pojawia się problem, bo rzeczywiście - widzę symetrię w diagramach, ale nie mogę się dokopać do info, w jaki sposób się je tworzy - tzn. czy można generować te schematy symetrii w dowolny sposób [uzależniony jedynie od ilości cyfr, które kcemy pokazać na starcie], czy też jest jakaś skończona ilość kombinacji układu odsłoniętych cyfr - mam nadzieję, że do tej pory wszystko jest zrozumiałe
  3. samo wypełnianie sudoku, gdy znany jest układ odsłoniętych na początq cyfr, wydaje się być odrębnym problemem, dlatego na razie nie mieszam - póki co nie wiem w jaki sposób wybiera się symetryczny układ cyfr w sudoku - i to jest moje pytanie :)

Czekam na odpowiedź i pozdrawiam!

0

znalazlem cos takiego.. mzoe sie przyda:
http://www.sudokuassistant.com/en/create/

Co do pytania o lustrzane algorytmy... moze zrob algorytm, ktory powklada lustrzanie pare cyfr np na rogach, i sprobuje rozwiazac, jak sie da to bedzie dobrze, a ptoem zaleznie od stopnia trudnosci pochowasz albo odkryjesz jakies kratki :)

0
Arci napisał(a)

czy też jest jakaś skończona ilość kombinacji układu odsłoniętych cyfr

  • oczywiście że jest skończona :D
0

Pół roku temu pisałem grę Sudoku na projekt z kursu C. Program mógł między inymi generować diagramy. Generowanie diagramów zrobiłem tak:
Zaczynałem od pełnej, poprawnie wypełnionej planszy. Potem kolejno usuwałem losowe cyfry. Po każdym usunieciu cyfry sprawdzałem, ile rozwiązań ma powstały w ten sposób diagram. jesli miał dokładnie jedno rozwiązanie, to usuwałem kolejna losowa cyfre. jesli miał wiecej, niż jedno, to wstawiał z powrotem usuniętą cyfrę i próbował z inną. Usuwanie trwało, dopóki nie zostało ileś tam cyfr (chyba ok. 25).
Nie jest to może idealny sposób i niezbyt szybki, ale dzaiała i generuje plansze maksymalnie w kilka sekund. Używam w tym algorytmie procedur do sprawdzania ilości rozwiązań i generowania pełnej planszy, ale napisanie ich jest już dość proste.

0

no ok, a jak generujesz pełne plansze?

0

Pare dni temu napisalem generator plansz sudoku, wiec odpisze na powyzsze pytanie.

Najpierw generuje trzy kwadraty po przekatnej:

7 4 3 0 0 0 0 0 0
5 8 1 0 0 0 0 0 0
6 2 9 0 0 0 0 0 0

0 0 0 2 3 7 0 0 0
0 0 0 6 8 5 0 0 0
0 0 0 4 1 9 0 0 0

0 0 0 0 0 0 8 5 3
0 0 0 0 0 0 4 1 2
0 0 0 0 0 0 7 6 9

Dla kazdego pola w kwadracie losuje liczbe od 1 do 9 z kolekcji. Nastepnie usuwam wylosowana liczbe z kolekcji i losuje nastepna. Itd az do momentu jak zostanie jedna liczba.

Jak juz generator zrobi 3 kwadraty zaczyna generowac nastepne zaczynajac od srodkowego kwadratu w pierwszym wierszu. Dla kazdego pola w kwadracie sprawdza jakie mozna wstawic liczby. Sprawdza najpierw wiersz, kolumne i zbior liczb, ktory mozna jeszcze wstawic w danym kwadracie. Jesli liczba mozliwych cyfr do wstawienia w danym polu w kwadracie wyniesie 0, generator zwroci blad i zacznie generowac nowa plansze. Jesli liczba cyfr mozliwych do wstawienia w danym polu w kwadracie bedzie wieksza od 1, generator wylosuje jedna z cyfr.

Ponizej rozwiazana plansza sudoku z podanego przykladu:

7 4 3 1 6 2 9 8 5
5 8 1 7 9 4 2 3 6
6 2 9 3 5 8 1 7 4

1 5 4 2 3 7 6 9 8
9 7 2 6 8 5 3 4 1
8 3 6 4 1 9 5 2 7

4 6 7 9 2 1 8 5 3
3 9 5 8 7 6 4 1 2
2 1 8 5 4 3 7 6 9

Idea nie jest idealna bo w najbardziej zlosliwym przypadku czas generowania jednej planszy rosnie do nieskonczonosci.

0

ok, to z generowaniem po przekątnej to świetny pomysł :)

tylko że ja mam teraz wypełnione sudoku, a w dalszym ciągu nie wiem, czy istnieje jakaś reguła na symetryczny układ odsłoniętych na starcie cyfr, czy też muszę po kolei zakrywać jedną cyfrę i sprawdzać ilość możliwych rozwiązań..

ale wtedy algorytm jest bardzo niestabilny czasowo, więc to nie może być jedyne rozwiązanie..

czekam na podpowiedzi i pozdrawiam :)

0

dobra, wykminiłem coś takiego:

int table[9][9];

void eliminuj_1_5_9()
{
int i=0,j=0,k=1,ile=0,l=0;

do
{
do
{
for(i=l;i<l+3;i++)
for(j=l;j<l+3;j++)
{
if(table[i][j]==k)
{
ile++;
if(ile>1)
{
table[i][j]=random(9)+1;
eliminuj_1_5_9();
break;
}
}
}
ile=0;
k++;
}
while(k<10);
k=0;
ile=0;
l+=3;
}
while(l!=9);
}

void eliminuj_2()
{
int row=0,i=0,j=0,col=3;

do
{
do
{
for(j=0;j<col;j++)
{
if(table[row][j]==table[row][col])
{
table[row][col]=random(9)+1;
eliminuj_2();
break;
}
}
for(i=3;i<6;i++)
{
if(table[i][col]==table[row][col])
{
table[row][col]=random(9)+1;
eliminuj_2();
break;
}
}
if(row==1)
{
for(j=3;j<6;j++)
{
if(table[0][j]==table[row][col])
{
table[row][col]=random(9)+1;
eliminuj_2();
break;
}
}
}
if(row==2)
{
for(j=3;j<6;j++)
{
if((table[0][j]==table[row][col])||(table[1][j]==table[row][col]))
{
table[row][col]=random(9)+1;
eliminuj_2();
break;
}
}
}
col++;
}
while(col<6);
col=3;
row++;
}
while(row<3);
}

int main()
{
int i=0,j=0,k=0;

randomize();
system("CLS");

// zerowanie tablicy:

for(i=0;i<9;i++)
for(j=0;j<9;j++)
table[i][j]=0;

// wypelnianie losowymi danymi trzech kwadratow po przekatnej:

do
{
for(i=k;i<k+3;i++)
for(j=k;j<k+3;j++)
table[i][j]=random(9)+1;
k+=3;
}
while(k!=9);

// eliminacja cyfr powtarzajacych sie w kwadratach

eliminuj_1_5_9();

// wypelnienie losowymi danymi drugiego kwadratu:

for(i=0;i<3;i++)
for(j=3;j<6;j++)
table[i][j]=random(9)+1;

// eliminacja cyfr powtarzajacych sie w drugim kwadracie:

eliminuj_2();

// wyswietlanie SuDoku:

for(i=0;i<9;i++)
for(j=0;j<9;j++)
{
cout<<table[i][j];
if(j==8)
cout<<endl;
}
system("PAUSE");
}

no i oczywiście nie wypełniłem jeszcze 3-ch małych kwadratów, a już stack overflow..

ale ciekawostką jest fakt, że Borland C++ 6 raz kompiluje i ukazuje poprawną planszę, a raz rzuca errorem - jeżeli przepełniłbym stos, to za każdym razem powinno mi generować stack overflow, prawda?

czekam na sugestie i pozdrawiam :)

P.S. pod devcpp w ogóle nie hula :) po prostu od razu się wyłącza, nawet nie próbuje generacji <:)

0

są łatwiejsze i szybsze sposoby na wygenerowanie losowej permutacji, wylosuj np. liczbe n z (1..2^9) i wybierz n-tą z kolei permutacje korzystając z next_permutation() w stl ;-)

0

Witam. Mam problem z stworzeniem planszy sudoku pod c++ (kompilator Dev-C++) Chciałam skorzystać ze sposobu, wymienionego tutaj, czyli wypełnianie kwadratów po skosie. I wszystko byłoby ładnie pięknie gdyby w ostatnim kwadracie na dole coś się nie chrzaniło. Zamiast wylosowanej liczby wpisuje mi zero, a do tablicy (z której wykreślam już wylosowaną liczbę) nagle zamiast zera wypisuje mi jakąś liczbę. Jeśli ktoś jest w stanie powiedzieć mi gdzie tu jest błąd to będę bardzo wdzięczna.

#include <iostream>
using namespace std;

int sud[9][9];
int t[9];

void kolejne()
{
     for(int i=1; i<=9; i++)
     t[i]=i;
}

void wypelnij_kw(int k, int j)
{
     srand ((int) time(NULL));
     kolejne();
     int x, i=k;
     //wypelnia kw 3x3
     do{ 
        for(int y=k; y<=j; y++)
        {
                t: x=rand()%9+1;
                if(t[x]!=0)
                {
                 sud[i][y]=t[x];
                 t[x]=0;
                 } else goto t;
        }
        i++;
     }while(i<=k+2);
}
main()
{
      for(int k=1; k<=9; k++)
      for(int m=1; m<=9; m++)
      sud[k][m]=0;
      wypelnij_kw(1,3);
      wypelnij_kw(4,6);
      wypelnij_kw(7,9);
      for(int k=1; k<=9; k++)
      for(int m=1; m<=9; m++)
      {
              cout<<sud[k][m]<<" ";
              if(m==9) cout<<endl;
      }
      system("pause");
}

Tutaj zmieniłam fragment żeby mi wypisywał co się dzieje:

                t2: x=rand()%9+1;
                cout<<"\nlos="<<x<<"\nt[x]="<<t[x]<<endl;
                if(t[x]!=0)
                {
                 cout<<"\nt["<<x<<"]: "<<t[x]<<endl;
                 cout<<"SUD_przed["<<i<<"]["<<y<<"]="<<sud[i][y]<<endl;
                 sud[i][y]=t[x];
                 cout<<"SUD["<<i<<"]["<<y<<"]="<<sud[i][y]<<endl;
                 t[x]=0;
                 cout<<"t["<<x<<"]="<<t[x]<<endl;
                 cout<<"cale t ";
                 for(int k=1; k<=9; k++)
                 cout<<t[k]<<" ";
                 } else goto t2;

Chodzi o to, że za każdym razem gdy wskaźniki wynoszą i=9 y=8 lub i=9 y=9 tablica t zamiast samych zer nagle ma liczby, których tam być nie powinno i w efekcie gdy już wyświetla mi całe 3 kwadraty to zero wkrada się do ostatniego. Czasami, mimo że tablica t dalej jest źle, w kwadracie nie pojawia się zero i wszystko niby jest dobrze.
Bardzo proszę, jeśli ktoś widzi czemu to nie działa jak należy, niech odpisze tutaj albo na mój mail: [email protected] ponieważ bardzo mnie ten problem nurtuje i po nocach spać nie mogę [glowa]

0

A czy tywiesz, że tablice w C są indeksowane od zera?
Tak jest be:

int t[9];

void kolejne()
{
     for(int i=1; i<=9; i++)
         t[i]=...

Tak jest dobrze:

int t[9];

void kolejne()
{
     for(int i=0; i<9; i++)
         t[i]=...
0

A już wiem, bo właśnie to znalazłam przed chwilą :) Ale dziękuję bardzo :)

0

Co do generowania planszy, to zacząłbym od jakiegoś prostego układu potem po prostu przestawiałbym losowo wiersze i kolumny w ramach odpowiednich trójek, a na koniec jeszcze podstawił inne cyfry (coś ala szyfr podstawy z losowym kluczem).
Usuwając cyfry z planszy ad hock usunąłbym połowę, a potem sprawdził czy jest jedno rozwiązanie.

Mam, gdzieś na dysku zapisany artykuł naukowy o sudoku i innych tego typu problemach i jak je rozwiązywać, ale nie mam czasu go przeczytać.

0

//html + javascript oczywiscie nie trudno bedzie to przerobić na inne języki.

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN"
"http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
       <style type="text/css">
			   table.moja td {width: 1cm;height:1cm;border:2px solid black;text-align:center; font-size: 200%}
       </style>

</head>
<body>
<script type="text/javascript">
function moz()
{
var ss="<table class='moja'>";
 var x1,x2,x3
for (var i =0; i<9 ; i++){
   ss+="<tr>";
   for (var j =0; j < 9;j++)
		ss+="<td id="+i+""+j+">"+"="+"</td>";
   ss+="</tr>";
}
ss+="</table>";
document.write(ss);
}

tab=[Array(10),Array(10),Array(10),Array(10),Array(10),Array(10),Array(10),Array(10),Array(10),Array(10)];
function sprawdz(x,y,i){
for (var j=0;j<9;j++) if ((tab[x][j]===i)||(tab[j][y]===i)) return false;
var x1= 0;
if (x > 2) x1 = 3;
if (x > 5) x1 = 6;
var y1= 0;
if (y > 2) y1 = 3;
if (y > 5) y1 = 6;
for (var c=x1;c<(x1+3);c++)
  for (var d=y1;d<(y1+3);d++)
      if (tab[c][d]===i) return false;
return true;
}
moz();
ustaw(0,0);
function ustaw(x,y){
		var tablica=[];
		var ret = false;
	   if (x>8) {x = 0 ; y++}
	   if (y>8) return true;
	   for (var i=0;i<9;i++) 
	       if (sprawdz(x,y,i+1)) tablica.push([i+1,Math.random()])
	   	if (tablica.length<1) return false;
		tablica.sort(function(a,b) {return a[1]-b[1]})
	   while (!ret){
	   	if (tablica.length<1) return false;
	   tab[x][y] = tablica.pop()[0];
	   document.getElementById(x+""+y).innerHTML=tab[x][y];
	   ret = ustaw(x+1,y);
	   if (!ret) tab[x][y]=10;
	   }
return true;
}
</script>
</body>
</html>

1 użytkowników online, w tym zalogowanych: 0, gości: 1