Java :: Aufgabe #87
1 Lösung
Das Damenproblem (Teil I)
Fortgeschrittener - Java
von ElPapito
- 07.05.2015 um 11:42 Uhr
Das klassische Damenproblem besteht aus einem 8x8 Schachfeld und 8 Damen.
Die Aufgabe besteht darin die 8 Damen so zu positionieren, dass sie sich gegenseitig nicht bedrohen, d.h. es dürfen keine zwei Damen in der gleichen Zeile/Spalte/Diagonale stehen.
Schreibe ein kleines Programm, welches ausgibt wie viele Lösungen existieren.
Die Aufgabe besteht darin die 8 Damen so zu positionieren, dass sie sich gegenseitig nicht bedrohen, d.h. es dürfen keine zwei Damen in der gleichen Zeile/Spalte/Diagonale stehen.
Schreibe ein kleines Programm, welches ausgibt wie viele Lösungen existieren.
Lösungen:
Java-Code
/**
* @author ElPapito
* @date 07.05.2015
*/
public class DasDamenproblem {
public static void main(String[] args) {
boolean[][] queen = new boolean[8][8];
int counter = solutions(queen, 0);
System.out.println(counter);
}
private static int solutions(boolean[][] queen, int row) {
if (row == queen.length) {
return 1;
}
int counter = 0;
for (int col = 0; col < queen.length; col++) {
if (!isPositionSave(queen, row, col)) {
continue;
}
queen[row][col] = true;
counter += solutions(queen, row + 1);
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;
}
}