YasSS - Yet Another (Simple|Stupid) Sudoku Solver

Auf meiner allgemeinen Projektseite habe ich YasSS schon vorgestellt. Hier folgt eine detaillierte Beschreibung.

Was ist YasSS?

YasSS ist ein C++-Programm für die Kommandozeile, das gegebene Sudoku löst.

Die eigentliche Funktionalität ist in einer Klasse gekapselt, sodass es einfach sein sollte, eine andere Benutzeroberfläche dazuzuprogrammieren.

Dokumentation

Hier gibt es die Manpage zu YasSS online und die Manpage zu yasss-curses.

Funktionsweise

YasSS speichert das Sudokufeld in einem Zweidimensionalen Array. Für jede Position wird in einem Bitfeld (also einem Array von bools) gespeichert, welche Zahlen dort noch hinein können.

Zum eigentlichen Solver gibt es weiter unten Details mit Quellcode.

Header-Datei der Klasse sudoku

Der Quellcode ist im Original auf englisch kommentiert. Hier ersetze ich sie durch deutsche Kommentare, um die Lesbarkeit zu erhöhen.

Eine Bemerkung vorweg: Die Daten werden so gespeichert, dass eine "0" einer leeren Zelle entspricht.

#ifndef _MORITZ_FIELD_
#define _MORITZ_FIELD_
#include <iostream>

// Ein Sudokufeld (implementiert als zweidimensionales 
// Array fester Größe) mit Solver.
class sudoku {
	public:
		sudoku();

		// Erzeuge ein Sudoku aus einem zweidimensionalen
		// Array
		sudoku(char init_data[9][9]);
		// dito, nur mit int statt char
		sudoku(int init_data[9][9]);
		
		// Erzeuge ein Sudoku aus einem eindimensionalen
		// Array
		sudoku(char* init_data);

		// Lesbare Ausgabe auf dem Bildschirm in der Form
		// 1 2 3 4 5 ...
		// 3 5 7 8 9 ...		
		void pretty_print(std::ostream &handle);

		// primitive Ausgabe: Alle Zahlen hintereinander gereiht.
		void print(std::ostream &handle);

		// sets item (x, y) to val
		// assumes that it is doesn't lead to an intermediate
		// confilict with sudoku rules
		// which is equivalent to saying it requires 
		// allowed_set(val, x, y) to be true

		// Setze Zelle (x, y) auf den Wert val.
		// setzt voraus, dass 
		// allowed_set(val, x, y) == true gilt
		void set_item(char val, int x, int y);

		// Hole den Wert an der Stelle (x, y).
		// Null bedeutet, dass der Wert nicht gesetzt ist.
		int get_item(int x, int y);
		
		// Ist es erlaubt, an der Stelle (x, y) den Wert val
		// einzutragen? es werden nur direkte Kollisionen
		// überprüft
		bool allowed_set(char val, int x, int y);

		// Löse das Sudoku. Liefert true bei Erfolg
		bool solve();
		
		// Ist das Sudoku komplett gelöst?
		bool is_solved();

		// Liefert true, wenn es keine Möglichkeit mehr gibt, 
		// eine Zahl zu setzen, ohne eine Regel zu verletzen
		bool is_stuck();
	protected:

		// Das eigentliche Feld
		char data[9][9];

		// allowed[x][y][i] ist false, wenn es eine direkte
		// Regelverletzung wäre, an (x, y) den Wert i zu setzen.
		bool allowed[9][9][9]; 

		// löse das Sudoku ohne Backtracking 
		// (soweit möglich)
		bool simple_solve();

		// zwei einfache Lösungsstratiegen, Details siehe 
		// unten
		bool simple_solve1();
		bool simple_solve2();

		// Löse das Sudoku mit Backtracking. True bei Erfolg.
		bool backtrack();


		// setze alle Werte auf Null
		void null_init();

		// Das wird nur zu Debuggingzwecken manchmal gebraucht...
		int recursion_depth;
		void set_recursion_depth(int rd) {recursion_depth = rd;};
};

#endif /* _MORITZ_FIELD */
      

Implementierung

Jetzt kommt das eigentlich interessante, die Implementierung. Die langweiligen Funktionen möchte ich hier weglassen. Wer den ganzen Code lesen will, findet ihn im source-Archiv

.

Wir fangen einfach an...

bool sudoku::allowed_set(char val, int x, int y){
	return allowed[x][y][val - 1];
}

Das Einzige, was man hier beachten muss ist, dass es für den Wert Null kein Feld in allowed gibt, man also eins abziehen muss.

Einfügen einer Zahl

Jetzt der Code für das Setzen einer Zahl und die Aktualisierung der Abhängigkeiten:

void sudoku::set_item(char val, int x, int y){
	// ein paar Checks, die beim Debuggen
	// hilfreich sind:
	assert(allowed_set(val, x, y));
	assert(data[x][y] == 0);
	assert(val >= 1);
	assert(val <= 9);

	// Wert setzen
	data[x][y] = val;

	// Jetzt müssen alle Abhängigkeiten 
	// aktualisiert werden ...

	// ... in den Zeilen und Spalten
	for(int i = 0; i < 9; i++){
		allowed[x][i][val - 1] = false;
		allowed[i][y][val - 1] = false;
	}

	// im dazugehörigen 3x3-Block
	int x_orig = 3 * (int) (x/3);
	int y_orig = 3 * (int) (y/3);
	for (int i = x_orig; i < x_orig + 3; i++){
		for (int j = y_orig; j < y_orig + 3; j++){
			allowed[i][j][val - 1] = false;
		}
	}

	// und jetzt an der Stelle selbst, in der die
	// Zahl eingefügt wurde.
	for (int i = 0; i < 9; i++)
		allowed[x][y][i] = false;
	allowed[x][y][val - 1] = true;
}

Einfaches lösen 1

So, jetzt gehts endlich richtig zur Sache. Hier kommt der erste Code, der tatsächlich Sudokus löst.

Dazu wird jede Zelle danach abgegrast, ob dort nur noch eine Zahl gesetzt werden darf:

bool sudoku::simple_solve1(){
	bool res = false;
	// grase alle Zellen ab:
	for (int x = 0; x < 9; x++){
		for (int y = 0; y < 9; y++){
			// uns interessieren nur Zellen, 
			// die noch nichts enthalten
			if ((int) data[x][y] == 0){
				int c = 0;
				int i0 = 0;
				// Zähle, wie viele Zahlen
				// dort erlaubt sind
				for (int i = 0; i < 9; i++){
					if (allowed[x][y][i]){
						i0 = i;
						c++;
					}
				}
				// ... und wenn es nur eine ist, setze 
				// sie
				if (c == 1){
					set_item(i0 + 1, x, y);
					res = true;

				} // for i

			} // if (data != 0)
		} // for y
	} // for x
	return res;
}

Das sind zwar viele ineinander verschachtelte Zeilen, aber eigentlich ist es nicht kompliziert.

Einfaches lösen 2

Der nächste Teil des Solvers funktioniert anders: Für jede Zelle, Spalte und jeden 3x3-Block wird gesucht, ob eine Zahl nur an einer Stelle möglich ist.

Das hört sich auf Anhieb nicht anders an als der letzte Teil, aber wenn man sich das ein bisschen durch den Kopf gehen lässt, kommt man bald darauf, dass es eine andere Art des Ausschlussprinzips ist.

bool sudoku::simple_solve2(){
	bool res = false;
	// Durchsuche alle Spalten
	for (int x = 0; x < 9; x++){
		// Durchsuche Spalte x
		// in vcount[i] wird gespeichert, wie oft die
		// Zahl i-1 vorkommen darf
		int vcount[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
		for (int y = 0; y < 9; y++){
			if (data[x][y] == 0) {
				for (int i = 0; i < 9; i++){
					if (allowed[x][y][i]){
						vcount[i]++;
					}
				}
			} else {
				// Die Zahl data[x][y] kommt schon 
				// in dieser Spalte vor, wir setzen
				// den Wert einfach sehr hoch 
				// (sprich: größer als 1)
				vcount[data[x][y] - 1] = 10;
			} // if
		} // for y

		// jetzt prüfe für alle Zahlen...
		for (int i = 0; i < 9; i++){
			// ... ob sie nur einmal vorkommen kann.
			if (vcount[i] == 1){
				// Jetzt müssen wir nur noch suchen,
				// wo das ist
				for (int k = 0; k < 9; k++){
					if (allowed[x][k][i]){
						// und sie dann setzen
						set_item(i+1, x, k);
						res = true;
					}
				}
			}
		} // for i
	} // for x


	// und jetzt genau das gleiche für die Zeilen
	for (int y = 0; y < 9; y++){
		int hcount[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
		for (int x = 0; x < 9; x++){
			if (data[x][y] == 0) {
				for (int i = 0; i < 9; i++){
					if (allowed[x][y][i]){
						hcount[i]++;
					}
				}
			} else {
				// any numer < 1 will do...
				hcount[data[x][y] - 1] = 10;
			} // if
		} // for y
		for (int i = 0; i < 9; i++){
			if (hcount[i] == 1){
				for (int k = 0; k < 9; k++){
					if (allowed[k][y][i]){
						set_item(i+1, k, y);
						res = true;
					}
				}
			}
		} // for i
	} // for x


	// Für die 3x3-Blück genau das gleiche.
	// Da man aber zwei Schleifen braucht, um einen 3x3-Block zu
	// durchlaufen, schaut es kompliziert aus.
	for (int xb = 0; xb < 9; xb += 3){
		for (int yb = 0; yb < 9; yb += 3){
			int rcount[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
			for (int i = 0; i < 9; i++){
				int x = xb + i % 3;
				int y = yb + (int) i/3;
				if (data[x][y] == 0){
					for (int k = 0; k < 9; k++){
						if (allowed[x][y][k]){
							rcount[k] ++;
						}
					} // for k
				} else {
					rcount[data[x][y] - 1] = 10;
				} // if data == 0
			} // for i
			for (int i = 0; i < 9; i++){
				if (rcount[i] == 1){
					for (int k = 0; k < 9; k++){
						int x = xb + k % 3;
						int y = yb + (int) k/3;
						if (allowed[x][y][i]){
							set_item(i+1, x, y);
						}
					}
					res = true;
				} // if rcount[i] == 1
			} // for i
		} // for yb
	} // for xb

	return res;
} // function

Der letzte Teil sah recht böse aus - aber eigentlich nur, weil es keine schönere, einfachere Möglichkeit gibt, die 3x3-Block zu durchqueren.

Backtracking

Jetzt kommen wir zu dem Teil, der alles lösen kann was lösbar ist, aber nicht unbedingt effizient ist: Backtracking.

bool sudoku::backtrack(){
	if (is_stuck()){
		return false;
	}

	// Wenn man den Kommentar vor diesem Befehl heraus nimmt kann
	// man mitverfolgen, wie das Backtracking ungefähr 
	// verläuft
//	cerr << "Recursion depth: " << recursion_depth 
//		<< "\n";


	// Suche eine beliebige Stelle, an der noch keine Zahl steht.
	// Der Einfachheit halber suche ich die erste:
	for (int x = 0; x < 9; x++){
		for (int y = 0; y < 9; y++){
			if (data[x][y] == 0){
				// eine Stelle gefunden.

				// Jetzt suche nach Zahlen, die dort hinein-
				// passen könnten.
				for (int i = 0; i < 9; i++){
					if (allowed[x][y][i]){
						// erzeuge eine Kopie des
						// Feldes:
						sudoku tmp = *this;

						// setze die Zahl
						tmp.set_item(i+1, x, y);
						tmp.set_recursion_depth(
								recursion_depth + 1);
						// Löse das neu ent-
						// standende Sudoku
						if (tmp.solve()){
							// und wenn es die
							// Lösung ist,
							// übernehme sie
							*this = tmp;
							return true;
						}
					}
				}
				return false;
			}//  if data == 0
		} // for y
	} // for x
	return false;
}

Das Backtracking ist auch nicht kompliziert. Da es vielleicht innerhalb der Schleifen nicht so gut herauskommt, hier nochmal der Algorithmus in Worten:

Alles zusammenbringen

Jetzt fehlt nur noch eine kleine Funktion, die die verschiedenen Solver in der richtigen Reihenfolge aufruft.

Dabei kann man als Faustregel davon ausgehen, dass Backtracking deutlich langsamer ist als die anderen beiden Strategien. Also wird Backtracking nur dann benutzt, wenn man anders nicht mehr weiter kommt.

bool sudoku::solve(){
	simple_solve();
	if (is_stuck()){
		return false;
	}
	if (is_solved()){
		return true;
	} else {
		return backtrack();
	}
}

bool sudoku::simple_solve(){
	bool res = false;
	bool flag = true;
	while (flag){
		flag = simple_solve1();
		flag = simple_solve2() || flag;
		if (flag){
			res = true;
		}
	} // while
	return res;
} // function

Sudokus erzeugen

Sudokus zu erzeugen ist keine exakte Wissenschaft. Eine einfache Möglichkeit, Sudokus zu erzeugen, bietet folgender Algorithmus:

  1. Wähle eine zufällige Position im Feld, und eine zufällige Zahl.
  2. Wenn es nicht zu einer direkten Verletzung der Sudokuregeln führt, die gewählte Zahl an der gewählten Stelle einzufügen, füge sie ein.
  3. Wiederhole Schritte 1 und 2, bis k=26 Zahlen gesetzt sind.
  4. Überprüfe, ob das entstandene Sudoku eindeutig lösbar ist. Wenn es gar keine Lösung gibt, lösche alle Zahlen und fange mit Schritt 1 an.
  5. Wenn es mehrere Lösungen gibt, mache weiter mit Schritt 1, 2 und dann mit Schritt 4.
  6. Wenn es genau eine Lösung gibt, hat man sein Ziel erreicht. Ende.

Dieser Algorithmus fürt zum Ziel, wenn man genug Geduld hat. Im Durchschnitt muss man bei k=26 etwa 70 Versuche wegschmeissen, bis man Erfolg hat, manchmal sind es auch über 300.

Trotzdem braucht die Erzeugung eines Sudokus im Durchschnitt auf meinem Laptop weniger als 27 Millisekunden, gemittelt über 1000 Erzeugungen.

Die Wahl von k beeinflusst die Geschwindigkeit erheblich. Für kleine k wird der Algorithmus sehr langsam, weil man sehr oft prüfen muss, ob ein Sudoku eindeutig ist, wofür man Backtracking braucht, was bei wenigen vorgegebenen Zahlen sehr lange dauern kann. Da ein Sudoku vermutlich mindestens 17 vorgegebene Zahlen braucht, ist eine Wahl von k<17 nicht sinnvoll.

Wählt man k groß, also z.B. k>30, ist der Algorithmus ebenfalls langsam, weil die Wahrscheinlichkeit, dass man ein unlösbares Sudoku erzeugt, sehr groß ist.

Zeit zur Erzeugung eines Sudokus in
		Abhängigkeit des Parameters k. In halblogarithmischer
		Darstellung sieht die Kurve wie eine Parabel aus, hat bei k=28
		ein Minimum mit t=0.026s, bei k=20 und k=35 ist die Zeit im
		Bereich einiger Sekunden
Zeit zum generieren eines Sudokus in halblogarithmischer Darstellung.

Optimal scheint eine Wahl von etwa k=26 zu sein. Damit ist der Algorithmus schnell genug, um in sinvoller Zeit Ergebnisse zu liefern, und klein genug, um noch schwere Sudokus zu erzeugen.

Es ist auch nicht sinnvoll, ein kleines k zu wählen in der Hoffnung, schwerere Sudokus zu erzeugen, denn die entstehden Sudokus haben nur sehr selten weniger als 25 Zahlen vorgegeben.

Ein mit diesem Algorithmus erzeugtes Sudoku hat typischerweise 27 bis 30 Zahlen vorgegeben.

Geschwindigkeit

YasSS löst auf meinem Notebook (mit Pentium M 1.5 GHz) ein minimales Sudoku in durchschnittlich 1.1 Millisekunden, gemittelt über 30.000 Sudokus.

Dabei wird allerdings nur die erste Lösung gesucht, falls mehrere vorhanden sein sollten, werden diese ignoriert.

Download

Hier gibt es die aktuelle Version von YasSS

Noch eine Kleinigkeit hinterher...

Wenn man YasSS mit einem leeren Sudoku aufruft, kommt das folgende Rätsel heraus: