8-Queen Problem
Problem:
Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal.
My Code:
________________________________________________________________
package alg;import java.util.Stack;public class EightQueens { public static final int N = 8; static class Queen { public int x, y; Queen(int x, int y) { this.x = x; this.y = y; } } static void findAllResult() { Stack<Queen> s = new Stack<Queen>(); for(int i = 0; i<N; i++){ Queen q = new Queen(0,i); s.push(q); locateNextQueen(1, s); } } static void locateNextQueen(int row, Stack<Queen> queens){ if(row == N){ System.out.println("Find one result:"); for(Queen q : queens){ System.out.println("\t(" + q.x + "," + q.y + ")"); } return; } for(int y = 0; y < N; y++){ boolean valid = true; for(Queen queen : queens){ if( row == queen.x || y == queen.y || (queen.y - y == queen.x - row) || (queen.y - y == row - queen.x) ){ valid = false; break; } } if(valid == false){ continue; }else { Queen q = new Queen(row, y); queens.push(q); locateNextQueen(row+1, queens); queens.pop(); } } } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub findAllResult(); }}