56 lines
1.7 KiB
Java
56 lines
1.7 KiB
Java
public class QueensProblem {
|
|
|
|
public static void main(String[] args) {
|
|
//Initialisiere Schachfeld 8x8
|
|
boolean[][] queen = new boolean[8][8];
|
|
int counter = solutions(queen, 0);
|
|
System.out.println(counter);
|
|
}
|
|
|
|
private static int solutions(boolean[][] queen, int row) {
|
|
//wenn alle Reihen belegt sind alle Damen gesetzt, Abbruchbedingung der Rekursion
|
|
if (row == queen.length) {
|
|
return 1;
|
|
}
|
|
|
|
int counter = 0;
|
|
//gehe jede Spalte der Reihe durch und sehe nach, ob position sicher ist
|
|
for (int col = 0; col < queen.length; col++) {
|
|
// falls nein -->nächster Schleifendurchlaus
|
|
if (!isPositionSave(queen, row, col)) {
|
|
continue;
|
|
}
|
|
|
|
//anderenfalls setze Position auf true
|
|
queen[row][col] = true;
|
|
//setze nächste Reihe
|
|
counter += solutions(queen, row + 1);
|
|
//wenn Lösung gefunden für aktuelles Feld setze zurück auf false
|
|
queen[row][col] = false;
|
|
}
|
|
|
|
return counter;
|
|
}
|
|
|
|
public static boolean isPositionSave(boolean[][] queen, int row, int col) {
|
|
|
|
for (int i = 0; i < row; i++) {
|
|
int dC = row - i;
|
|
// Teste Spalte
|
|
if (queen[i][col]) {
|
|
return false;
|
|
}
|
|
// Teste linke Diagonale
|
|
if (col - dC >= 0 && queen[i][col - dC]) {
|
|
return false;
|
|
}
|
|
// Teste rechte Diagonale
|
|
if (col + dC < queen.length && queen[i][col + dC]) {
|
|
return false;
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
}
|