Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
69
Who we are?
Popescu Andrei
Ciurea Mihai
Guta Andrei
Safta Andy
Dancila Adrian
Metoda Backtracking
Metodele Bactracking
Metoda backtracking se aplică algoritmilor pentru rezolvarea următoarelor tipuri de
probleme:
Fiind date n mulţimi S1, S2, ... Sn, fiecare având un număr numar si de elemente, se cere găsirea
elementelor vectorului X =(x1, x2, ... xn) ϵ S=S1xS2x…Sn, astfel încât să fie îndeplinită o anumită
relaţie φ(x1, x2, … ,xn) între elementele sale.
~Mai multe detalii in Bila cu "Detalii Backtracking!~
Backtracking in plan
Ideaa cautarii cu revenire poate fi generalizata si se poate
aplica si problemelor in care cautarea se realizeaza in plan (intr-o matrice).
In acest caz , solutia se prezinta sub forma unui tablou bidimensional.
Detalii Backtracking
- Relaţia φ(x1, x2, … ,xn) se numeşte relaţie internă (condiție internă), mulţimea S=S1xS2x…Sn
- se numeşte spaţiul soluţiilor posibile, iar vectorul X se numeşte soluţia rezultat.
- Metoda backtracking determină toate soluţiile rezultat ale problemei. Dintre acestea se
- poate alege una care îndeplineşte în plus o altă condiţie.
- Această metodă se foloseşte în rezolvarea problemelor care îndeplinesc simultan
- următoarele condiţii:
- - mulţimile S1, S2, ... Sn sunt mulţimi finite, iar elementele lor se consideră că se află într-o
- relaţie de ordine bine stabilită (de regulă sunt termenii unei progresii aritmetice);
- - nu se dispune de o altă metodă de rezolvare, mai rapidă;
- - x1, x2, …, xn pot fi la rândul lor vectori;
- - S1, S2, ... Sn pot fi identice.
- Metoda backtracking elimină generarea tuturor celor
- si
- i
-
- n
- 1
- nr
- posibilităţi din spaţiul soluţiilor
- posibile (adică a produsului cartezian al celor n mulțimi). În acest scop la generarea vectorului X,
- se respectă următoarele condiţii:
- a) xk primeşte valori numai dacă x1, x2, ... ,xk-1 au primit deja valori;
- b) după ce se atribuie o valoare lui xk, se verifică relaţia (condiția) numită de continuare
- φ
- `
- (x1, x2, … ,xk) care stabileşte situaţia în care are sens să se treacă la calculul lui xk+1.
- Neîndeplinirea condiţiei φ
- `
- exprimă faptul că oricum am alege xk+1, xk+2, ... ,xn nu se ajunge
- la soluţia rezultat.
- În caz de neîndeplinire a condiţiei φ
- `
- (x1, x2, … ,xk), se alege o nouă valoare pentru xk ϵ Sk
- dintre cele nealese, şi se reia verificarea condiţiei φ
- `
- .
- Dacă mulţimea de valori xk s-a epuizat, se revine la alegerea altei valori pentru xk-1 dintre
- cele nealese ş.a.m.d. Această micşorare a lui k dă numele metodei, ilustrând faptul că atunci când
- nu se poate avansa se urmăreşte înapoi secvenţa curentă din soluţia posibilă. Între condiţia internă
- şi cea de continuare există o strânsă legătură. Generarea soluțiilor se termină după ce au fost
- testate toate valorile din S1
Problema Sudoku
"SUDOKU"
O grilă SUDOKU este o matrice 9 x 9 care respectă următoarele proprietăţi:
1. fiecare element al matricii este un număr natural între 1 şi 9;
2. fiecare linie conţine toate numerele naturale de la 1 la 9;
3. fiecare coloană conţine toate numerele naturale de la 1 la 9;
4. fiecare dintre cele 9 submatrici de dimensiune 3 x 3, evidenţiate prin linii îngroşate în exemplul de mai jos, conţine toate numerele de la 1 la 9.
Un puzzle SUDOKU este o matrice 9 x 9 completată parţial cu numere naturale de la 1 la 9. Mai jos este un exemplu de puzzle SUDOKU. O soluţie a unui astfel de puzzle este o grilă sudoku care coincide cu puzzle-ul pe poziţiile precompletate.
Cerința
Scrieţi un program care, pentru o matrice 9 x 9 dată, reprezentând un puzzle SUDOKU, determină o soluţie a unui astfel de puzzle, după regulile de mai sus.
Date de intrare
Fișierul de intrare sudoku.in conține o matrice 9 x 9 (câte 9 elemente pe câte o linie a fişierului, fiecare element fiind separat printr-un spaţiu), reprezentând un puzzle SUDOKU, în care poziţiile necompletate au valoarea 0.
Date de ieșire
Fișierul de ieșire sudoku.out va conține o matrice 9 x 9 (câte 9 elemente pe câte o linie a fişierului, fiecare element fiind separat printr-un spaţiu), reprezentând soluţia puzzle-ului din fişierul de intrare.
Restricții și precizări
puzzle-ul din fişierul de intrare are soluţie unică, pentru toate testele
Exemplu:
sudoku.in
2 5 8 7 3 0 9 4 1
6 0 9 8 2 4 3 0 7
4 0 7 0 1 5 2 6 0
3 9 5 2 7 0 4 0 6
0 6 2 4 0 8 1 0 5
8 4 0 6 5 0 7 2 9
1 8 4 3 6 9 5 7 2
0 7 0 1 4 2 0 9 3
9 2 3 5 8 7 6 1 4
sudoku.out
2 5 8 7 3 6 9 4 1
6 1 9 8 2 4 3 5 7
4 3 7 9 1 5 2 6 8
3 9 5 2 7 1 4 8 6
7 6 2 4 9 8 1 3 5
8 4 1 6 5 3 7 2 9
1 8 4 3 6 9 5 7 2
5 7 6 1 4 2 8 9 3
9 2 3 5 8 7 6 1 4
Exemplu
Notatii
Cititi daca va intereseaza :)
#include <fstream>
using namespace std;
ifstream f("sudoku.in")
ofstream g("sudoku.out");
int a[10][10],i,j,n,k;
int st[3][100],as,ev,gast;
void succesor()
{
if(a[st[1][k]][st[2][k]]<9)
{
a[st[1][k]][st[2][k]++;
as=1;
}
else as=0;
}
void valid()
{
int i,j;
ev=1;
//parcurg linia
for(j=1;j<=9;j++)
if(j!=st[2][k]&&a[st[1][k]][j]==a[st[1][k]][st[2][k]])
ev=0;
//parcurg coloana elementului de pe nivelul k
for(i=1;i<=9;i++)
if(i!=st[1][k]&&a[i][st[2][k]]==a[st[1][k]][st[2][k]])
ev=0;
//parcurg careul corespunzator elementului a[st[1][k]][st[2][k]]
if(st[1][k]>=1&&st[1][k]<=3&&st[2][k]>=1&&st[2][k]<=3)
{
for(i=1;i<=3;i++)
for(j=1;j<=3;j++)
if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k] j!=st[2][k]))
ev=0;
}
else
if(st[1][k]>=1&&st[1][k]<=3&&st[2][k]>=4&&st[2][k]<=6)
{
for(i=1;i<=3;i++)
for(j=4;j<=6;j++)
if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k] j!=st[2][k]))
ev=0;
}
else
if(st[1][k]>=1&&s[1][k]<=3&&st[2][k]>=7&&st[2][k]<=9)
{
for(i=1;i<=3;i++)
for(j=7;j<=9;j++)
if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k] j!=st[2][k]))
ev=0;
}
else
if(st[1][k]>=4&&st[1][k]<=6&&st[2][k]>=1&&st[2][k]<=3)
{
for(i=4;i<=6;i++)
for(j=1;j<=3;j++)
if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k] j!=st[2][k]))
ev=0;
}
else
if(st[1][k]>=4&&st[1][k]<=6&&st[2][k]>=4&&st[2][k]<=6)
{
for(i=4;i<=6;i++)
for(j=4;j<=6;j++)
if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k] j!=st[2][k]))
ev=0;
}
else
if(st[1][k]>=4&&st[1][k]<=6&&st[2][k]>=7&&st[2][k]<=9)
{
for(i=4;i<=6;i++)
for(j=7;j<=9;j++)
if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k] j!=st[2][k]))
ev=0;
}
else
if(st[1][k]>=7&&st[1][k]<=9&&st[2][k]>=1&&st[2][k]<=3)
{
for(i=7;i<=9;i++)
for(j=1;j<=3;j++)
if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k] j!=st[2][k]))
ev=0;
}
else
if(st[1][k]>=7&&st[1][k]<=9&&st[2][k]>=4&&st[2][k]<=6)
{
for(i=7;i<=9;i++)
for(j=4;j<=6;j++)
if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k] j!=st[2][k]))
ev=0;
}
else
if(st[1][k]>=7&&st[1][k]<=0&&st[2][k]>=7&&st[2][k]<=9)
{
for(i=7;i<=9;i++)
for(j=7;j<=9;j++)
if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k] j!=st[2][k]))
ev=0;
}
void tipar()
{
int i,j;
for(i=1;i<=9;i++)
{
for(j=1;j<=9;j++)
g<<a[i][j]<<" ";
g<<endl;
}
gasit=1;
}
int main()
{
for(i=1;i<=9;i++)
for(j=1;j<=9;j++)
{
f>>a[i][j];
if(a[i][j]==0)
{
n++;
st[1][n]=i;
st[2][n]=j;
}
}
k=1;
while(k>0&&!gasit)
{
do
{
succesor();
if(as)
valid();
}
while(as&&!ev);
if(as)
if(k==n)
tipar();
else
k++;
else
{
a[st[1][k]][st[2][k]]=0;k--;
}
}
return 0;
}