Titlul: Sudoku
Scris de: Danny Colours din Mai 12, 2014, 20:45:48
Deci... Incerc sa fac un program care sa verifice daca niste numere pot constitui un joc de sudoku intr-o matrice si daca poate fi completata; Partea cu verificatul daca numerele sunt asezate corect ruleaza dar cea de-a doua nu! #include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f("sudoku.in");
ofstream g("sudoku.out");
int a[10][10],i,j,k2,k3,d2=0,r=0,r2=0,k,d=0,aux,v[10],d5=0,s,o10=0,o,aj,aj2;
for(i=1;i<=9;i++)
for(j=1;j<=9;j++)
{f>>a[i][j];
if(a[i][j]>0)
d5++;}
d5=81-d5;
for(i=1;i<=9;i++)
for(j=1;j<=9;j++)
if(a[i][j]>=1&&a[i][j]<=9)
{ if(i>=1&&i<=3)
{if(j>=1&&j<=3)
{for(k2=1;k2<=3;k2++)
for(k3=1;k3<=3;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=4&&j<=6)
{for(k2=1;k2<=3;k2++)
for(k3=4;k3<=6;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=7&&j<=9)
{for(k2=1;k2<=3;k2++)
for(k3=7;k3<=9;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++;
d2=0;}}
if(i>=4&&i<=6)
{if(j>=1&&j<=3)
{for(k2=4;k2<=6;k2++)
for(k3=1;k3<=3;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=4&&j<=6)
{for(k2=4;k2<=6;k2++)
for(k3=4;k3<=6;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=7&&j<=9)
{for(k2=4;k2<=6;k2++)
for(k3=7;k3<=9;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}}
if(i>=7&&i<=9)
{if(j>=1&&j<=3)
{for(k2=7;k2<=9;k2++)
for(k3=1;k3<=3;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=4&&j<=6)
{for(k2=7;k2<=9;k2++)
for(k3=4;k3<=6;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=7&&j<=9)
{for(k2=7;k2<=9;k2++)
for(k3=7;k3<=9;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}}}
for(k=1;k<=9;k++)
v[k]=0;
for(i=1;i<=9;i++)
{for(j=1;j<=9;j++)
if(a[i][j]>=1&&a[i][j]<=9)
{aux=a[i][j];
v[aux]++;
for(k=1;k<=9;k++)
if(v[k]>=2)
d++;}
for(k=1;k<=9;k++)
v[k]=0;}
for(k=1;k<=9;k++)
v[k]=0;
for(i=1;i<=9;i++)
{for(j=1;j<=9;j++)
if(a[j][i]>=1&&a[j][i]<=9)
{aux=a[j][i];
v[aux]++;
for(k=1;k<=9;k++)
if(v[k]>=2)
d++;}
for(k=1;k<=9;k++)
v[k]=0;}
for(k=1;k<=9;k++)
v[k]=0;
if(d>0)
r2++;
if(r2>0||r>0)
cout<<"Numerele nu sunt asezate corect";
if(r2==0&&r==0)
cout<<"Numerele sunt asezate corect";
while(o10<1)
for(i=1;i<=9;i++)
for(j=1;j<=9;j++)
if(a[i][j]==0)
{s=0;
for(o=1;o<=9;o++)
{aj=a[i][j]; d2=0; d=0; r=0; r2=0;
a[i][j]=o;
if(i>=1&&i<=3)
{if(j>=1&&j<=3)
{for(k2=1;k2<=3;k2++)
for(k3=1;k3<=3;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=4&&j<=6)
{for(k2=1;k2<=3;k2++)
for(k3=4;k3<=6;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=7&&j<=9)
{for(k2=1;k2<=3;k2++)
for(k3=7;k3<=9;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}}
if(i>=4&&i<=6)
{if(j>=1&&j<=3)
{for(k2=4;k2<=6;k2++)
for(k3=1;k3<=3;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=4&&j<=6)
{for(k2=4;k2<=6;k2++)
for(k3=4;k3<=6;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=7&&j<=9)
{for(k2=4;k2<=6;k2++)
for(k3=7;k3<=9;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}}
if(i>=7&&i<=9)
{if(j>=1&&j<=3)
{for(k2=7;k2<=9;k2++)
for(k3=1;k3<=3;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=4&&j<=6)
{for(k2=7;k2<=9;k2++)
for(k3=4;k3<=6;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=7&&j<=9)
{for(k2=7;k2<=9;k2++)
for(k3=7;k3<=9;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}}
for(k=1;k<=9;k++)
v[k]=0;
for(i=1;i<=9;i++)
{for(j=1;j<=9;j++)
if(a[i][j]>=1&&a[i][j]<=9)
{aux=a[i][j];
v[aux]++;
for(k=1;k<=9;k++)
if(v[k]>=2)
d++;}
for(k=1;k<=9;k++)
v[k]=0;}
for(i=1;i<=9;i++)
{for(j=1;j<=9;j++)
if(a[j][i]>=1&&a[j][i]<=9)
{aux=a[j][i];
v[aux]++;
for(k=1;k<=9;k++)
if(v[k]>=2)
d++;}
for(k=1;k<=9;k++)
v[k]=0;}
if(d>0)
r2++;
if(r2==0&&r==0)
{s++; aj2=o;}
a[i][j]=aj;}
if(s==1)
{a[i][j]=aj2;
o10++;}}
if(o10==d5)
cout<<"Jocul poate fi completat";
for(i=1;i<=9;i++)
for(j=1;j<=9;j++)
g<<a[i][j];
g.close();
f.close();
return 0;
}
Si acum sa explic ce am facut...Partea care nu ruleaza incepe de la while. Parcurg matricea ... Daca un elemnt este egal cu 0 (adica nu e nimic) se verifica cate numere pot ocupa acel spatiu. Daca doar un numar , acel spatiu este ocupa de nr respectiv. Cand spun ca nu ruleaza ma refer la faptul ca nu se mai intampla nimic.... Apropo ...uitati o matrice valida 5 3 7 0 8 0 0 2 0 0 6 0 3 9 7 8 0 0 0 0 9 0 5 0 0 0 0 0 1 3 0 2 0 0 0 4 0 2 6 0 0 0 9 3 0 4 0 0 0 7 0 2 6 0 0 0 0 0 4 0 3 0 0 0 0 1 9 6 2 0 7 0 0 4 0 0 3 0 1 9 2 care ar fi trebuit sa fie completata..
Titlul: Răspuns: Sudoku
Scris de: Prehari Romica din Mai 13, 2014, 11:42:13
Nu stiu cat de bine merge ideea ta dar am vazut ca mai folosesti de doua ori for(i=...),for(j=...) in for-urile care folosesc tot i si j. cand iasa din for-urile alea doua, i si j au valoare 10 si nu mai intra in for-urile mari.
si nu cred ca e buna ideea fiindca nu tot timpul primul numar care intra intr-o casuta ii bun...
Titlul: Răspuns: Sudoku
Scris de: Danny Colours din Mai 13, 2014, 13:28:19
Pai intocmai ca nu-l ia pe primul , daca in acel spatiu se potrivesc mai multe numere ramane gol pana la urmatoarea parcurgere...in fine am mai facut niste modificari ... while(ok==1)
{for(i=1;i<=9;i++)
for(j=1;j<=9;j++)
if(a[i][j]==0)
{s=0;
for(o=1;o<=9;o++)
{aj=a[i][j]; d2=0; d=0; r=0; r2=0;
a[i][j]=o;
if(i>=1&&i<=3)
{if(j>=1&&j<=3)
{for(k2=1;k2<=3;k2++)
for(k3=1;k3<=3;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=4&&j<=6)
{for(k2=1;k2<=3;k2++)
for(k3=4;k3<=6;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=7&&j<=9)
{for(k2=1;k2<=3;k2++)
for(k3=7;k3<=9;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}}
if(i>=4&&i<=6)
{if(j>=1&&j<=3)
{for(k2=4;k2<=6;k2++)
for(k3=1;k3<=3;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=4&&j<=6)
{for(k2=4;k2<=6;k2++)
for(k3=4;k3<=6;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=7&&j<=9)
{for(k2=4;k2<=6;k2++)
for(k3=7;k3<=9;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}}
if(i>=7&&i<=9)
{if(j>=1&&j<=3)
{for(k2=7;k2<=9;k2++)
for(k3=1;k3<=3;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=4&&j<=6)
{for(k2=7;k2<=9;k2++)
for(k3=4;k3<=6;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}
if(j>=7&&j<=9)
{for(k2=7;k2<=9;k2++)
for(k3=7;k3<=9;k3++)
if(a[i][j]==a[k2][k3])
d2++;
if(d2>=2)
r++; d2=0;}}
for(k=1;k<=9;k++)
v[k]=0;
for(k9=1;k9<=9;k9++)
{for(k10=1;k10<=9;k10++)
if(a[k9][k10]>=1&&a[k9][k10]<=9)
{aux=a[k9][k10];
v[aux]++;
for(k=1;k<=9;k++)
if(v[k]>=2)
d++;}
for(k=1;k<=9;k++)
v[k]=0;}
for(k9=1;k9<=9;k9++)
{for(k10=1;k10<=9;k10++)
if(a[k10][k9]>=1&&a[k10][k9]<=9)
{aux=a[k10][k9];
v[aux]++;
for(k=1;k<=9;k++)
if(v[k]>=2)
d++;}
for(k=1;k<=9;k++)
v[k]=0;}
if(d>0)
r2++;
if(r2==0&&r==0)
{s++; aj2=o;}
a[i][j]=aj;}
if(s==1)
{a[i][j]=aj2;
o10++;}}
if(s>0)
{ok==1; s=0;}
else
{ok==0; s=0;}}
if(o10==d5)
cout<<"Jocul poate fi completat";
else
cout<<"Jocul nu poate fi completat"; Am adaugat la while ok.. Daca dupa o parcurge nu se adauga niciun numar (s2=0) Nu se mai parcurge a doua ora .. si am rezolvat problema de la i si j insa tot nu merge.... Adica merge doar prima parte..
Titlul: Răspuns: Sudoku
Scris de: Prehari Romica din Mai 13, 2014, 15:00:32
ok... nu m-am uitat eu bine pe cod. ai putea sa verifici daca se poate pune acea cifra si in alte casute din acel patratel de 3x3 si daca nu atunci o pui, altfel treci la urmatoarea...
Titlul: Răspuns: Sudoku
Scris de: Bogdan Boboc din Iulie 15, 2014, 13:42:48
am incercat si eu sa fac un program care rezolva un joc de sudoku cu backtracking dar nu afiseaza nimic si nu-mi dau seama unde e greseala... ](*,) #include <fstream>
#include <cstring>
using namespace std;
ifstream f("sudoku.in");
ofstream g("sudoku.out");
int a[11][11];
int v[11]; // vector de aparitii
void afisare()
{
int k,h;
for(k=1;k<=9;k++)
{
for(h=1;h<=9;h++)
g<<a[k][h];
g<<'\n';
}
}
void back(int i,int j)
{
int l,c,LL,CC,x,y;
if(i==10 && j==1){ afisare(); return; }
else{
if(a[i][j]==0)
{
memset(v,0,sizeof(v));
for(l=1;l<=9;l++)v[a[i][l]]++,v[a[l][j]]++; // marchez elementele de pe linie si coloana in vectorul de aparitii
if(i<4)x=1;
else if(i>=4 && i<7)x=4;
else x=7;
if(j<4)y=1;
else if(j>=4 && j<7)y=4;
else y=7;
LL=x+3;CC=y+3;
for(l=x;l<LL;l++)
for(c=y;c<CC;c++)
v[a[l][c]]++;//marchez elementele din patrat
for(l=1;l<=9;l++)
if(v[l]==0)
{
a[i][j]=l;
if(j==9)back(i+1,1);
else back(i,j+1);
a[i][j]=0;
}
}
else{
if(j==9)back(i+1,1);
else back(i,j+1);
}
}
}
int main()
{
int i,j;
char ch;
for(i=1;i<=9;i++)
for(j=1;j<=9;j++)
f>>ch,a[i][j]=ch-'0';
back(1,1);
return 0;
}
in 530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079
out 534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
(e problema sudoku de pe campion)
Titlul: Răspuns: Sudoku
Scris de: Breahna David din Iulie 17, 2014, 07:44:08
bogdanbobob97 )
Deci fii atent, Am facut si eu problema si din cite ai vazut din pm, meu am facut-o un pic diferit,, Adica sper ca ai observat ca nu m-am folosit de vectorul de aparitii..
DECI>
Tu ai declarat vectorul de aparitii la nivel global,, daca o faci local, in procedura problema e OK !!!!
Pentru ca la fiecare back, valorile din vector sunt modificate si se pierd cele de la back-ul anterior,,
Succes,, :ok: :) :)
Titlul: Răspuns: Sudoku
Scris de: Bogdan Boboc din Iulie 17, 2014, 12:17:17
bogdanbobob97 )
Deci fii atent, Am facut si eu problema si din cite ai vazut din pm, meu am facut-o un pic diferit,, Adica sper ca ai observat ca nu m-am folosit de vectorul de aparitii..
DECI>
Tu ai declarat vectorul de aparitii la nivel global,, daca o faci local, in procedura problema e OK !!!!
Pentru ca la fiecare back, valorile din vector sunt modificate si se pierd cele de la back-ul anterior,,
Succes,, :ok: :) :)
da, de la acel vector era. multumesc!
|