משתמש:יבחוש~hewikisource/דוגמה למימוש חידת n המלכות ב - Java

לב האלגוריתם נמצא ב - printAllSolutions.

class NQueenSolver {
    // A solver of the n queens puzzle. 
    // solutions representation:
    //   array of n integers in [0,n-1] named board. Entry board[i] represents the column 
    //   of the queen in line i.  
 

    // Please note: This code is aimed to be as simple as possible. 
    // A more classic approach would have been to return all the solutions 
    // in a data strcture (instead of printing them during the recursive process)    

    // The backtracking algorthim: 
    static void printAllSolutions(int i, int[] board) {
	if(i==board.length) { // all lines filled - found a solution 
	    printBoard(board); 
	    return; 
	}
	for(int j=0; j<board.length; ++j)  // check all places in line 
	    if(isValidPlace(i,j,board)) {
		board[i] = j;
		printAllSolutions(i+1,board); // ok, filled this line, try filling all the next lines
	    }
	// reached the end of the line - backtracking 
    }
    
    // warper 
    static void printAllSolutions(int n) {
	printAllSolutions(0,new int[n]);
    }

    static public void main(String[] args) {
	printAllSolutions(8);
	// try also: printAllSolutions(5);
    }


    //methods which are called by the backtracking algorithm:

    static void printBoard(int[] board) {
	for(int i=0; i<board.length; ++i) { 
	    for(int j=0; j<board.length; ++j)
		if(board[i] == j) 
		    System.out.print("|Q");
		else
		    System.out.print("| ");
	    System.out.println("|");
	}
	System.out.println("\n");
    }

    static boolean isValidPlace(int i, int j, int[] board) {
	for(int i1 = 0; i1<i; ++i1) 
	    if(board[i1] == j ||          // is it on the same column?  
	       i1 + board[i1] == i + j || // one diagonal
	       i1 - board[i1] == i - j)   // the other diagonal
		return false;
	return true;
    }
}

// output format: 

// |Q| | | | | | | |
// | | | | |Q| | | |
// | | | | | | | |Q|
// | | | | | |Q| | |
// | | |Q| | | | | |
// | | | | | | |Q| |
// | |Q| | | | | | |
// | | | |Q| | | | |


// |Q| | | | | | | |
// | | | | | |Q| | |
// | | | | | | | |Q|
// | | |Q| | | | | |
// | | | | | | |Q| |
// | | | |Q| | | | |
// | |Q| | | | | | |
// | | | | |Q| | | |

// ...