Damenproblem

[valentina2013]

Hallo,

ich muss das 8 Damenproblem lösen,und eine rekursive Methode

void backtrack(int i, inz j)

schreiben, die alle lösungen für ein 8*8_schachbrett berechnet und ausgibt:Hier die quellcode:

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));

	}
	
}

könnt ihr mir bitte helfen um mein programm zu verbessern?
Danke

 

[JavaMeister]

Wie genau soll es verbessert werden?

 

[valentina2013]

so dass die backtrack methode alle mögliche löseungen findet
die isValiBoard methode sagt mir ob eine dame auf dem übergebenen platz sitzen darf. und in der methode setze ich die dame auch. vielleicht ist dass unten schon ein problem, denn ich muss doch ständig neu die dame setzten . Es muss quasi immer gezählt werden wie oft ich die 8 damen auf einmal setze.dieser teil habe ich garnicht ,hu bin ganz dzrcheinander

 

[valentina2013]

Bitte Hilft mir:

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(boolean board[][]){
		
			for (int row=0; row<N;row++){
				for (int column=0;column<N;column++){
					if (board[row][column]){
						// Zeile überprüfen, es reicht ab der aktuellen Position nach rechts zu suchen
						for (int k = column+1;k<board[row].length;k++){
							if (board[row][k])return false;
						}
						
						// Spalte überprüfen, es reicht ab der aktuellen Position nach unten zu suchen
						for (int k = row + 1; k < N;  k++) {
							if (board [k][column])return false;
						}
						
						// Diagonalen überprüfen
						for (int k = 1; ((row + k) < N) && ((column + k) < N);k++){
							if (  board[row+k][column+k])return false;
							}
																
						for (int k = 1; ((row + k) <N)&& ((column - k) >= 0); k++) {
							if (board[row+k][column-k])  return false;
						}										
					}				
				}			
			}		
			return true;
		}
	
	
	public static void backtrack(int i, int j){//hier wird solutionID doppeltgezählt
		for(int a=j;a<board[i].length;a++){//backtrack muss i und j übergeben bekommen (so die 
			board[i][a]=true;                 //aufgabenstellung)wie kann ich es hier verbessern?
			if(isValidBoard(board)){
				if(i>=N-1){
					solutionID++;
					drawBoard();
				}else{
					backtrack(i+1,j);
				}
			}
			board[i][a]=false;
		}
		
	}
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));

	}
	
}

die code funktioniert, jedoch die ausgabe von solutionID ist 184 und nicht 92,

 

[Deros]

in drawBoard gibt es die verfängliche Zeile

System.out.println("// solution number: "+(++solutionID));

nehme an hier willst du nicht wirklich ++solutionID oder?

 

[valentina2013]

ah cool, danke dir