Sudoku

[•dannycolours]

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!

Cod:

#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..

[•romyk]

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...

[•dannycolours]

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 ...

Cod:

 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..

[•romyk]

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...

[•bogdanboboc97]

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...

Cod:

#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

Cod:

530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079

out

Cod:

534678912 
672195348 
198342567
859761423 
426853791 
713924856 
961537284 
287419635 
345286179

(e problema sudoku de pe campion)

[•breahnadavid]

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,,

[•bogdanboboc97]

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,,

da, de la acel vector era.
multumesc!