[c++] rozwiązywanie sudoku

0

Mam problem i byłabym bardzo wdzięczna za pomoc. Mógłby mi ktoś powiedzieć czemu wyskakuje mi błąd: error C2065: 'tymczasowa' : undeclared identifier, kiedy ja zmienna "tymczasowa" przekazuje jako rgument funkcji, więc powinna byc odczytywana w tej funkcji normalnie.
A drugie pytanie to czy ktoś mi może pomóc wymyślić jak mogłabym kiedy nie znajdzie rozwiązania jeszcze raz wyszukać minimalnej ilości możliwych do wpisania cyfr w komórce, ale tak żęby to była inna komórka niż przy wcześniejszym wywołaniu tej f-cji?
Z góry dziękuję!

#include <iostream>
#include <cstdlib>
#include<fstream>
#include<string>

using namespace std;

struct komorka
{
    int liczba;
    bool stala;
    bool tab[9];
};

void wyswietlanie (komorka sudoku[9][9])
{
    for(int x=0; x<9; x++)
    {
        if(x%3==0)cout<<"-------------------------\n";  
        for(int y=0; y<9; y++)
        {
            if(y%3==0)cout<<"| ";
            cout<<sudoku[x][y].liczba<<" ";
        }
        cout<<"| ";
        cout<<endl; 
    }
    cout<<"-------------------------\n";
    cout<<endl<<endl;
}

void wyswietlanie_tablic(komorka sudoku[9][9])
{
    for(int x=0; x<9; x++)
    {
        for(int y=0; y<9; y++)
        {
            cout<<"x: "<<x<<"y: "<<y<<"  ";
            for(int i=0; i<9; i++)
            {
                if(sudoku[x][y].tab[i]==true)cout<<i+1<<" ";
            }
            cout<<endl;
        }
    }
}
void sprawdzanie(komorka sudoku[9][9])/*****************przypisywanie wartosci false liczba ktore nie moga byc w komorce*/
{
    int x2, y2, xs, ys;
    for(int x=0; x<9; x++)
    {
        for(int y=0; y<9; y++)
        {
            if(sudoku[x][y].stala!=true)
            {
                for(int i=0; i<9; i++)
                {
                    y2=0;
                    while(y2<9)
                    {
                        if(sudoku[x][y2].liczba==i+1) sudoku[x][y].tab[i]=false;
                        y2++;
                    }
                    x2=0;
                    while(x2<9)
                    {
                        if(sudoku[x2][y].liczba==i+1) sudoku[x][y].tab[i]=false;
                        x2++;
                    }
                    if(x%3==0 && y%3==0)
                    {
                        x2=x;
                        y2=y;
                    }
                    if(x%3==0 && y%3==1)
                    {
                        x2=x;
                        y2=y-1;
                    }
                    if(x%3==0 && y%3==2)
                    {
                        x2=x;
                        y2=y-2;             
                    }
                    if(x%3==1 && y%3==0)
                    {
                        x2=x-1;
                        y2=y;                   
                    }
                    if(x%3==2 && y%3==0)
                    {
                        x2=x-2;
                        y2=y;
                    }
                    if(x%3==2 && y%3==2)
                    {
                        x2=x-2;
                        y2=y-2;                 
                    }
                    if(x%3==1 && y%3==2)
                    {
                        x2=x-1;
                        y2=y-2;                 
                    }
                    if(x%3==2 && y%3==1)
                    {
                        x2=x-2;
                        y2=y-1;                 
                    }
                    if(x%3==1 && y%3==1)
                    {
                        x2=x-1;
                        y2=y-1;                 
                    }
                    xs=x2;
                    ys=y2;
                    for(x2; x2<xs+3; x2++)
                    {
                        for (y2; y2<ys+3; y2++)
                        {
                            if(sudoku[x2][y2].liczba==i+1) sudoku[x][y].tab[i]=false;
                        }
                    }       
                }
            }
        }
    }
}

void wpisywanie_pewnych(komorka sudoku[9][9])
{
    bool zmiana=true;
    int s, ilosc;
    while(zmiana==true)
    {
        zmiana=false;
        for(int x=0; x<9; x++)
        {
            for(int y=0; y<9; y++)
            {
                if(sudoku[x][y].stala!=true)
                {
                    /***********sprawdzanie czy jest tylko jeden mozliwy element w komorce******/

                    s=0;
                    ilosc=0;
                    for(int i=0; i<9; i++)
                    {
                        if(sudoku[x][y].tab[i]==true)
                        {
                            ilosc++;
                            s=i+1;
                        }
                    }
                    if(ilosc==1)
                    {
                        sudoku[x][y].liczba=s;
                        sudoku[x][y].stala=true;
                        zmiana=true;
                        sprawdzanie(sudoku);
                        for(int n=0; n<9; n++)
                        {
                            sudoku[x][y].tab[n]=false;
                        }
                    }
                }
            }
        }
        int z, g, t, tx, ty;
        /************sprawdzanie brakujacych liczb w wierszach*************/
        for(int x=0; x<9; x++)
        {
            for(int i=0; i<9; i++)
            {
                z=0;
                g=0;
                t=0;
                for(int y=0; y<9; y++)
                {
                    if(sudoku[x][y].liczba==i+1)z++;
                }
                if(z==0)
                {
                    for(int y=0; y<9; y++)
                    {
                        if(sudoku[x][y].stala!=true)
                        {
                            if(sudoku[x][y].tab[i]==true)
                            {
                                g++;
                                t=y;
                            }
                        }
                    }
                    if(g==1 && sudoku[x][t].stala!=true)
                    {
                        sudoku[x][t].liczba=i+1;
                        sudoku[x][t].stala=true;
                        zmiana=true;
                        sprawdzanie(sudoku);
                        for(int n=0; n<9; n++)
                        {
                            sudoku[x][t].tab[n]=false;
                        }
                    }
                }
            }
        }
        /************sprawdzanie brakujacych liczb w kolumnach*************/
        for(int y=0; y<9; y++)
        {
            for(int i =0; i<9; i++)
            {
                z=0;
                g=0;
                t=0;
                for(int x=0; x<9; x++)
                {
                    if(sudoku[x][y].liczba==i+1)z++;
                }
                if(z==0)
                {
                    for(int x=0; x<9; x++)
                    {
                        if(sudoku[x][y].stala!=true)
                        {
                            if(sudoku[x][y].tab[i]==true)
                            {
                                g++;
                                t=x;
                            }
                        }
                    }
                    if(g==1 && sudoku[t][y].stala!=true)
                    {
                        sudoku[t][y].liczba=i+1;
                        sudoku[t][y].stala=true;
                        zmiana=true;
                        sprawdzanie(sudoku);
                        for(int n=0; n<9; n++)
                        {
                            sudoku[t][y].tab[n]=false;
                        }
                    }
                }
            }
        }
        /********************sprawdzanie w kwadratach*******************************/
        for(int i =0; i<9; i++)
        {
            z=0;
            g=0;
            tx=0;
            ty=0;
            for(int y=0; y<3; y++)
            {
                for(int x=0; x<3; x++)
                {
                    if(sudoku[x][y].liczba==i+1) z++;
                }
            }
            if(z==0)
            {
                for(int y=0; y<3; y++)
                {
                    for(int x=0; x<3; x++)
                    {
                        if(sudoku[x][y].stala!=true)
                        {
                            if(sudoku[x][y].tab[i]==true)
                            {
                                g++;
                                ty=y;
                                tx=x;
                            }
                        }
                    }
                }
                if(g==1 && sudoku[tx][ty].stala!=true)
                {
                    sudoku[tx][ty].liczba=i+1;
                    sudoku[tx][ty].stala=true;
                    zmiana=true;
                    sprawdzanie(sudoku);
                    for(int n=0; n<9; n++)
                    {
                        sudoku[tx][ty].tab[n]=false;
                    }
                }   
            }
            z=0;
            g=0;
            tx=0;
            ty=0;
            for(int y=3; y<6; y++)
            {
                for(int x=0; x<3; x++)
                {
                    if(sudoku[x][y].liczba==i+1)z++;
                }
            }
            if(z==0)
            {
                for(int y=3; y<6; y++)
                {
                    for(int x=0; x<3; x++)
                    {
                        if(sudoku[x][y].stala!=true)
                        {
                            if(sudoku[x][y].tab[i]==true)
                            {
                                g++;
                                ty=y;
                                tx=x;
                            }
                        }
                    }
                }
                if(g==1 && sudoku[tx][ty].stala!=true)
                {
                    sudoku[tx][ty].liczba=i+1;
                    sudoku[tx][ty].stala=true;
                    zmiana=true;
                    sprawdzanie(sudoku);
                    for(int n=0; n<9; n++)
                    {
                        sudoku[tx][ty].tab[n]=false;
                    }
                }
            }
            z=0;
            g=0;
            tx=0;
            ty=0;
            for(int y=6; y<9; y++)
            {
                for(int x=0; x<3; x++)
                {
                    if(sudoku[x][y].liczba==i+1)z++;
                }
            }
            if(z==0)
            {
                for(int y=6; y<9; y++)
                {
                    for(int x=0; x<3; x++)
                    {
                        if(sudoku[x][y].stala!=true)
                        {
                            if(sudoku[x][y].tab[i]==true)
                            {
                                g++;
                                ty=y;
                                tx=x;
                            }
                        }
                    }
                }
                if(g==1 && sudoku[tx][ty].stala!=true)
                {
                    sudoku[tx][ty].liczba=i+1;
                    sudoku[tx][ty].stala=true;
                    zmiana=true;
                    sprawdzanie(sudoku);
                    for(int n=0; n<9; n++)
                    {
                        sudoku[tx][ty].tab[n]=false;
                    }
                }   
            }
            z=0;
            g=0;
            tx=0;
            ty=0;
            for(int y=0; y<3; y++)
            {
                for(int x=3; x<6; x++)
                {
                    if(sudoku[x][y].liczba==i+1)z++;
                }
            }
            if(z==0)
            {
                for(int y=0; y<3; y++)
                {
                    for(int x=3; x<6; x++)
                    {
                        if(sudoku[x][y].stala!=true)
                        {
                            if(sudoku[x][y].tab[i]==true)
                            {
                                g++;
                                ty=y;
                                tx=x;
                            }
                        }
                    }
                }
                if(g==1 && sudoku[tx][ty].stala!=true)
                {
                    sudoku[tx][ty].liczba=i+1;
                    sudoku[tx][ty].stala=true;
                    zmiana=true;
                    sprawdzanie(sudoku);
                    for(int n=0; n<9; n++)
                    {
                        sudoku[tx][ty].tab[n]=false;
                    }
                }   
            }
            z=0;
            g=0;
            tx=0;
            ty=0;
            for(int y=0; y<3; y++)
            {
                for(int x=6; x<9; x++)
                {
                    if(sudoku[x][y].liczba==i+1)z++;
                }
            }
            if(z==0)
            {
                for(int y=0; y<3; y++)
                {
                    for(int x=6; x<9; x++)
                    {
                        if(sudoku[x][y].stala!=true)
                        {
                            if(sudoku[x][y].tab[i]==true)
                            {
                                g++;
                                ty=y;
                                tx=x;
                            }
                        }
                    }
                }
                if(g==1 && sudoku[tx][ty].stala!=true)
                {
                    sudoku[tx][ty].liczba=i+1;
                    sudoku[tx][ty].stala=true;
                    zmiana=true;
                    sprawdzanie(sudoku);
                    for(int n=0; n<9; n++)
                    {
                        sudoku[tx][ty].tab[n]=false;
                    }
                }   
            }
            z=0;
            g=0;
            tx=0;
            ty=0;
            for(int y=3; y<6; y++)
            {
                for(int x=3; x<6; x++)
                {
                    if(sudoku[x][y].liczba==i+1)z++;
                }
            }
            if(z==0)
            {
                for(int y=3; y<6; y++)
                {
                    for(int x=3; x<6; x++)
                    {
                        if(sudoku[x][y].stala!=true)
                        {
                            if(sudoku[x][y].tab[i]==true)
                            {
                                g++;
                                ty=y;
                                tx=x;
                            }
                        }
                    }
                }
                if(g==1 && sudoku[tx][ty].stala!=true)
                {
                    sudoku[tx][ty].liczba=i+1;
                    sudoku[tx][ty].stala=true;
                    zmiana=true;
                    sprawdzanie(sudoku);
                    for(int n=0; n<9; n++)
                    {
                        sudoku[tx][ty].tab[n]=false;
                    }
                }   
            }
            z=0;
            g=0;
            tx=0;
            ty=0;
            for(int y=6; y<9; y++)
            {
                for(int x=6; x<9; x++)
                {
                    if(sudoku[x][y].liczba==i+1)z++;
                }
            }
            if(z==0)
            {
                for(int y=6; y<9; y++)
                {
                    for(int x=6; x<9; x++)
                    {
                        if(sudoku[x][y].stala!=true)
                        {
                            if(sudoku[x][y].tab[i]==true)
                            {
                                g++;
                                ty=y;
                                tx=x;
                            }
                        }
                    }
                }
                if(g==1 && sudoku[tx][ty].stala!=true)
                {
                    sudoku[tx][ty].liczba=i+1;
                    sudoku[tx][ty].stala=true;
                    zmiana=true;
                    sprawdzanie(sudoku);
                    for(int n=0; n<9; n++)
                    {
                        sudoku[tx][ty].tab[n]=false;
                    }
                }   
            }
            z=0;
            g=0;
            tx=0;
            ty=0;
            for(int y=3; y<6; y++)
            {
                for(int x=6; x<9; x++)
                {
                    if(sudoku[x][y].liczba==i+1)z++;
                }
            }
            if(z==0)
            {
                for(int y=3; y<6; y++)
                {
                    for(int x=6; x<9; x++)
                    {
                        if(sudoku[x][y].stala!=true)
                        {
                            if(sudoku[x][y].tab[i]==true)
                            {
                                g++;
                                ty=y;
                                tx=x;
                            }
                        }
                    }
                }
                if(g==1 && sudoku[tx][ty].stala!=true)
                {
                    sudoku[tx][ty].liczba=i+1;
                    sudoku[tx][ty].stala=true;
                    zmiana=true;
                    sprawdzanie(sudoku);
                    for(int n=0; n<9; n++)
                    {
                        sudoku[tx][ty].tab[n]=false;
                    }
                }   
            }
            z=0;
            g=0;
            tx=0;
            ty=0;
            for(int y=6; y<9; y++)
            {
                for(int x=3; x<6; x++)
                {
                    if(sudoku[x][y].liczba==i+1) z++;
                }
            }
            if(z==0)
            {
                for(int y=6; y<9; y++)
                {
                    for(int x=3; x<6; x++)
                    {
                        if(sudoku[x][y].stala!=true)
                        {
                            if(sudoku[x][y].tab[i]==true)
                            {
                                g++;
                                ty=y;
                                tx=x;
                            }
                        }
                    }
                }
                if(g==1 && sudoku[tx][ty].stala!=true)
                {
                    sudoku[tx][ty].liczba=i+1;
                    sudoku[tx][ty].stala=true;
                    zmiana=true;
                    sprawdzanie(sudoku);
                    for(int n=0; n<9; n++)
                    {
                        sudoku[tx][ty].tab[n]=false;
                    }
                }   
            }
        }
    }
}

void wpisywanie_niepewnych(komorka sudoku[9][9])
{
    bool zmiana1=true;
    bool skonczona1=false;
    int il_true, min_il_true=9, minx, miny;
    bool jest_mozliwa_zmiana=false;
    //while(skonczona1==false || zmiana1==true)
    //{
        //zmiana1=false;
    for(int x=0; x<9; x++)
    {
        for(int y=0; y<9; y++)
        {
            if(tymczasowa[x][y].stala!=true)
            {
                il_true=0;
                for(int i=0; i<9; i++)
                {
                    if(tymczasowa[x][y].tab[i]==true)il_true++;
                }
                if (il_true<=min_il_true)
                {
                    min_il_true=il_true;
                    minx=x;
                    miny=y;
                }
            }
        }
    }
    int i=0;
    while(skonczona1==false && i<9)
    {
        if(tymczasowa[minx][miny].tab[i]==true)
        {
            tymczasowa[minx][miny].liczba=i+1;
            tymczasowa[minx][miny].stala=true;
            zmiana1=true;
            for(int n=0; n<9; n++)
            {
                tymczasowa[minx][miny].tab[n]=false;
            }
            sprawdzanie(tymczasowa);
            wpisywanie_pewnych(tymczasowa);
            for(int x=0; x<9; x++)
            {
                for(int y=0; y<9; y++)
                {
                    if(tymczasowa[x][y].stala!=true)skonczona1=false; //sprawdzamy czy sudoku jest rozwiazane
                }
            }
            for(int x=0; x<9; x++)
            {
                for(int y=0; y<9; y++)
                {
                    for(int n=0; n<9; n++)
                    {
                        if(tymczasowa[x][y].tab[n]==true)jest_mozliwa_zmiana=true;
                    }
                }
            }
            if(skonczona1==false && jest_mozliwa_zmiana==true){wpisywanie_niepewnych(tymczasowa);}
        }
        i++;
    }

    if(skonczona1==true)
    {
        for(int x=0; x<9; x++)
        {
            for(int y=0; y<9; y++)
            {
                sudoku[x][y].stala=tymczasowa[x][y].stala;
                sudoku[x][y].liczba=tymczasowa[x][y].liczba;
                for (int i=0; i<9; i++)
                {
                    sudoku[x][y].tab[i]=tymczasowa[x][y].tab[i];
                }
            }
        }
    }
    for(int x=0; x<9; x++)
    {
        if(x%3==0)cout<<"-------------------------\n";  
        for(int y=0; y<9; y++)
        {
            if(y%3==0)cout<<"| ";
            cout<<tymczasowa[x][y].liczba<<" ";
        }
        cout<<"| ";
        cout<<endl; 
    }
    cout<<"-------------------------\n";
    cout<<endl<<endl;

}

int main()
{   
    int wybor;
    string nazwa;
    fstream plik;
    komorka sudoku[9][9];

    cout<<"Witaj w programie rozwiazujacym sudoku!\n \n ";
    cout<<"Wybierz poziom trudnosci sudoku, ktore ma zostac rozwiazane: \n ";
    cout<<"1-latwe\n 2-srednie\n 3-trudne\n 4-wlasne sudoku\n\n";
    cin>>wybor;

    switch(wybor)
    {
        case 1:
            plik.open("latwe.txt");
            break;
        case 2:
            plik.open("srednie.txt");
            break;
        case 3:
            plik.open("trudne.txt");
            break;
        case 4:
            cout<<"\npodaj nazwe dokumentu tekstowego, ktory zawiera sudoku\n";
            cin>>nazwa; 
            nazwa.append(".txt");
            plik.open(nazwa.c_str());
            break;
    }
    system("cls");
    /*****przypisanie wszystkim komórką tablicy poczatkowych wartosci false, co oznacza, że nie sa stalymi****/
    for(int x=0; x<9; x++)
    {
        for(int y=0; y<9; y++)
        {
            sudoku[x][y].stala=false;
        }
    }
   /**********************************************************************************************/
    if( plik.good() == true )
    {
        for(int x=0; x<9; x++)
        {
            for(int y=0; y<9; y++)
            {
                plik>>sudoku[x][y].liczba;
                if(sudoku[x][y].liczba>0) //jesli jest 0 to tak jakby nic nie bylo wpisane, komorka nie jest stala
                {
                    sudoku[x][y].stala=true;   //jesli jest podana liczba, to komorka jest stala, jej nie zmieniamy, wypelniajac sudoku
                    for(int i=0; i<9; i++)
                    {
                        sudoku[x][y].tab[i]=false; //dla stalych komorek zadna wiecej liczba nie moze tam byc umieszczona, wiec dla kazdego i tablica jest rowna false
                    }
                }
            }
        }
        plik.close();
    }
    else
    {
        cout<<"\n\nnie mozna otworzyc pliku!\n\n";
    }

    cout<<"Sudoku przed rozwiazaniem: "<<endl<<endl;
    wyswietlanie(sudoku);
    /*ustawiamy dla wszystkich cyfr, wstępne wartości true, czyli, że mogą się w danej komórce, która nie jest stałą, znajdywać*/
    for(int x=0; x<9; x++)
    {
            for(int y=0; y<9; y++)
            {
                if(sudoku[x][y].stala!=true)
                {
                    for(int i=0; i<9; i++)
                    {
                        sudoku[x][y].tab[i]=true;
                    }
                }
            }
    }
    /**********************************************************************************/
    bool skonczone=true;
    sprawdzanie(sudoku);
    wpisywanie_pewnych(sudoku); // uzupelniamy liczby ktore mozna wpisac uzywajac algorytmow rozwiazywania sudoku
    wyswietlanie(sudoku);

    komorka tymczasowa[9][9];
    /****************do tymczasowej tablicy kopiujemy tablicę sudoku*/
    for(int x=0; x<9; x++)
    {
        for(int y=0; y<9; y++)
        {
            tymczasowa[x][y].stala=sudoku[x][y].stala;
            tymczasowa[x][y].liczba=sudoku[x][y].liczba;
            for (int i=0; i<9; i++)
            {
                tymczasowa[x][y].tab[i]=sudoku[x][y].tab[i];
            }
        }
    }
    /****************************************************************/

    for(int x=0; x<9; x++)
    {
            for(int y=0; y<9; y++)
            {
                    if(sudoku[x][y].stala!=true)skonczone=false; //sprawdzamy czy sudoku jest rozwiazane
            }
    }
    if(skonczone==false)wpisywanie_niepewnych(tymczasowa); //jesli nie jest, to uzywamy metody probowania poprawnych rozwiazan z powrotami

    cout<<"Sudoku po rozwiazaniu: "<<endl<<endl;
    wyswietlanie(sudoku);

    system("pause");
    return 0;
}
1

Zacznij od skasowania tego kodu i napisania go od nowa. Tym razem przy założeniu że użytkownik podaje rozmiar planszy. Czy próbowałabyś napisać ten kod tak samo gdyby miał działać dla kwadratów 1000x10000 i dla liczb 1...1000000? Nie? No właśnie.
Twój kod ma ponad 800 linijek. Estymuje że zwykły brute-force (a to właśnie napisałaś...) dałoby się zamknąć w 50 linijkach, a w 100 linijkach byłby brute z jakimiś ulepszeniami.

0

Odpowiem na pierwszą część bo drugiej nawet nie zrozumiałem.
W definicji funkcji możesz użyć to co do niej przekazujesz ale pod taką nazwą jak w tej definicji podajesz a nie jak później ją wywołasz. Funkcja przecież nie wie, że Ty to kiedyś wywołasz z takim czymś.

0

Z tym, że on ma działać tylko dla takiej planszy, bo jest to moje zadanie na zajęcia i właśnie takich rozmiarów plansza ma być wpisywana.
Kod jest taki długi z dwóch względów, tylko tak umiałam napisać, i najpierw wpisuje te pewne liczby wg dwóch algorytmów, tak jak ja na kartce rozwiązuję sudoku i rozwiązują mi się dobrze te proste sudoku. Dopiero w momencie kiedy to nie działa, chce zastosować brute face lub jakiś algorytm z powrotami, tylko właśnie tego nie umiem zrobić i tu proszę o pomoc. I to jest tylko ta funkcja wpisywanie_niepewnych. Chciałam tam najpierw znaleźć takie pole, do którego mogę wpisać jak najmniej liczb (moje sudoku[x][y].tab[i], to jest tablica bool dla każdej wartości od 1 do 9 czy da się ją wpisać) i sprobówać wpisać tam wartość zobaczyć czy wyjdzie i jeśli nie to wyszukać to minimum jeszcze raz ale tak żeby było inne.

0
szweszwe napisał(a):

Odpowiem na pierwszą część bo drugiej nawet nie zrozumiałem.
W definicji funkcji możesz użyć to co do niej przekazujesz ale pod taką nazwą jak w tej definicji podajesz a nie jak później ją wywołasz. Funkcja przecież nie wie, że Ty to kiedyś wywołasz z takim czymś.

dziękuję, to już zauważyłam:)

0

Na twoim miejscu spojrzałabym sobie do Google, zapytania typu: c++ sudoku solver, c sudoku solver, sudoku solver algorithm i napisała ten kod od nowa.

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