sudoku backtrackingproblem

[Bastian]

folgender code:

import java.util.Random;

public class Create {

	int[][] Sudoku = new int[9][9];
	boolean[][][] Versucht = new boolean[9][9][9];
	Random zufall = new Random();

	public void init() {

		// Vorbelegung Sudoku mit Nullen
		for (int r = 0; r < 9; r++) {
			for (int s = 0; s < 9; s++) {
				Sudoku[r][s] = 0;
			}
		}

		// Vorbelegung Versucht mit false
		for (int r = 0; r < 9; r++) {
			for (int s = 0; s < 9; s++) {
				for (int z = 0; z < 9; z++) {
					Versucht[r][s][z] = false;
				}
			}
		}
	}

	public void fill() {
		int row = 0;
		int col = 0;
		boolean found = false;
		// Suche das nächste freie Feld
		while (row < 9 && !found) {
			while (col < 9 && !found) {
				if (Sudoku[row][col] == 0)
					found = true;
				col++;
			}
			col--;
			if (col == 8 && !found) {
				row++;
				col = 0;
			}
		}
		// Abbruch falls kein freies Feld mehr gefunden wurde
		if (!found)
			return;
		// Setze gefundenes Feld = noch nicht benutze Zufallszahl

		int ZufallsZahl = 0;
		do {

			ZufallsZahl = 1 + Math.abs(zufall.nextInt(9));

		} while (Versucht[row][col][ZufallsZahl - 1]);
		System.out.println("Z" + ZufallsZahl);
		// falls nicht doppelt, fülle feld
		if (!doppeltRow(row, col, ZufallsZahl)
				&& !doppeltCol(row, col, ZufallsZahl)) {
			Sudoku[row][col] = ZufallsZahl;
			Versucht[row][col][ZufallsZahl - 1] = true;
			System.out.println("Reihe " + row);
			System.out.println("Spalte " + col);
			System.out.println(Sudoku[row][col]);
		} else if (noSolution(row, col, ZufallsZahl)) {
			if (doppeltRow(row, col, ZufallsZahl)) {
				for (int r = 0; r < 9; r++) {
					for (int z = 0; z < 9; z++) {
						Versucht[r][col][z] = false;

					}
					Sudoku[r][col] = 0;
				}
			}
			if (doppeltCol(row, col, ZufallsZahl)) {
				for (int c = 0; c < 9; c++) {
					for (int z = 0; z < 9; z++) {
						Versucht[row][c][z] = false;

					}
					Sudoku[row][c] = 0;
				}
			}

			// int r = 0;
			// int c = 0;
			// r = row;
			// c = col - 1;
			// if (c < 0) {
			// c = 8;
			// r--;
			// }
			// Sudoku[r][c] = 0;
		}

		fill();
	}

	public boolean doppeltCol(int row, int col, int ZufallsZahl) {
		for (int r = 0; r < 9; r++) {
			if (Sudoku[r][col] == ZufallsZahl /* && c != col */) {
				return true;
			}
		}
		return false;
	}
	public boolean doppeltRow(int row, int col, int ZufallsZahl) {
		for (int c = 0; c < 9; c++) {
			if (Sudoku[row][c] == ZufallsZahl /* && r != row */) {
				return true;
			}
		}

		return false;
	}

	public boolean noSolution(int row, int col, int ZufallsZahl) {
		for (int z = 0; z < 9; z++) {
			if (Versucht[row][col][z] == false)
				return true;
		}
		return false;
	}

}

 

[Bastian]

Z7
Reihe 0
Spalte 3
7
Z1
Z8
Z6
Z3
Z4
Z1
Z3
Z9
Z4
Z1
Z9
Z3
Z1
Z7
Reihe 0
Spalte 3
7
Z2
Z9
Z2
Z8

Problem:
Eigentlich sollte ein 9*9 feld mit zahlen von 1-9 so gefüllt werden, sodass es pro reihe und spalte keine doppelten zahlen gibt. dies scheint auch zu funktionieren, jedoch kommt es irgendwann zu einem StackOverflowError...
Mir fällt nix mehr ein, wie ich das lösen könnt *grml*[/code]

 

[Bleiglanz]

na ja, die Abbruchbedingung wird nicht erreicht

Entschlacke mal den Code, der ist irgendwie suboptimal

while (row < 9 && !found) {
    col = 0;
    while (col < 9 && !found) {
            found=(Sudoku[row][col] == 0);
            col++;
     }
     row++;
}

ich vermute mal, dass nicht sichergestellt ist, dass wirklich bei jedem durchlauf mit found=false immer ein weiteres Feld einen Wert != 0 erhält

evtl. fehlendes else vor dem zweiten if (doppeltCol(row, col, ZufallsZahl))?