3. Problem mit Sudoku-Solver

Problem mit Sudoku-Solver

  • 3

    hi!
    Ich hab mal versucht ein Programm zu schreiben das ein fertiges Sudoku-Rätsel erstellt.
    Folgender Code ist dabei rausgekommen :

    #include <cstdlib>
#include <iostream>

using namespace std;

int grid[8][8];

int backtrace(int y, int x, int number)
{
	int rowcount	= 0;
    int columncount = 0;
	int e			= 0;

	for(int j=0;j<20;j++){
		if((j<18)&&(j>8)){
			if(grid[x][rowcount]==number){
					e=1;
					return e;
					break;
			}
			rowcount++;
		}
		if(j<9){
			if(grid[columncount][y]==number){
					e=1;
					return e;
					break;
			}
			columncount++;
		}
	}
	return e;
}

int main(int argc, char *argv[])
{
int x		= 0;
int y		= 0;
int number;

for(int i=0;i<81;i++){

if(x==9){
	x=0;
	y++;
}

	int r=1;
	while(r==1){
		number =  1 + ( rand() % ( 9 - 1 + 1 ) );
		r = backtrace(y,x,number);
	}

	grid[x][y] = number;

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

    x		= 0;
    y		= 0;

    for(int p=0;p<81;p++){
    if(x==9){
	x=0;
	y++;
	cout<<endl;
    }

    cout<<grid;

    if(x<10){
	x++;
    }
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}

    Das Problem ist, dass das Programm ewig arbeitet und eine Prozessorauslastung von nahezu 100% produziert.
    Ich hatte ja schon erwartet das es eine zeit brauchen würde zum berechnen, aber so lange nun auch nicht.
    Nun weiß ich nicht ob der Code ansich richtig ist, oder ich irgendwas wichtiges vergessen habe und dadurch eine Endlosschleife entsteht.

    0
  • C
    Mod

    mit dem algorithmus habe ich mich nicht beschäftigt.

    3TageBart schrieb:

    int grid[8][8];

    iirc hat ein Sudoku 9x9 felder.

    0
  • 3

    zählt 0 denn nicht ?

    0

  • beim initialisieren alle arrayfelder n angeben, beim zählen dann von 0 bis n-1

    0
  • 3

    ich hab das script nochmal überarbeitet und alles in Funktionen gepackt.
    Es funktioniert jetzt soweit das innerhalb der 3x3 Boxen jede zahl nur einmal vorkommt, aber in den spalten und zeilen kommen die Zahlen noch mehrfach vor.

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

using namespace std;

int n = 9;
int grid[9][9];
int box = (int)sqrt(n);

bool checkHorizontal(int position, int value){
    for(int i=0;i<n;i++)
    {
            if(grid[i][position]==value)
                return false;

           return true;
    }
}

bool checkVertical(int position, int value){
    for(int i=0;i<n;i++)
    {
            if(grid[position][i]==value)
                return false;

           return true;
    }
}

bool checkBox(int i,int j, int value){
  int i_start = (int)(i/box) * box;
  int j_start = (int)(j/box) * box;

  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){
     int error = 0;
     if(!checkHorizontal(x, value))
       error=1;

     if(!checkVertical(y, value))
      error=1;

     if(!checkBox(x, y, value))
      error=1;

     if(error==0)
           return true;

  return false;
}

//-----------------------------------------------------------------------------
bool solve(){

int x=0;
int y=0;

for(int i=0;i<81;i++){
        cout<<"Zahl "<<i+1<<endl;

        if(x==9){
	    x=0;
	    y++;
        }
     cout<<x<<"x"<<y<<endl;
     for(int a=1;a<=n;a++){
     cout<<"Try : "<<a<<endl;
          if(backtrace(x,y,a))
          {
           grid[x][y] = a;
           goto ende;
          }
     }
ende:
	if(x<10){
    x++;
	}
}
}

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

    for(int p=0;p<81;p++){
    if(x==9){
	x=0;
	y++;
	cout<<endl;
    }
    cout<<grid[x][y];

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

    cout<<endl;
}

//-----------------------------------------------------------------------------
int main(int argc, char *argv[])
{
    solve();
    print();
        system("PAUSE");
        return EXIT_SUCCESS;
}
    0
  • J
     

    #include <cstdlib>
#include <iostream>
#include <cmath>
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 = (int)(i/box) * box;
    int j_start = (int)(j/box) * box;

    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 solve()
{

    int x=0;
    int y=0;

    for (int i=0; i < n*n; ++i)
    {
        if (x==9)
        {
            x=0;
            y++;
        }
        for (int a=1;a<=n;a++)
        {
            if (backtrace(x,y,a))
            {
                grid[x][y] = a;
                break; // break ist besser als goto
            }
        }
        if (x<10)
        {
            x++;
        }
    }
}

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

    for (int p=0;p<81;p++)
    {
        if (x==9)
        {
            x=0;
            y++;
            cout<<endl;
        }
        cout<<grid[x][y] << " ";

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

    cout<<endl;
}

int main(int argc, char *argv[])
{
    memset(grid, -1, sizeof(grid)); // Alle Werte des Arrays auf -1 setzen, sonst kann da
                                    // alles mögliche drinn stehen.

    solve();
    print();
}

    Allerdings kommt dabei kein Soduku raus, da die Methode, die Zahlen einfach zu verteilen, nicht funktioniert.

    mfg.

    0
  • 3

    hmma also du scheinst da im Code irgendwas durcheinander gebracht zu haben, da kommt nicht vie brauchbares bei raus.

    also bei meinem Code kommt immer dasselbe muster bei raus, das ist ja eientlich nicht verwunderlich aber normalerweise dürfte jede zahl nur einmal pro Zeile / Spalte vorkommen 😞

    123234234
    456156156
    789789789
    314314314
    256256256
    789789789
    314314314
    256256256
    789789789

    Warum sollte diese Methode denn nicht funktionieren ?

    0
  • J

    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.

    0
  • J

    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.

    0
  • 3

    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;
               }
            }
        }
    }
}
    0

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

    0
  • V

    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.

    0
  • O

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

    0
  • 3

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

    0
  • ?

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

    0
  • V

    Explizit in einen float, double oder long double casten:

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

    Greetz

    0
  • ?

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

    0
  • C

    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()".

    0
  • ?

    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.

    0
  • ?

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

    0
  • V

    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

    0
Anmelden zum Antworten