Problem mit Sudoku-Solver

joomoo

3TageBart schrieb:

Warum sollte diese Methode denn nicht funktionieren ?

Deswegen: Er geht ja alles der Reihe nach durch: Also wird der Anfang so aussehen:

123 456 789

nun geht er in die zweite zeile und dort wird er folgendes hinsetzen:

123 456 789
456 789

Was kommt nun aber in die letzte Spalte? Da gibt es keine Lösung. Deswegen gibt meine Version des Codes auch so etwas "komisches" aus. Trotzdem ist die Version richtig, da sie genau das tut was du machen willst, nur das damit halt niemals ein gültiges Sodoku herrauskommen kann.

mfg.

joomoo

So klappt es:

#include <iostream>
#include <cmath> // cmath ist neuer als math.h
using namespace std;

const int n = 9; // n sollte nicht verändert werden
const int box = static_cast<int>(sqrt(n)); // static_cast ist besser
int grid[9][9];

bool checkHorizontal(int position, int value)
{
    for (int i=0;i<n;i++)
    {
        if (grid[i][position]==value)
        {
            return false;
        }
    }
    return true; // Raus aus der Schleife!
}

bool checkVertical(int position, int value)
{
    for (int i=0;i<n;i++)
    {
        if (grid[position][i]==value)
            return false;
    }
    return true; // Raus aus der Schleife!
}

bool checkBox(int i,int j, int value)
{
    int i_start = (i/box) * box; // int cast nicht notwendig, da beim Teilen
    int j_start = (j/box) * box; // von ints auch ints rauskommen

    for (int a=i_start; a<i_start+box; a++)
        for (int b=j_start; b<j_start+box; b++)
            if (grid[a][b] == value)
                return false;

    return true;
}

bool backtrace(int x, int y, int value)
{
    if (checkHorizontal(y, value) && // y muss übergeben werden da x durchgegangen wird
        checkVertical(x, value) && // hier muss x hin
        checkBox(x, y, value))
    {
        return true;
    }
    return false;
}

bool print()
{
    int x        = 0;
    int y        = 0;

    for (int p=0;p<81;p++)
    {
        if (x==9)
        {
            x=0;
            y++;
            cout<<"\n";
        }
        if(grid[x][y] == -1)
        {
            std::cout << "  ";
        }
        else
        {
            cout<<grid[x][y] << " ";
        }

        if (x<10)
        {
            x++;
        }
    }

    cout<<flush;
}

void solve() // Brauch nicht bool zurückgeben
{

    int x=0;
    int y=0;

    for (int i=0; i < n*n; ++i)
    {
        for (int a=1;a<=n;a++)
        {
            int x = i % n; // So lassen sich x und y aus i errechnen
            int y = i / n;
            if (backtrace(x, y, a))
            {
                grid[x][y] = a;
                break; // break ist besser als goto
            }
            while(a == n) // Solange keine Lösung gefunden wurde
            {
                --i; // Einen Schritt zurück gehen
                grid[x][y] = -1;
                a = grid[i % n][i / n]; // a auf den vorherigen Wert setzen
                // wenn dieser jetzt auch schon 9 war, wird der Wert davor aktualisiert
            }
        }
    }
}

int main() // main ohne Parameter gibt's auch
{
    memset(grid, -1, sizeof(grid)); // Alle Werte des Arrays auf -1 setzen, sonst kann da
                                    // alles mögliche drinn stehen.

    solve();
    print();
}

Jedes mal wenn es nicht möglich war einen Wert zu setzen, wird so lange zurück gegangen und die Werte davor werden neu ausprobiert. Die Methode wird auch bei Wikipedia beschrieben: http://de.wikipedia.org/wiki/Sudoku (Backtracking-Methode)

mfg.

3TageBart

wie würde das ganze aussehen wenn man anstatt der Reihenfolge den Zufall spielen läst ?
Ich hab ein wenig rumprobiert hab aber nix gescheites hinbekommen, das Programm hängt sich immer auf.

void solve() // Brauch nicht bool zurückgeben
{

    int x=0;
    int y=0;

    for (int i=0; i < n*n; ++i)
    {
        for (int a=1;a<=n;a++)
        {
            int x = i % n;
            int y = i / n;

            int number;
            int check=0;
            int count=0;

            while(!check){
               count++;
               number = 1 + ( rand() % ( 9 - 1 + 1 ));
               cout<<number<<endl;
               check = backtrace(x,y,number);
               grid[x][y] = number;
               if(count>10){
                --i; // Einen Schritt zurück gehen
                grid[x][y] = -1;
                number = grid[i % n][i / n];
                count=0;
               }
            }
        }
    }
}

elise

geh mit dem debugger durch die stelle, an der er sich aufhängt.

volkard

3TageBart schrieb:

Ich hab ein wenig rumprobiert hab aber nix gescheites hinbekommen, das Programm hängt sich immer auf.

hängt es sich echt auf, oder ist es nur ein wenig langsam und würde 30 tage brauchen? ich würde da, um sicher zu gehen, zum beispiel einmal pro sekunde ne ausgane des gesamten feldes machen.

OkaR

kann mir jemand verraten, warum bei mir der fehler
.\main.cpp(9) : error C2668: 'sqrt' : ambiguous call to overloaded function
kommt?

3TageBart

das Programm läuft ein paar sekunden und dann kommt : "Es trat ein Problem auf, das Programm muss beendet werden blablabla^^"

Also bei Joomoo's letztem Code kommt bei mir der Fehler:

.\Sudoku.cpp(6) : error C2668: 'sqrt': Mehrdeutiger Aufruf einer überladenen Funktion
C:\Programme\Microsoft Visual Studio 8\VC\include\math.h(581): kann 'long double sqrt(long double)' sein
C:\Programme\Microsoft Visual Studio 8\VC\include\math.h(533): oder "float sqrt(float)"
C:\Programme\Microsoft Visual Studio 8\VC\include\math.h(128): oder "double sqrt(double)"
bei Anpassung der Argumentliste '(const int)'

was kann ich dagegen machen? hab noch nich wirklich ahnung davon....

Vellas

Explizit in einen float, double oder long double casten:

const int box = static_cast<int>(sqrt(static_cast<double>(n)));

Greetz

Ok. thx das funktioniert jetzt. Allerdings kommt jetzt noch ein Fehler in Zeile 90:

...\sudoku.cpp(90) : error C4716: 'print': Muss einen Wert zurückgeben

da ich in dem ganzen Programm noch nicht wirklich durchsehe, weiß ich jetzt hier auch nicht was er von mir will..

CStoll

Ich glaube, du solltest erstmal die Grundlagen von C(++) verstehen, dann wird's einfacher

"print()" ist definiert als bool-Funktion, also mußt du ihr auch ein return spendieren. Alternativ kannst du es ändern in "void print()".

bin ja grad dabei. hab dieses semester mein studium angefangen und hab leider überhaupt keine vorkentnisse in C(++) und muss ein Projekt in Strukturiertes Programmieren bearbeiten. Da hab ich mir den Sudoku-Löser/Entwerfer ausgesucht. Und da such ich jetzt schonmal ein Programm was funktioniert um zu sehen wie das abläuft.

Also mit "void print()" hats nich geklappt. ich hab jetzt einfach nen false zurückgegeben keine ahnung ob das richtig ist, aber das programm läuft auf jeden fall erstmal (auch mit "return true").

Und weiß jemand von euch ob es auch nen mehr grafischen Sudoku-Löser irgentwo 4 free gibt? Also nich nur Blackbox sondern mit Benutzeroberfläche und Buttons und so...

Vellas

Hi!

Wenn du mit Quellcode meinst, wirst du den Code erst recht nicht verstehen, wenn du nicht mal die Grundlagen in C++ richtig drauf hast. Aber hab mal bei google einfach "sudoku solver" eingegeben und gleich als erstes einen Online-Solver gefunden:
http://www.sudokusolver.co.uk/

Ich würde dir aber erstmal empfehlen mit leichteren Anwendungen anzufangen und C++ so weit lernen das du einigermaßen sicher darin bist bevor du dir Anwendungen mit grafischer Benutzeroberfläche antust.

Des Weiteren sollte es reichen aus bool vor dem print ein void zu machen:

void print() {
// ...
}

Ansonsten haste irgendwas falsch gemacht.

Greetz