Hallo,
ich muss das 8 Damenproblem lösen,und eine rekursive Methode
schreiben, die alle lösungen für ein 8*8_schachbrett berechnet und ausgibt:Hier die quellcode:
könnt ihr mir bitte helfen um mein programm zu verbessern?
Danke
ich muss das 8 Damenproblem lösen,und eine rekursive Methode
Java:
void backtrack(int i, inz j)
Java:
public class Queens {
public static int N = 8;
public static int solutionID = 0;
public static boolean [][] board = new boolean[N][N];
public static void drawBoard() {
System.out.println("// solution number: "+(++solutionID));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
System.out.print((j == 0 ? "// " : "") + (board[i][j] ? "x" : ".") + (j+1 == N ? "\n": " "));
System.out.println();
}
public static boolean isValidBoard( int row, int column){
//Durchlaufe horizontal
for(int i=0;i<N;i++){
if(board[row][i]){
return false;
}
}
//Durchlaufe diagonal
// unten rechts
for(int i=0; row+i<N && column+i<N;i++){
if(board[row+i][column+i]){
return false;
}
}
//oben rechts
for(int i=0; row-i>=0 && column+i<N;i++){
if(board[row-i][column+i]){
return false;
}
}
//oben links
for(int i=0; row-i>=0 && column-i>=0; i++){
if(board[row-i][column-i]){
return false;
}
}
//unten links
for(int i=0; row+i<N &&column-i>=0;i++){
if(board[row+i][column-i]){
return false;
}
}
//durchlaufe vertikal
for(int i=0;i<N; i++){
if(board[i][column]){
return false;
}
}
board[row][column]=true;
return true;
}
public static void backtrack(int i, int j){//hier ist es nicht richtig!!!!!
if(i>N-1){
return;
}
boolean valid=isValidBoard(i,j);
if(valid){
solutionID++;
drawBoard();
i++;
backtrack(i,j);
}else{
backtrack(i,j);
i++;
}
}
public static void main(String args[]) {
for (int j = 0; j < N; j++) {
board[0][j] = true;
backtrack(0, j);
board[0][j] = false;
}
System.out.println("solution count correct: " + (solutionID == 92));
}
}
Danke