Algorithmus für Sudoku

[spidermobile]

Hallo zusammen,

ich würde gerne zu Übungszwecken ein Sudoku bauen. Da ich nie die Mathe-Leistungsstufe :wink: besucht habe, werde ich bestimmt am Algorithmus für das Setzen der Zahlen scheitern. Bin bei google leider nicht fündig geworden. Kennt jemand einen Link für den Quelltext dieses Algorithmus (also nicht das ganze Spiel, das möchte ich ja selber proggen).

Wäre schön! Danke!

 

[McLane]

Also ein Spezieller Algorithmus der das Sudokuproblem löst ist mir nicht bekannt.

Jedoch habe ich das Problem vor einiger Zeit recht effizient (10 ms Berechnungszeit) mit dem "Backtracking-Algorithmus" gelöst. Vielleicht hilft der dir auch.

Einfach mal googlen und du findest unendlich viele Links (Sogar bei Wikipedia). Leider kann ich dir keine speziellen Linkempfehlungen geben

 

[spidermobile]

Hi McLane,

ja das bei WiKi hab ich schon gesehen. Danke! So wie ich das lesen, ist wohl der "Backtracking-Algorithmus" der Schlüssel zum Erfolg. Hab mir überhaupt keine Ahnung, was das ist. Na dann werde ich jetzt mal goggle bemühen!

Hab mal gesucht. Es gibt wohl auch noch die "Brute-Force Methode". Aber das aind alles Bömische Dörfer für mich. Hier im Forum habe ich auch leider nichts passendes gefunden.

Gibt es da gar keine Lösungsansätze im Quellcode?

 

[lin]

Naja Brute-Force ist halt einfach die Methode, dass du alle Möglichkeiten durchprobierst, ist aber nicht sonderlich elegant.

Gibt es da gar keine Lösungsansätze im Quellcode?

Hm, ich denke mal da muss man nicht sonderlich viel von Mathematik verstehen, nur n'bisserl was überlegen. Kannst ja zuerst mal nen Algorithmus schreiben, der ein einfaches Sudoku lösen kann.

 

[spidermobile]

Hallo Lin,

hört sich leichter an, als es für mich ist. Bin eigentlich kein Entwickler sondern lerne nur nebenher etwas Java. Hab auch schon kleinere Projekte gemacht, aber diese Form na ich will mal sagen von "KI" ist mir ganz ganz fremd. Dehlab wollte ich mal zur Anregung einen Codeschnipsel mit dem ich mich dan auseinander setzen kann!

Ich erwarte keine fertige Lösung!

 

[McLane]

Ich dachte eigentlich immer der Backtracking Algorithmus ist auch eine Brute-Force Methode, weil er sich zur Not alle Lösungswege anschaut, wenn er vorher keinen passenden gefunden hat.
Hierzu habe in meinen Sudoku eine kleine Optimierung eingebaut: Ich prüfe direkt nach dem Einfügen einer neuen Zahl, ob sie da stehen darf oder ob schon ein Widerspruch vorhanden ist. Ohne dieser "Zwischenabfrage" rechnet mein Programm ein Vielfaches länger (nämlich mehrere Minuten statt 10 Millisekunden)

Ich gebe dir mal hier meine Hauptmethode zur Lösung des Sudokus. Ich weiss zwar nicht, ob das sehr verständlich ist, weil ich es damals nur reingehackt habe, aber es ist besser als nichts :wink:

	private static boolean solveSudoku(
			int[][] problem, int nextX, int nextY) {
		
		boolean result = false;
		int x = nextX;
		int y = nextY;
		
		//Find next free field
		while (y < 9) {
			while (x < 9) {
				if (problem[y][x] != 0) {
					x++;
				}
				else {
					break;
				}				
			}
			if (x >= 9) {
				x = 0;
				y++;				
			}
			else if (problem[y][x] == 0) {
				break;
			}
		}
		
		//If Square is filled, check if it is correctly filled
		if ((nextY == 9) || (y == 9)) {
			return isLegalResult(problem);
		}

		for (int i = 1; i <= free[y].getSize(); i++) {
			int item = free[y].removeNth(i);
			
			problem[y][x] = item;
			
			if ((verticalsOK(x, problem)) && (squareOK(x, y, problem))) {
				if (x == 8) {
					result = solveSudoku(problem, 0, y + 1);								
				}
				else {
					result = solveSudoku(problem, x + 1, y);
				}
				if (result) {
					return true;
				}
				else {
					problem[y][x] = 0;
					free[y].add(item);
				}
			}
			else {
				problem[y][x] = 0;
				free[y].add(item);
			}
		}
		return false;
	}

Weiter ist noch zu erwähnen, dass die Variable free eine Sortierte Liste ist (musste ich selber implementieren), in der die Zahlen stehen, die noch in Zeile i eingefügt werden müssen.

Falls du willst schicke ich dir auch gerne mein ganzes Sudoku-Programm. Dann musst du mir nur deine eMail-Adresse per PN mitteilen

 

[McLane]

Da unerwarteterweise ziemlich viele Leute sich für meine Sudokulösung interessieren habe ich sie vorerst online gestellt.

Hier könnt ihr das Programm herunterladen:

www.informatik.uni-kiel.de/~dik/sudoku/Sudoku.zip

Eventuell werde ich es nach 2-3 Wochen löschen müssen, weil ich den Webspace für ein Praktikum bei uns an der Uni brauche, aber bis dahin könnt ihr es euch ersteinmal saugen.

Viel Spaß damit
McLane

 

[thE_29]

Danke

 

[SnooP]

ich glaube das Problem ist np-vollständig

 

[McLane]

ich glaube das Problem ist np-vollständig

So spontan haette ich das Gegenteil vermutet. Jedenfalls wenn man davon ausgeht, dass das Feld n*n Felder gross ist. Ich habe es mir allerdings nicht genau ueberlegt oder ausgerechnet.

Aber mich wuerde interessieren, worauf du mit deiner Aussage Bezug nimmst.

 

[SnooP]

Das hat mein halb-blindes Informatikerauge mir verraten... - und ich kenne mich mit Sudoku auch nicht soo aus... aber nen google-link verrät dann auch mehr und bestätigt mein Auge

http://www.americanscientist.org/template/AssetDetail/assetid/48550?&print=yes#48707

demnach ist das Backtracking nicht wirklich optimal... was ja aber auch nicht verwunderlich ist - gibt halt immer ne bessere Möglichkeit als Backtracking eigentlich

und am obigen Algorithmusstücken kann man das auch schon ahnen... zum einen sind da ein quadratischer und ein linearer Bestandteil in dem if-Teil drinne (verticalsOK und squareOK) und danach wird das ganze rekursiv aufgerufen... abhängig von der Größe der Tabelle... - das stinkt ganz gewaltig nach np-hart *g*

und noch nen bissel hübscher stehts in diesem Paper:
http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf

hab damit übrigens überhaupt nicht bezug nehmen wollen, wollte nur verdeutlichen, dass es mehr oder weniger egal ist, wie der Algorithmus aussieht, es kann keinen geben, der wirklich effizient (sprich polynomial) ist...

 

[McLane]

Danke für die Links.

Die belegen wirklich, dass meine Vermutung falsch ist und das Problem NP-Vollständig ist.

Aber das Sudoku ist ja, jedenfalls bei 9 Ziffern, so klein, dass es schnell ausgerechnet werden kann.

Dennoch habe ich eine kleine Korrektur: verticalsOK und squareOK arbeiten bei mir beide linear (Ich weiß es tut nichts zur Sache, aber ich wollte es noch mal erwähnen).

Also nochmals vielen Dank für den Link und die zügige Antwort.

 

[SnooP]

richtig - kleinere Sudokus sind noch relativ schnell zu berechnen - aber die Größe des Teils ist ja gerade das n - wenn das zunimmt wirds immer komplexer das zu berechnen.

und ich denke doch, dass squareOK quadratisch ist, oder? also O(n^2):

		for (int y1 = lty; y1 < (lty + 3); y1++) {
			for (int x1 = ltx; x1 < (ltx + 3); x1++) {
				int value = problem[y1][x1];
//...

aber das ist tatsächlich relativ egal - die Komplexität kommt alleine schon wegen der Rekursion zustande...

 

[McLane]

Auch wenn es egal ist, möchte ich die Linearität begünden (ich gebe allerdings zu, das es auf den ersten Blick nach quadratischer Laufzeit aussieht)

Wir haben ein Sudoku mit n Ziffern, daraus ergibt sich, dass ein einzelnes Quadrat Wurzel(n) lang ist und auch Wurzel(n) breit ist (im 9*9 Sudoku also Wurzel(9) = 3). Das muss auch so sein, weil in einem Quadrat n Ziffern stehen müssen (Das ist halt die Regel, die squareOK überprüft).
Da die beiden for-Schleifen Höhe mal Breite Schritte rechnen ergibt sich eine Laufzeit von

O(Wurzel(n) * Wurzel(n)) = O(Quadrat(Wurzel(n))) = O(n) - (Also lineare Laufzeit)

Wie schon gesagt es ist wirklich egal und tut nicht zur Sache, was die NP-Vollständigkeit angeht, aber ich habe gerne Recht

 

[spidermobile]

Hi Lin,

Hm, ich denke mal da muss man nicht sonderlich viel von Mathematik verstehen, nur n'bisserl was überlegen. Kannst ja zuerst mal nen Algorithmus schreiben, der ein einfaches Sudoku lösen kann.

ich kann es mir nicht verkneifen :wink: . Wenn das nichts mit höherer Mathematik zu tun hat, fresse ich einen Besen!

 

[McLane]

Ja ich glaub auch, dass wir ein wenig vom Thema abgekommen sind :wink:

 

[SnooP]

... aber ich gebe gerne zu, dass du recht hast.. ich hatte nur nen oberflächlichen Blick auf den Code geworfen und nicht gesehen, wie sich die Grenzen der for-schleifen berechnen ... hast also gewonnen!

Aber Komplexitätsbetrachtung bei Algorithmen ist doch ganz prima on-topic oder?

 

[Bleiglanz]

hmm

n = Anzahl der freien Felder

dann ist bei Backtracking die "Komplexität" doch O(9^n), weil das ja nix anderes ist als alle Möglichkeiten durchprobieren

aber weil man den Suchbaum bei diesem Problem wunderbar zusammenschlagen kann (wegen der "Einschränkungen") würde es mich nicht sooo stark wundern, wenn das doch polynomial wäre???

hat doch bestimmt schon jemand gelöst die Frage??

[edit] vergesst es, hab gerade die beiden oben verlinkten Papers gesehen