3. Sudoku Löser

Sudoku Löser

  • ?

    Hallo,
    Ich arbeite gerade an einen Sudoku Löser, jedoch funktioniert meine Zahlensuche nicht immer.
    Manche Zahlen sucht das Programm richtig, manche jedoch nicht.
    Daher meine Frage was ist falsch?
    Könnt ihr bitte einen Blick darauf werfen 😋

    Danke im Voraus!

    Hier ist der Quellcode(Einlesen und Werte suchen):

    #include <iostream>                                                                             
#include <cstdlib>
#include <windows.h>

using namespace std;

void gotoxy(int x, int y);
void einlesen(int iFeld[9][9]);
void ausgabe(int iFeld[9][9]);
void kordinaten(int iFeld[9][9], int & x, int & y);
void horizontal(int iFeld[9][9], int x, int y, int & hwert);
void vertical(int iFeld[9][9], int x, int y, int hwert, int & vwert);
void bkordinaten(int x, int y, int & xa, int & xe, int & ya, int & ye);
void block(int iFeld[9][9], int x, int y, int & bwert, int hwert, int vwert, int xa, int xe, int ya, int ye);
void erhoehen(int iFeld[9][9], int x, int y, int & hwert, int & vwert, int & bwert, int xa, int xe, int ya, int ye);

int main()
{
cout<< endl << "Sudoku Loeser" << endl;                                                         // Überschrift
cout<< endl << "copyright Christian Klemm & Gerhard Stoeckl 2012" << endl << endl << endl;      // Überschrift

int hwert = 1;
int vwert = 1;
int bwert = 1;
int x = 0;
int y = 0;
int xa = 0;
int ya = 0;
int xe = 0;
int ye = 0;
int iFeld[9][9] =   {                                                         // Deklaration des 2 dimensionalen Array
                    5,0,1,0,7,2,0,0,0,
                    6,0,0,1,9,5,2,0,0,
                    2,9,8,0,0,0,0,6,0,
                    8,1,0,0,6,0,0,0,3,
                    4,0,0,8,0,3,0,0,1,
                    7,2,0,0,2,0,0,0,6,
                    0,6,0,0,0,0,2,8,0,
                    0,0,0,4,1,9,0,0,5,
                    0,0,0,0,8,0,0,7,9,
                  };
/*
{
                    6,3,2,7,8,1,9,4,5,
                    0,8,7,5,9,6,2,1,3,
                    5,1,9,2,4,3,8,7,6,
                    8,6,4,3,5,2,7,9,1,
                    7,5,1,9,6,8,3,2,4,
                    2,9,3,1,7,4,6,5,8,
                    9,4,5,6,3,7,1,8,2,
                    1,7,6,8,2,5,4,3,9,
                    3,2,8,4,1,9,5,6,7
                  };

*/

ausgabe(iFeld);
cout<< endl << endl;

kordinaten(iFeld,x,y);

horizontal(iFeld,x,y,hwert);
vertical(iFeld,x,y,hwert,vwert);
bkordinaten(x,y,xa,xe,ya,xe);

cout<< endl <<"xa=" <<xa;
cout<< endl <<"xe=" <<xe;
cout<< endl <<"ya=" <<xa;
cout<< endl <<"ye=" <<xe;

block(iFeld,x,y,bwert,hwert,vwert,xa,xe,ya,ye);

cout<< endl <<"x="<< x << endl <<"y="<< y << endl <<"hwert="<< hwert << endl <<"vwert="<< vwert<< endl <<"bwert="<< bwert<< endl;

erhoehen(iFeld,x,y,hwert,vwert,bwert,xa,xe,ya,ye);

cout<< endl <<"hwert="<< hwert << endl <<"vwert="<< vwert<< endl <<"bwert="<< bwert;

if(hwert == vwert && hwert == bwert && vwert == bwert)
{
cout<< endl << endl << "Alle 3 werte gleich" << endl << endl;
}else
{
cout<< endl << endl << "Die 3 Werte sind unterschiedlich" << endl << endl;
}

ausgabe(iFeld);

return(0);
}

void gotoxy(int x,int y)                                                                        // Funktion gotoxy
{
   COORD cur={x,y};
   SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),cur);
}

void einlesen(int iFeld[9][9])
{
cout<< "Bitte geben sie das zu loesende Sudoku ein: " << endl << endl;                          // Einlesen des Sudokus

for(int z = 0; z < 9; z++)
{
cout<< endl;
    for(int s = 0; s < 9; s++)
    {
    cin>> iFeld[z][s];
    gotoxy(s+1,z+5);
    }
}
}

void ausgabe(int iFeld[9][9])                                                                   // Funktion ausgabe
{
for(int z = 0; z < 9; z++)
{
cout<< endl;
    for(int s = 0; s < 9; s++)
    {
    cout<< " " << iFeld[z][s];
    }
}
}

void kordinaten(int iFeld[9][9], int & x, int & y)                                              // Ermittelt das erste Leere Feld im Sudoku
{
for(int z = 0; z < 9; z++)
{
    for(int s = 0; s < 9; s++)
    {
        if(iFeld[z][s] == 0)
        {
        y = z;
        x = s;
        break;
        }
    }

    if(y != 0)
    {
    break;
    }
}
}

void horizontal(int iFeld[9][9], int x, int y, int & hwert)                                     // funktion horizontal
{
for(int i = 0; i < 9; i++)
{
    if(iFeld[y][i] == hwert)
    {
    hwert++;
    //horizontal(iFeld,x,y,hwert);
    i = 0;
    }
}
}

void vertical(int iFeld[9][9], int x, int y, int hwert, int & vwert)                            // funktion vertical
{
for(int i = 0; i < 9; i++)
{
    if(iFeld[i][x] == vwert || iFeld[i][0] == hwert)
    {
    vwert++;
    //vertical(iFeld,x,y,hwert,vwert);
    i = 0;
    }
}
}

void bkordinaten(int x, int y, int & xa, int & xe, int & ya, int & ye)
{
if(x >= 0 && x <= 2)
{
xa = 0;
xe = 3;
cout<< endl << "1. Block in X";
}else   if(x > 2 && x <= 5)
        {
        xa = 3;
        xe = 6;
        cout<< endl << "2. Block in X";
        }else   {
                xa = 6;
                xe = 9;
                cout<< endl << "3. Block in X";
                }

if(y >= 0 && y <= 2)
{
ya = 0;
ye = 3;
cout<< endl << "1. Block in Y";
}else   if(y > 2 && y <= 5)
        {
        ya = 3;
        ye = 6;
        cout<< endl << "2. Block in Y";
        }else   {
                ya = 6;
                ye = 9;
                cout<< endl << "3. Block in Y";
                }
}

void block(int iFeld[9][9], int x, int y, int & bwert, int hwert, int vwert, int xa, int xe, int ya, int ye)
{
for(int s = 0; s < 3; s++)      // sobald xa und xe bzw. ya und ye programm funktioniert nicht mehr!
{
    for(int z = 0; z < 3; z++)
    {
        if(iFeld[z][s] == bwert || iFeld[z][s] == vwert || iFeld[z][s] == hwert)
        {
        bwert++;
        //block(iFeld,x,y,bwert,hwert,vwert,xa,xe,ya,ye);
        s = 0;
        z = 0;
        }
    }
}
}

void erhoehen(int iFeld[9][9], int x, int y, int & hwert, int & vwert, int & bwert, int xa, int xe, int ya, int ye)
{
cout<< "erhöhen";
int hvbwerte[3];
int gleiche[3] = {0,0,0};
int g = 0;
int sum = 0;

hvbwerte[0] = hwert;                                // Speichert hwert, vwert und bwert in ein feld
hvbwerte[1] = vwert;
hvbwerte[2] = bwert;

do //schleife erhöht so lange bis alle gleich sind
{

for(int j = 0; j < 3; j++)                          // sucht größte Zahl im Feld
{
    if (hvbwerte[j] > g)
    {
    g = hvbwerte[j];
    }
}

cout<< endl << endl;

for(int u = 0; u < 3; u++)                          // sucht die zu erhöhenden Zahlen
{
    if (hvbwerte[u] < g)
    {
    gleiche[u]++;
    }
}

for(int u = 0; u < 3; u++)                          // summe des feldes
{
sum = sum + gleiche[u];
}

for(int g = 0; g < 3; g++)
{
    if(gleiche[g] == 1)
    {
        if(g == 0)
        {
        cout<< "Horizontal wird erhoeht" << endl;
        hwert++;
        horizontal(iFeld,x,y,hwert);
        }

        if(g == 1)
        {
        vwert++;
        vertical(iFeld,x,y,hwert,vwert);

        cout<< "Vertical wird erhoeht" << endl;
        }

        if(g = 2)
        {
        cout<< "Block wird erhoeht" << endl;
        bwert++;
        bkordinaten(x,y,xa,xe,ya,xe);
        }
    }
}
}while(sum == 0);
}
    0
  • K

    du glaubst doch nicht ernsthaft, dass sich jemand 300 Zeilen (schlecht formatierten) Quellcode durchliest, nur um deine Debugarbeit zu erledigen oder?

    greetz KN4CK3R

    0
  • ?

    😞 ich bin noch nicht so erfahren im programmieren.
    Naja ich finde meinen Fehler aber nicht.
    Könntet ihr bitte kurz einen Blick darauf werfen?

    0
  • C

    Ohne mir das jetzt wirklich durchgelesen zu haben, geb ich dir trotzdem mal ein Stichwort nach dem du suchen kannst: Backtracking.

    0
  • ?

    Ich weiß Backtracking hab ich mir schon angesehen.
    Aber da ich noch nicht so erfahren bin wollte ich es zuerst diesen Lösungsweg versuchen.

    0
  • Mod

    KN4CK3R schrieb:

    du glaubst doch nicht ernsthaft, dass sich jemand 300 Zeilen (schlecht formatierten) Quellcode durchliest, nur um deine Debugarbeit zu erledigen oder?

    Meinem Compiler macht das nichts aus:

    test.cc: In function ‘int main()’:
test.cc:41:19: warning: missing braces around initializer for ‘int [9]’ [-Wmissing-braces]
test.cc:41:19: warning: missing braces around initializer for ‘int [9]’ [-Wmissing-braces]
test.cc:41:19: warning: missing braces around initializer for ‘int [9]’ [-Wmissing-braces]
test.cc:41:19: warning: missing braces around initializer for ‘int [9]’ [-Wmissing-braces]
test.cc:41:19: warning: missing braces around initializer for ‘int [9]’ [-Wmissing-braces]
test.cc:41:19: warning: missing braces around initializer for ‘int [9]’ [-Wmissing-braces]
test.cc:41:19: warning: missing braces around initializer for ‘int [9]’ [-Wmissing-braces]
test.cc:41:19: warning: missing braces around initializer for ‘int [9]’ [-Wmissing-braces]
test.cc:41:19: warning: missing braces around initializer for ‘int [9]’ [-Wmissing-braces]
test.cc: In function ‘void gotoxy(int, int)’:
test.cc:101:4: error: ‘COORD’ was not declared in this scope
test.cc:101:10: error: expected ‘;’ before ‘cur’
test.cc:102:42: error: ‘STD_OUTPUT_HANDLE’ was not declared in this scope
test.cc:102:59: error: ‘GetStdHandle’ was not declared in this scope
test.cc:102:61: error: ‘cur’ was not declared in this scope
test.cc:102:64: error: ‘SetConsoleCursorPosition’ was not declared in this scope
test.cc: At global scope:
test.cc:99:6: warning: unused parameter ‘x’ [-Wunused-parameter]
test.cc:99:6: warning: unused parameter ‘y’ [-Wunused-parameter]
test.cc:157:6: warning: unused parameter ‘x’ [-Wunused-parameter]
test.cc:172:6: warning: unused parameter ‘y’ [-Wunused-parameter]
test.cc:223:6: warning: unused parameter ‘x’ [-Wunused-parameter]
test.cc:223:6: warning: unused parameter ‘y’ [-Wunused-parameter]
test.cc:223:6: warning: unused parameter ‘xa’ [-Wunused-parameter]
test.cc:223:6: warning: unused parameter ‘xe’ [-Wunused-parameter]
test.cc:223:6: warning: unused parameter ‘ya’ [-Wunused-parameter]
test.cc:223:6: warning: unused parameter ‘ye’ [-Wunused-parameter]
test.cc: In function ‘void erhoehen(int (*)[9], int, int, int&, int&, int&, int, int, int, int)’:
test.cc:301:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
test.cc: At global scope:
test.cc:242:6: warning: unused parameter ‘ye’ [-Wunused-parameter]

    Lass dich nicht von den unbekannten Windowsfunktionen stören, ich habe eben kein Windows. Aber die anderen Warnungen sind deuten teilweise auf ganz schön dicke Hauer hin. Ganz besonders Zeile 301. Die unbenutzten Variablen sind auch ein schlechtes Zeichen.

    0
  • ?

    Die ungenützten Variablen werden zur Zeit (für Testläufe) nicht verwendet.
    Das mit den Windows Funktionen lässt sich beheben.
    Was wäre denn ein möglicher Fehler, wenn zum Beispiel die Zahlensuche mit einer 2 Funktioniert. Wenn ich für Testzwecke die Zahl jedoch verändere, zum Beispiel 3 läuft das Programm nicht mehr fertig durch oder bricht ab.

    0
  • Mod

    christianklemm schrieb:

    Was wäre denn ein möglicher Fehler, wenn zum Beispiel die Zahlensuche mit einer 2 Funktioniert. Wenn ich für Testzwecke die Zahl jedoch verändere, zum Beispiel 3 läuft das Programm nicht mehr fertig durch oder bricht ab.

    Grundlagen!
    = Zuweisung
    == Vergleich

    0
  • ?

    Um das Problem etwas einzugrenzen.
    Das ist die Funktion zur Überprüfung der Zeile:

    void horizontal(int iFeld[9][9], int x, int y, int & hwert)                                     
{ 
for(int i = 0; i < 9; i++) 
{ 
    if(iFeld[y][i] == hwert) 
    { 
    hwert++; 
    //horizontal(iFeld,x,y,hwert); 
    i = 0; 
    } 
} 
}

    und das die Funktion für die dazugehörige Spalte:

    void vertical(int iFeld[9][9], int x, int y, int hwert, int & vwert)                            
{
for(int i = 0; i < 9; i++)
{
    if(iFeld[i][x] == vwert || iFeld[i][x] == hwert)
    {
    vwert++;
    //vertical(iFeld,x,y,hwert,vwert);
    i = 0;
    }
}
}

    Hier dürfte das Problem nicht liegen aber wie ist es möglich das es mit einer 2 funktioniert und mit einer 3 nicht?

    0
  • ?

    Vielleicht kommst du auch auf die Idee, einen STL-Container wie std::array zu benutzen? Der wirt eine Exception (brauchst nicht zu wissen was das ist, es gibt aber bei Fehlern was auf die Konsole aus was du (oder zumindest wir) deuten kannst), wenn du z.B. einen Index größer als erlaubt angibst.
    Und dann kannst du auch ein typedef benutzen, um die ganze (wiederkehrende Tipparbeit) zu sparen.

    typedef std::array< std::array < size_t /* Nummer für das Feld, 0 heißt Leer */, 9 >, 9 > sudokuArray_t;

sudokuArray_t field;
    0
  • ?

    Das mit typedef ist eine gute Idee.
    Da ich in c/c++ nur die Grundlagen kenne weiß ich jetzt nicht genau was du mit STL-Container meinst.

    0
  • ?

    christianklemm schrieb:

    Das mit typedef ist eine gute Idee.
    Da ich in c/c++ nur die Grundlagen kenne weiß ich jetzt nicht genau was du mit STL-Container meinst.

    STL = Standard Template Library = Standard - Template (Schablonen) - Bibliothek

    Ist schon ein merkwürdiges Wort, nicht? Template? Um es kurz zu machen (tutorials gibt es genug): Du machst dir ein eigenes Array.

    std::vector<int> vec;

    Hier haben wir einen std::vector instanziiert. std::vector ist eine Template-Klasse, die intern ein Array des übergebenen Typs anlegt (in diesem Fall vom Typ int).
    Das schöne daran ist, dass es dieses Array für uns verwaltet und einigen Ärger erspart. Es gibt neben std::vector natürlich noch andere Container wie std::list, std::deque, std::queue und noch viele (wichtige) andere...
    Verschiedene Funktionen erleichtern uns sofort das Leben:

    vec.size();//Größe des vectors. Hier 0, weil er noch Leer ist (wir haben nichts hineingetan)
vec.push_back(5);//Wir legen eine 5 an die hinterste Position und vergrößern dabei natürlich den Vector um 1 (size() ist jetzt 1).
vec.push_front(1);//size() ist jetzt 2. Einziger Unterschied zu push_back(): 1 wird jetzt (wie der Name suggeriert) ganz nach vorne getan.
vec.pop_back();//Und pop_front, der bruder: Beide entfernen ein Objekt aus dem vector, pop_back() hinten und pop_front - na, rate mal. size() = 1.

vec[0] = 4; //Der wert, der vorher 1 war, ist jetzt 4. Das Element an Position 0 also.
vec.at(0) = 5;//dito, nur prüft diese Funktion, ob der übergebene Index (hier 0) größer als erlaubt ist (bei z.B. 100 würde er eine Exception werfen).

vec.clear();//Löscht alle Elemente im vector. size() = 0.

    Es gibt noch viel mehr Funktionen, und Konstruktoren und noch Algorithmen (für alle Container). Das ist alles furchtbar interessant, schau mal hier.

    Das ist BTW ein sehr großes Thema, denn du wirst feststellen dass auch iteratoren, templates und so weiter eine große Rolle in der STL Spielen. Klar dauert das ein wenig, nur ist die STL so ungefähr das selbstverständlichste für jeden (C++)-Programmierer. Also lohnt es sich definitiv mal vorbeizuschauen (was du sowieso irgendwann tun musst).

    Zurück zu deinem Beispiel. Ein std::array ist etwas anderes als std::vector, da es nicht ver-größerbarer oder -kleinerbarer ist. Seine Größe bleibt gleich, deswegen übergeben wir sie als template-parameter übergeben. Der muss nicht umbedingt ein unbekannter Typ sein, es kann auch ein integraler sein (integral = int, short, char, long, und evt. long long):

    std::array<int, 8> ar;

    Hier können wir auf jedes dieser 8 Elemente zugreifen. Das ist für dein Sudoku-Feld nützlich, da seine Größe ja nicht änderbar ist. Oder? Eine Referenz zu std::array findest du im Netz.

    0
  • ?

    ok danke für den ausführlichen Beitrag.
    Werde mich mal damit beschäftigen.

    Eine Frage hat von euch schon jemand einmal einen Sudokulöser programmiert?

    0
  • ?

    christianklemm schrieb:

    Eine Frage hat von euch schon jemand einmal einen Sudokulöser programmiert?

    Ja, schon längst. Mit GUI und allem drum und dran.
    Das System das ich benutzt hab, ist Bruteforce.

    0
  • ?

    Asoo. Hast du dir meinen Quellcode durchgelesen? Eventuell auf Denkfehler/Programmierfehler gestoßen?

    0
  • ?

    christianklemm schrieb:

    Asoo. Hast du dir meinen Quellcode durchgelesen? Eventuell auf Denkfehler/Programmierfehler gestoßen?

    Ich werde deinen Code nicht lesen. Stattdessen ein professioneller Tipp: refactoring. Mach lieber gleich alles nochmal, und diesmal schön formatieren, gut planen (besonders den Algorithmus) und konzentriert arbeiten. Dann dauerts nur halb solang.

    0
  • C

    Ja, ganz klassisch in C. 🙂

    0
  • ?

    Asoo. Ok. Wie würde denn ein Gut formatierter Quellcode ausschauen? 😃
    Ich hatte mir gedacht mein Quellcode ist schön 😋

    0
  • ?

    @Cybertec Kann ich mir deinen Quellcode ansehen? 😋

    0
  • ?

    christianklemm schrieb:

    Asoo. Ok. Wie würde denn ein Gut formatierter Quellcode ausschauen? 😃
    Ich hatte mir gedacht mein Quellcode ist schön 😋

    Oh nein... 😮 😃

    Zum formatieren habe ich mal ein kleines Tutorial geschrieben, such mal danach (kann es bei bestem Willen nicht finden). Sonst schau mal wie andere "formattieren"...

    0
Anmelden zum Antworten