Sudoku in C mit Backtracking Methode

rohamis · 05.05.2011

Hallo zusammen,

ich muss in C einen Algorithmus schreiben, der ein beliebiges Sudoku mit der Backtracking Methode (rekursiv) löst.
Allerdings habe ich schon 3 Funktionen vorgelegt bekommen, die ich auch benutzen soll(!!!).

Ich weiss genau was Backtracking ist, ich weiss auch wie das in Sudoku funktioniert, aber ich komme nicht so ganz dahinter, wie ich das in C realisieren soll.

Mein Problem besteht nämlich darin, woher das Programm wiessen kann, zu welchen Feld es zurück gehen soll. Ich habe in einem Array die Felder markiert, die auch bearbeitet wurden sind, aber ich weiss nicht wie ich es dem Kompiler "sagen" soll, dass er da nochmals überprüfen soll, welche Zahl als nächstes Möglich ist.

Die Funktionen die ich habe sind: (b = Sudoku Brett)
1) suche_freie_stelle(i,j,b)
2) ist_belegt (ob Feld frei ist oder nicht)
3) ist_erlaubt (on in das leere Feld die Zahl rein kommen kann oder nicht).

Damit soll ich halt den Algorithmus schreiben.

Hier das, was ich bis jetzt gemacht habe. Ihr werdet auch schnell erkennen, dass ich es bis dahin nur soweit geschaft habe, dass er das Soduko soweit löst, bis der ein Feld sieht wo es keine Zahl rein passt. Dann ist schluss

Das soll auch nicht heissen, dass es bisher richtig ist was ich habe. Wenn jemand mir sagen würde "mache es anders" dann habe ich auch kein Problem mit. Wichtig ist, ich muss diese 3 Funktionen benutzen in dem Algo.

Code:

int loese_sudoku(int i, int j, int b[BS][BS] )
{
  int zahl_erlaubt = 0;
  char markiert[BS][BS];
  int m,n;
  for(m=0;m<BS;m++)
    for(n=0;n<BS;n++)
      markiert[m][n] = 'f';

  suche_naechste_freie_stelle(&i,&j,b);            /* mit zeigern, damit die änderungen auch hier sichtbar sind */
  if(i>=BS)
  {
    printf("Sudoku ist fertig!\n");
    return 1;
  }
  else
  {
    int z = 1;
    while(z<=10)
    {
      if(z==10)
      {
          if(markiert[i][j-1] == 'f');     /* HIER WEISS ICH NICHT WAS ICH MACHEN SOLL */
                                                /* WIE ICH ZURÜCK GEHEN SOLL BZW. WIE ER WISSEN WOLL */
                                                /* ZU WELCHEM FELD ER WIEDER ZURÜCK GEHEN MUSS!!! */
      }
      else
      {
    if(ist_erlaubt(z,i,j,b))
    {
      b[i][j] = z;
      zahl_erlaubt = 1;
      markiert[i][j] = 'm';
      loese_sudoku(i,j,b);
    }
      }
      z++;
    }
  }
}

TrµMAn · 05.05.2011

Nur mal kurz, ob ich das Prinzip vom Backtracking richtig verstanden hab:

Ich versuche eine Lösung (die 1. Beste) zu finden, sollte ich einmal nicht weiter kommen, mache ich den letzten Schritt rückgängig und versuche es anders.

Meine eigentliche Überlegung wäre ja die hier gewesen, ist aber ohne Backtracing und ohne Rekursion:

Man müsste sich eine Ziffer vornehmen (z = 1)
und ausprobieren, ob ich alle 9 setzen kann (für jedes freie Feld, überprüfe ob z hinein passt und ob nur z hinein passt)
danach müsste ich meine Ziffer um 1 erhöhen (z++)
komme ich dann irgendwann bei 10 an (while (z < 10) )
setze ich meine Ziffer wieder auf 1 ( z = 1 )
und ist das Sudoku noch nicht gelöst fange ich wieder an, meine Ziffer in alle freien Felder zu klöppeln ( while (!is_solved(sudoku))

Also im Grunde wie das 8-Damen Problem, nur mit Ziffern.

rohamis · 05.05.2011

Danke dir für die Antwort.

Ja ok löse ich (zumindest am Anfang) auch ein Sudoku, allerdings habe ich das als Aufgabe mittels Backtracking zu machen, deswegen.

Backtracking:
- Geh zum nächsten freien Feld
- Probiere von 1-9
- wenn passt
Ziffer setzen und weiter gehen
wenn nicht
auf das vorherige Feld was du bearbeitet hast zurück gehen, und die nächst mögliche Ziffer reinsetzen, und wenn da auch nichts geht, solange zurück gehen bis etwas halt geht.

Irgendwie muss ich in meinem Code die schon bearbeitete Felder manuel zurück setzen also
b[j] = 0;
Das würde dann auch die Markierung sein so zu sagen. Das habe ich vor ca. 5 min. begriffen.
Das mit der Markierung an dem oben stehendem Code ist also erstmals falsch.
Weiss aber immer noch nicht wie

rohamis · 05.05.2011

Hab es gerade geschaft.
Man muss in dem Algo selbst prüfen, dass man nicht übers Feld hinausläuft, und man muss die bearbeiteten Felder, die aber keine Zahl (für den Moment) akzeptieren auf Null setzen. Das ist das auch praktisch die "Markierung".

TrµMAn · 05.05.2011

So ich habe jetzt eine Lösung gefunden, rekursiv und mit Backtracking.

Du musst bedenken, dass durch die Rekursion, immernoch eine instanz der Methode auf dem Stack liegt, in die du zurück springen musst.

Ich löse es aktuell so:

Ist das aktuelle Feld belegt, überprüfe ich ob es sich um das letzte Feld handelt. Ist das so, kann ich "true" zurück geben, dann ist das Sudoku gelöst.
Sonst suche ich das nächste Feld und rufe meine Lösefunktion mit dem neuen Feld auf.
Sollte das Feld nicht belegt sein, probiere ich alle Zahlen aus:
Sobald eine zahl passt, setze ich diese ein.
(In meinem Fall, gebe ich hier schon "true" zurück, wenn ich gerade das letzte Feld gefüllt habe)
Danach mache ich eine Kopie von meinen Koordinaten (Damit ich, wenn der Funktionsaufruf zurück kommt, weiter auf dieser einen Koordinate lösen kann (Backtracking) ich merke mir praktisch wo ich war, bevor ich die nächste Stelle suche

), lasse die Koordinaten des nächsten Feldes dort hinein schreiben und versuche dort weiter zu lösen.
Hier überprüfe ich wieder, ob beim Lösungsversuch "true" zurückgegeben wurde, und gebe danach auch true zurück.

Den Code möchte ich (noch) nicht veröffentlichen, du sollst dabei ja schließlich etwas lernen

Außerdem sieht der Code grausig aus

ganz schlechtes Vorbild...

Schön das du es selbst geschafft hast, aber:

rohamis schrieb:
und man muss die bearbeiteten Felder, die aber keine Zahl (für den Moment) akzeptieren auf Null setzen.

in dem Fall musst du einfach zum vorherigen Funktionsaufruf zurück springen und dort weiter suchen.

Achso und da du jetzt gelöst hast, hier noch mein Code (ja ich weiß, graaaaaauuuuuusam)

Code:

#include <iostream>

using namespace std;

// Überprüft ob das übergebene Feld schon überschrieben wurde (Standardwert = 0)
bool ist_belegt(int zahl)
{
	return zahl != 0;
}

// Liefer Koordinaten des nächsten Feldes.
void naechstes_feld(int& i, int& j)
{
	if(i == 8)
	{
		i = 0;
		j++;
	}
	else
	{
		i++;
	}
}

// Überprüft ob die Zahl in dem aktuellen Feld erlaubt ist.
bool ist_erlaubt(int z, int i, int j, int sudoku[9][9])
{
	// Alle Zeilen durchgehen
	for(int l = 0; l < 9; l++)
		if(sudoku[l][j] == z)
			return false;

	// Alle Spalten durchgehen
	for(int l = 0; l < 9; l++)
		if(sudoku[i][l] == z)
			return false;

	// Herausfinden, in welchem der 9 kleinen Felder wir uns befinden
	int check_square_i = i / 3;
	check_square_i *= 3; // macht aus 0, 1 und 2 den Wert 0 (1. Feld) und aus 3, 4, 5 den Wert 3 (2. Feld) und aus 6, 7, 8 den Wert 6 (3. Feld)
	int check_square_j = j / 3;
	check_square_j *= 3; 

	// Überprüfen, ob in dem kleinen Feld, die Ziffer schon vorhanden ist.
	for(int l = check_square_i; l < check_square_i + 3; l++)
	{
		for(int k = check_square_j; k < check_square_j + 3; k++)
		{
			if(sudoku[l][k] == z)
				return false;
		}
	}

	// Ist die Ziffer gültig, wird true zurück gegeben.
	return true;
}

// Löst das Sudoku rekursiv
bool loese_sudoku(int i, int j, int sudoku[9][9])
{
	// Ist das aktuelle Feld belegt, springe zum nächsten und versuche es dort weiter.
	if(ist_belegt(sudoku[i][j]))
	{
		if(i == 8 && j == 8)
			return true; // Wenn das letzte Feld erreicht wurde
		naechstes_feld(i, j);
		return loese_sudoku(i, j, sudoku);
	}

	// Alle Zahlen durchprobieren
	for(int z = 1; z < 10; z++)
	{
		// Ist die Zahl erlaubt, 
		if(ist_erlaubt(z, i, j, sudoku))
		{
			// Zahl einsetzen, für die nächsten Versuche
			sudoku[i][j] = z;
			// Sollte es schon die letzte Zahl gewesen sein, hier aufhören.
			if(i == 8 && j == 8)
				return true;
			// sonst kopieen von i und j anlegen, das nächste Feld für i und j suchen und es damit versuchen.
			int l = i, k = j;
			naechstes_feld(l, k);
			if(loese_sudoku(l, k, sudoku))
				return true;
		}
	}
	return false;
}

void print_sudoku(int sudoku[9][9])
{
	for(int i = 0; i < 9; i++)
	{
		for(int j = 0; j < 9; j++)
		{
			cout << sudoku[i][j];
			if(j % 3 == 2 && j != 8)
				cout << "|";
		}
		cout << "\n";
		if(i % 3 == 2 && i != 8)
			cout << "---|---|---\n";
	}
}

void main()
{
	int sudoku[9][9] =
	{
		{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
		{ 4, 0, 6, 7, 8, 9, 1, 2, 3 },
		{ 7, 8, 9, 0, 0, 0, 4, 5, 6 },
		{ 3, 1, 2, 6, 4, 5, 9, 7, 8 },
		{ 6, 4, 5, 9, 7, 8, 3, 1, 2 },
		{ 9, 7, 8, 3, 1, 2, 6, 0, 5 },
		{ 2, 3, 1, 5, 6, 4, 8, 9, 7 },
		{ 5, 6, 4, 8, 9, 7, 2, 3, 0 },
		{ 0, 0, 0, 0, 0, 0, 0, 0, 4 },
	};
	print_sudoku(sudoku);
	cout << "\n\n";

	if(loese_sudoku(0, 0, sudoku))
	{
		cout << "Sudoku geloest!\n\n";
		print_sudoku(sudoku);
	}
	else
		cout << "Sudoku nicht loesbar!";
}

TrµMAn · 06.05.2011

Eine kleine Änderung muss da bei mir noch rein, sonst kommt es vor, dass er es nicht lösen kann, obwohl es lösbar ist.

Code:

#include <iostream>

using namespace std;

// Überprüft ob das übergebene Feld schon überschrieben wurde (Standardwert = 0)
bool ist_belegt(int zahl)
{
	return zahl != 0;
}

// Liefer Koordinaten des nächsten Feldes.
void naechstes_feld(int& i, int& j)
{
	if(i == 8)
	{
		i = 0;
		j++;
	}
	else
	{
		i++;
	}
}

// Überprüft ob die Zahl in dem aktuellen Feld erlaubt ist.
bool ist_erlaubt(int z, int i, int j, int sudoku[9][9])
{
	// Alle Zeilen durchgehen
	for(int l = 0; l < 9; l++)
		if(sudoku[l][j] == z)
			return false;

	// Alle Spalten durchgehen
	for(int l = 0; l < 9; l++)
		if(sudoku[i][l] == z)
			return false;

	// Herausfinden, in welchem der 9 kleinen Felder wir uns befinden
	int check_square_i = i / 3;
	check_square_i *= 3; // macht aus 0, 1 und 2 den Wert 0 (1. Feld) und aus 3, 4, 5 den Wert 3 (2. Feld) und aus 6, 7, 8 den Wert 6 (3. Feld)
	int check_square_j = j / 3;
	check_square_j *= 3; 

	// Überprüfen, ob in dem kleinen Feld, die Ziffer schon vorhanden ist.
	for(int l = check_square_i; l < check_square_i + 3; l++)
	{
		for(int k = check_square_j; k < check_square_j + 3; k++)
		{
			if(sudoku[l][k] == z)
				return false;
		}
	}

	// Ist die Ziffer gültig, wird true zurück gegeben.
	return true;
}

// Löst das Sudoku rekursiv
bool loese_sudoku(int i, int j, int sudoku[9][9])
{
	// Ist das aktuelle Feld belegt, springe zum nächsten und versuche es dort weiter.
	if(ist_belegt(sudoku[i][j]))
	{
		if(i == 8 && j == 8)
			return true; // Wenn das letzte Feld erreicht wurde
		naechstes_feld(i, j);
		return loese_sudoku(i, j, sudoku);
	}

	// Alle Zahlen durchprobieren
	for(int z = 1; z < 10; z++)
	{
		// Ist die Zahl erlaubt, 
		if(ist_erlaubt(z, i, j, sudoku))
		{
			// Zahl einsetzen, für die nächsten Versuche
			sudoku[i][j] = z;
			// Sollte es schon die letzte Zahl gewesen sein, hier aufhören.
			if(i == 8 && j == 8)
				return true;
			// sonst kopieen von i und j anlegen, das nächste Feld für i und j suchen und es damit versuchen.
			int l = i, k = j;
			naechstes_feld(l, k);
			if(loese_sudoku(l, k, sudoku))
				return true;
		}
	}
	sudoku[i][j] = 0; // Bei Fehlschlag das Feld wieder leeren!
	return false;
}

void print_sudoku(int sudoku[9][9])
{
	for(int i = 0; i < 9; i++)
	{
		for(int j = 0; j < 9; j++)
		{
			cout << sudoku[i][j];
			if(j % 3 == 2 && j != 8)
				cout << "|";
		}
		cout << "\n";
		if(i % 3 == 2 && i != 8)
			cout << "---|---|---\n";
	}
}

void main()
{
	int sudoku[9][9] =
	{
		{ 0, 0, 0, 0, 0, 8, 0, 3, 0 },
		{ 0, 3, 0, 5, 0, 0, 4, 7, 1 },
		{ 2, 0, 0, 1, 0, 0, 6, 9, 0 },
		{ 5, 0, 0, 0, 0, 2, 1, 0, 0 },
		{ 1, 2, 4, 0, 0, 0, 9, 6, 3 },
		{ 0, 0, 6, 4, 0, 0, 0, 0, 2 },
		{ 0, 8, 9, 0, 0, 5, 0, 0, 7 },
		{ 3, 5, 2, 0, 0, 9, 0, 4, 0 },
		{ 0, 1, 0, 3, 0, 0, 0, 0, 0 },
	};

	print_sudoku(sudoku);
	cout << "\n\n";

	if(loese_sudoku(0, 0, sudoku))
	{
		cout << "Sudoku geloest!\n\n";
		print_sudoku(sudoku);
	}
	else
		cout << "Sudoku nicht loesbar!";
}

rohamis · 30.11.2011

Ich danke dir sehr für die Hilfe. Auch wenn es so ziemlich lange gedauert hat von mir zu antworten.
Mod kann Thema schliessen.

Sudoku in C mit Backtracking Methode

rohamis

TrµMAn

rohamis

rohamis

TrµMAn

TrµMAn

rohamis

Sudoku in C mit Backtracking Methode

ANGEBOTE & SPONSOREN

Neueste Beiträge

Statistik des Forums