Sudoku Löser

[Loud Silence]

Ich bin im Moment dabei ein Programm zur Lösung eines Sudokus zu programmieren. Es ist noch nicht fertiggestellt. Ich stoße jedoch jetzt schon auf ein Problem. Leider benötigt man, um das Problem zu verstehen den ganzen Code:

public class Sudoku {

public static int [][] Field  = new int [9][9];
	
	public static void backtrack(int posX, int posY) {
	
		//Field [6][0] = 8;
		
		for (int a = 1; a < 10; a++){
			if (checkAll(posX, posY, a)== true){
				if (posX == 8){
					Field [posX][posY] = a;
					System.out.println("X: " + posX + " Y: " + posY + "  =  " + Field[posX][posY]);
					backtrack(0, posY + 1);
					break;
				}else{
				Field [posX][posY] = a;
				System.out.println("X: " + posX + " Y: " + posY + "  =  " + Field[posX][posY]);
				backtrack(posX +1, posY);
				break;
				}
			} else{
			}
		}
		Field[posX][posY] = 0;
		//System.out.println(checkBox(6, 1, 8));
	}
	
	
	public static boolean checkAll (int x, int y, int val){
		if(checkCol(x, val) && checkRow(y, val) && checkBox(x, y, val)){
			return true;
		}else {
			return false;
		}
	}
	
	
	public static boolean checkCol(int x, int val){
		
		for(int y = 0;y < 9; y++ ){
			if (Field [x][y] == val){
				//System.out.println("Treffer Spalte");
			return false;
			}
		}
		return true;
	}
	
	public static boolean checkRow(int y, int val){
		for(int x = 0;x < 9; x++ ){
			if (Field [x][y] == val){
				//System.out.println("Treffer Reihe");
			return false;
			}		
		}
		return true;
	}
	
	public static boolean checkBox(int x, int y, int val){
		x = (x / 3) * 3;
		y = (y / 3) * 3;
		
		for (int row = 0; row < 3; row++){
			for (int col = 0; col < 3; col++){
				if (Field[y + row][x + col] == val){
					//System.out.println("Treffer Box");
					return false;
				}
			}
		}
		return true;
	}
	
	public static void main(String[] args) {
	
		
		backtrack(0,0);
		
	}

}

Die Ausgabe, wenn ich das Programm laufen lasse, sieht nun wie folgt aus:

X: 0 Y: 0 = 1
X: 1 Y: 0 = 2
X: 2 Y: 0 = 3
X: 3 Y: 0 = 4
X: 4 Y: 0 = 5
X: 5 Y: 0 = 6
X: 6 Y: 0 = 7
X: 7 Y: 0 = 8
X: 8 Y: 0 = 9
X: 0 Y: 1 = 4
X: 1 Y: 1 = 5
X: 2 Y: 1 = 6
X: 3 Y: 1 = 1
X: 4 Y: 1 = 2
X: 5 Y: 1 = 3
X: 6 Y: 1 = 8
X: 7 Y: 1 = 7

Sudoku:

1 2 3 4 5 6 7 8 9
4 5 6 1 2 3 8 7

Mir geht es nun um die beiden fett gedruckten Zahlen.
Warum werden sie überhaupt ausgegeben?
Müsste er nicht bei der 8 schon abbrechen da keine Zahl an diese Stelle hineinpasst?
Grüße
LS

 

[Loud Silence]

*push*

 

[frequency]

nabend,

du hast in zeile 66 <if (Field[y + row][x + col] == val){> geschrieben, meinst aber sicher
<if (Field[x+ row][y+ col] == val){> oder?

sonst ist mir noch aufgefallen, dass das meiner Auffassung nach nicht ganz sauber ist, denn
- zeile 12 und zeile 17 kannst du einmal vor zeile 11 schreiben
- was soll zeile 22?

ich würde die Sache anders angehen:
übergib dem backtracking steht's ein x, ein y, ein Wert für die Zelle bei x und y und das sudoku
das backtracking legt ein neues array (sudoku) an, kopiert das übergebene dort hinein und trägt den übergebenen Wert in die Kopie ein
nun suchen zwei ineinander verschachtelte forschleifen nach der nächsten freien Zelle in der Kopie
jetzt wird mit einer forschleife und deinem checkall ein Kandidat für eben diese freie Zelle in der Kopie ermittelt
das x, das y und der Kandidat sowie die Kopie werden wieder dem backtracking übergeben
hinter die forschleife für den Kandidaten ein Return (hier enden fehlerhafte sudokus)
hinter die beiden verschachtelten fortschleifen ein return (hier enden zulässige sudokus)
fertig

 

[frequency]

ja doch, ich bin mir sicher das der Fehler iwo in checkbox liegt, denn
die Bedingung des ifs in zeile 10 muss wahr gewesen sein, sonst gäbe es die Ausgabe ja nicht.
bei checkrow und checkcol bin ich voll bei dir, die funktionieren. bleibt nur checkbox übrig...

 

[Loud Silence]

Danke, dass sie sich die Zeit genommen haben.
Der erste Tipp war schon mal Gold wert. Vielen Dank dafür!
Er bricht jetzt wie gewünscht nach der 3 ab.
Bei allem weiteren muss ich zugeben, dass ich etwas ausgestiegen bin.
Ich wollte wie folgt weiter verfahren:
Wenn du nicht mehr weiter kommst gehe eine Zahl zurück und erhöhe sie um eins. Mach weiter.
Beim nächsten Fehler letzte Zahl wieder ++. Wenn letzte Zahl 9 dann noch eine Zahl weiter zurück...

 

[frequency]

moin,

freut mich, wenn ich dir helfen konnte

wie gesagt, ich würde das anders angehen. Denn: du hast den Kern getroffen, wie realisiert man es, dass, wenn kein Kandidat mehr gefunden werden kann für eine freie Zelle, ausreichend weit zurückgegangen wird und alle Einträge bis hier rückgängig gemacht werden?

du schreibst Einträge immer gleich in das original, obwohl du nicht weißt ob sie richtig sind, sie sind es eben nur zum Zeitpunkt des Eintrags, im nächsten Schritt kann sich schon ergeben, dass der vorherige Eintrag auf jeden fall falsch ist.

Eben auf Grund dessen würde ich immer ein array übergeben und in der Funktion ein weiteres anlegen und das übergebene dort hineinkopieren und mit der Kopie weiter arbeiten, denn wenn nun einer Zelle kein Wert mehr zugewiesen werden kann, kann man die Funktion verlassen (schließen), die kopie existiert also einfach nicht mehr (sie ist ja nur in der Funktion sichtbar) und es wird mit dem vorherigen array weitergearbeitet usw...

greetz

 

[Loud Silence]

Ok also ich hab jetzt mal ein bisschen im Internet herumgeschaut und diesen Link gefunden. Es sind im Prinzip dieselben Komponenten verbaut, allerdings sehe ich nicht, wo genau das backtracking stattfindet. Das Programm schein aber zu funktionieren.

 

[frequency]

hi,

der Quelltext ist, was die Rekrusion betrifft, für 'n Ar***! Da wird mit Laufzeitspeicher umhergeworfen, unglaublich! Außerdem wird immer noch ein, meiner Meinung nach, schwere lesbarer Weg beschritten.
Was das Applet betrifft, davon hab ich keine Ahnung. Vielleicht ist das ganz gut, das vermag ich nicht zu sagen.

Kommen wir nochmal zu Deinem Problem, ich habe mich damals ebenfalls mit dem Thema beschäftigt und schlussendlich das Folgende zustande gebracht. Ja, das ist C. Es sei mir verziehen, das jetzt nicht umzuschreiben. C und Java funktionieren in den hier relevanten Punkten aber identisch.
Schau Dir das mal genau an ... Für daraus resultierende Fragen stehe ich nachwievor gern zur Verfügung.

Eine Frage habe ich noch: Weisst Du was genau Rekrusion ist und was der Begriff Backtracking meint?

#include <stdio.h>
#include <stdlib.h>

#define G 3
#define true 1
#define false 0

int isvalid(int wert, int zeile, int spalte, int feld[G*G][G*G])
{
	int i, j;
	
	for (j=0; j<G*G; j++)
		if (feld[zeile][j]==wert)
			return false;
	
	for (i=0; i<G*G; i++)
		if (feld[i][spalte]==wert)
			return false;
	
	for (i=(zeile/G)*G; i<(zeile/G+1)*G; i++)
		for (j=(spalte/G)*G; j<(spalte/G+1)*G; j++)
			if (feld[i][j]==wert)
				return false;
	
	return true;
}
backtracking(int wert, int zeile, int spalte, int feld[G*G][G*G])
{
	int array[G*G][G*G];
	int value;
	int i, j;
	
	for (i=0; i<G*G; i++)
		for (j=0; j<G*G; j++)
			array[i][j]=feld[i][j];
	
	array[zeile][spalte]=wert;
	
	for (i=0; i<G*G; i++)
		for (j=0; j<G*G; j++)
			if ( !array[i][j] ) {
				for (value=1; value<=9; value++)
					if ( isvalid(value, i, j, array) )
						backtracking(value, i, j, array);
				}
				return;
			}
	
	//anzahl_loesungen++;
	printf("-----------\n");
	printf("cnt=%d:\n", cnt);
	for (i=0; i<G*G; i++)
	{
		for (j=0; j<G*G; j++)
		{
			printf("%d", array[i][j]);
		}
		printf("\n");
	}
	printf("----------\n");
	system("pause");
	return;
}
int main()
{
	int sudoku[G*G][G*G]={0};
	/*int sudoku[G*G][G*G]={ {7,0,0,0,0,0,0,0,0},
						 {0,1,3,2,0,0,6,0,0},
						 {0,5,6,0,0,0,0,0,8},
						 {0,3,1,7,0,0,0,8,0},
						 {6,0,0,0,2,8,0,0,5},
						 {9,0,0,0,0,0,0,0,0},
						 {0,0,0,4,0,2,0,7,0},
						 {0,0,0,0,0,7,0,0,3},
						 {0,7,0,1,0,0,2,9,0}};*/
	
	backtracking(sudoku[0][0], 0, 0, sudoku);
	
	//int i, j;
	//for (i=0; i<G*G; i++)
	//{
	//	for (j=0; j<G*G; j++)
	//	{
	//		printf("%d", sudoku[i][j]);
	//	}
	//	printf("\n");
	//}
	
	printf("Das Sudoku hat %d Loesungen!\n"
		  "Anzahl Fkt.-Aufrufe %d\n", anzahl_loesungen, rekursions_tiefe);
	
	system("pause");
	return EXIT_SUCCESS;
}

 

[frequency]

hi,

der Quelltext ist, was die Rekrusion betrifft, für 'n Ar***! Da wird mit Laufzeitspeicher umhergeworfen, unglaublich! Außerdem wird immer noch ein, meiner Meinung nach, schwere lesbarer Weg beschritten.
Was das Applet betrifft, davon hab ich keine Ahnung. Vielleicht ist das ganz gut, das vermag ich nicht zu sagen.

Kommen wir nochmal zu Deinem Problem, ich habe mich damals ebenfalls mit dem Thema beschäftigt und schlussendlich das Folgende zustande gebracht. Ja, das ist C. Es sei mir verziehen, das jetzt nicht umzuschreiben. C und Java funktionieren in den hier relevanten Punkten aber identisch.
Schau Dir das mal genau an ... Für daraus resultierende Fragen stehe ich nachwievor gern zur Verfügung.

Eine Frage habe ich noch: Weisst Du was genau Rekrusion ist und was der Begriff Backtracking meint?

#include <stdio.h>
#include <stdlib.h>

#define G 3
#define true 1
#define false 0

int isvalid(int wert, int zeile, int spalte, int feld[G*G][G*G])
{
	int i, j;
	
	for (j=0; j<G*G; j++)
		if (feld[zeile][j]==wert)
			return false;
	
	for (i=0; i<G*G; i++)
		if (feld[i][spalte]==wert)
			return false;
	
	for (i=(zeile/G)*G; i<(zeile/G+1)*G; i++)
		for (j=(spalte/G)*G; j<(spalte/G+1)*G; j++)
			if (feld[i][j]==wert)
				return false;
	
	return true;
}
backtracking(int wert, int zeile, int spalte, int feld[G*G][G*G])
{
	int array[G*G][G*G];
	int value;
	int i, j;
	
	for (i=0; i<G*G; i++)
		for (j=0; j<G*G; j++)
			array[i][j]=feld[i][j];
	
	array[zeile][spalte]=wert;
	
	for (i=0; i<G*G; i++)
		for (j=0; j<G*G; j++)
			 if ( !array[i][j] ) {
				 for (value=1; value<=9; value++)
					if ( isvalid(value, i, j, array) )
						 backtracking(value, i, j, array);

 				 return;
			}
	
	
	 printf("-----------\n");
	for (i=0; i<G*G; i++)
		for (j=0; j<G*G; j++)
 			printf("%d", array[i][j]);
		printf("\n");
	 printf("----------\n");
	system("pause");
 	return;
}
int main()
{
	int sudoku[G*G][G*G]={0};
	/*int sudoku[G*G][G*G]={ {7,0,0,0,0,0,0,0,0},
						 {0,1,3,2,0,0,6,0,0},
						 {0,5,6,0,0,0,0,0,8},
						 {0,3,1,7,0,0,0,8,0},
						 {6,0,0,0,2,8,0,0,5},
						 {9,0,0,0,0,0,0,0,0},
						 {0,0,0,4,0,2,0,7,0},
						 {0,0,0,0,0,7,0,0,3},
						 {0,7,0,1,0,0,2,9,0}};*/
	
	backtracking(sudoku[0][0], 0, 0, sudoku);
	
	system("pause");
	return EXIT_SUCCESS;
}

 

[frequency]

Sorry, Fehler meinerseits. Der zweite ist der Richtige! Ich übe noch mit dem Editor :lol:
Wobei man sich dort (also im zweiten Quelltext!) Zeile 50 bis 56 noch sparen kann, wenn einen nur interessiert ob es lösbar ist und wieviele Lösungen es hat. Das Ganze ist also, wenn man es richtig macht, extrem kurz!