`
standalone
  • 浏览: 609811 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

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

}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics