如坐春风
人生苦短，要紧跟自己的梦想，爱你所做的事业。
posts - 160,  comments - 284,  trackbacks - 0
八皇后问题解法
代码如下:

package com.sitinspring;

/**
 * 八皇后问题例题
 * @author sitinspring
 *
 * @date:2008-4-11-下午04:07:12
 */
public class EightQueen{
    // X代表处于别的皇后杀伤范围内,不能放下的格子
    private static final String ImpossiblePos = "X";
    
    // Q代表皇后的位置
    private static final String Qreen = "Q";
    
    // ■代表可以放置皇后的位置
    private static final String Space = "■";
    
    // 皇后数量
    private int n;
    
    /**
     * 构造函数
     * @param n
     */
    public EightQueen(int n){
        this.n=n;
        putQueens();
    }
    
    /**
     * 放置皇后
     *
     */
    public void putQueens(){    
        String[][] arr=null;
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                // 初始化数组
                arr=getInitArray();
                
                // 放置第一个皇后
                putOneQreen(i,j,arr);
                
                // 放置其余皇后
                placeQueens(n-1,arr);
                
                if(getQreenCount(arr)==n){
                    // 如果所有皇后都能放下则打印放置图
                    printArray(arr);
                    //return;
                }

            }
        }    
        
        // 到这里说明不可能放下
        //System.out.println(n+"阶不可能放下诸皇后");        
    }
    
    
    /**
     * 放置其余皇后
     * @param qreenCount
     * @param arr
     */
    private void placeQueens(int qreenCount,String[][] arr){
        for(int queenIndex=0;queenIndex<qreenCount;queenIndex++){
            int spaceRow=-1,spaceCol=-1;
            
            // 找出可以放皇后的地方
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(arr[i][j].equals(Space)){
                        spaceRow=i;
                        spaceCol=j;
                        break;
                    }
                }
            }
            
            if(spaceRow!=-1 && spaceCol!=-1){
                putOneQreen(spaceRow,spaceCol,arr);
            }
        }        
    }
    
    /**
     * 放置一个皇后,改变其所在单元格和控制单元格
     * @param row
     * @param col
     * @param arr
     */
    private void putOneQreen(int row,int col,String[][] arr){
        // 所在单元格
        arr[row][col]=Qreen;
        
        // 皇后控制的横向单元格v
        for(int i=0;i<n;i++){
            if(arr[i][col].equals(Space)){
                arr[i][col]=ImpossiblePos;
            }            
        }
        
        // 皇后控制的纵向单元格h
        for(int i=0;i<n;i++){
            if(arr[row][i].equals(Space)){
                arr[row][i]=ImpossiblePos;
            }        
        }
        
        // 皇后控制的斜向单元格\
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if( (i-j)==(row-col) ){
                    if(arr[i][j].equals(Space)){
                        arr[i][j]=ImpossiblePos;
                    }        
                }
            }
        }
        
        // 皇后控制的斜向单元格/
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if( (i+j)==(row+col) ){
                    if(arr[i][j].equals(Space)){
                        arr[i][j]=ImpossiblePos;
                    }        
                }
            }
        }
    }
    
    /**
     * 取得初始化的数组
     * @return
     */
    private String[][] getInitArray(){
        String[][] arr=new String[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                arr[i][j]=Space;
            }
        }
        
        return arr;
    }
    
    /**
     * 取得皇后的数目
     * @param arr
     * @return
     */
    private int getQreenCount(String[][] arr){
        int retval=0;
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(arr[i][j].equals(Qreen)){
                    retval++;
                }
            }
        }
        
        return retval;
    }
    
    /**
     * 答应棋盘方阵
     * @param arr
     */
    private void printArray(String[][] arr){
        System.out.println("-------"+n+"------>");
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                System.out.print(arr[i][j]+" ");
            }
            System.out.print("\n");
        }
        System.out.println("<-------"+n+"------");
    }
    
    /**
     * 入口
     * @param args
     */
    public static void main(String[] args){
        for(int i=0;i<20;i++){
            new EightQueen(i);
        }
    }
}


输出:
-------1------>
Q 
<-------1------
-------4------>
X X Q X 
Q X X X 
X X X Q 
X Q X X 
<-------4------
-------4------>
X Q X X 
X X X Q 
Q X X X 
X X Q X 
<-------4------
-------4------>
X X Q X 
Q X X X 
X X X Q 
X Q X X 
<-------4------
-------4------>
X Q X X 
X X X Q 
Q X X X 
X X Q X 
<-------4------
-------5------>
X X Q X X 
X X X X Q 
X Q X X X 
X X X Q X 
Q X X X X 
<-------5------
-------5------>
X X X Q X 
X Q X X X 
X X X X Q 
X X Q X X 
Q X X X X 
<-------5------
-------5------>
X X X X Q 
X X Q X X 
Q X X X X 
X X X Q X 
X Q X X X 
<-------5------
-------5------>
X X X Q X 
X Q X X X 
X X X X Q 
X X Q X X 
Q X X X X 
<-------5------
-------5------>
X X Q X X 
X X X X Q 
X Q X X X 
X X X Q X 
Q X X X X 
<-------5------
-------5------>
X X X X Q 
X X Q X X 
Q X X X X 
X X X Q X 
X Q X X X 
<-------5------
-------5------>
X X Q X X 
X X X X Q 
X Q X X X 
X X X Q X 
Q X X X X 
<-------5------
-------5------>
X X X Q X 
Q X X X X 
X X Q X X 
X X X X Q 
X Q X X X 
<-------5------
-------5------>
X X X Q X 
X Q X X X 
X X X X Q 
X X Q X X 
Q X X X X 
<-------5------
-------5------>
X X X X Q 
X Q X X X 
X X X Q X 
Q X X X X 
X X Q X X 
<-------5------
-------5------>
Q X X X X 
X X Q X X 
X X X X Q 
X Q X X X 
X X X Q X 
<-------5------
-------5------>
X X X Q X 
X Q X X X 
X X X X Q 
X X Q X X 
Q X X X X 
<-------5------
-------5------>
X X Q X X 
X X X X Q 
X Q X X X 
X X X Q X 
Q X X X X 
<-------5------
-------5------>
X X X Q X 
X Q X X X 
X X X X Q 
X X Q X X 
Q X X X X 
<-------5------
-------5------>
X X X X Q 
X X Q X X 
Q X X X X 
X X X Q X 
X Q X X X 
<-------5------
-------5------>
X X X X Q 
X Q X X X 
X X X Q X 
Q X X X X 
X X Q X X 
<-------5------
-------5------>
X Q X X X 
X X X X Q 
X X Q X X 
Q X X X X 
X X X Q X 
<-------5------
-------6------>
X X X X Q X 
X X Q X X X 
Q X X X X X 
X X X X X Q 
X X X Q X X 
X Q X X X X 
<-------6------
-------7------>
X X X X X Q X 
X X X Q X X X 
X Q X X X X X 
X X X X X X Q 
X X X X Q X X 
X X Q X X X X 
Q X X X X X X 
<-------7------
-------7------>
X X X X X Q X 
X X Q X X X X 
Q X X X X X X 
X X X Q X X X 
X X X X X X Q 
X X X X Q X X 
X Q X X X X X 
<-------7------
-------7------>
X X X X X Q X 
X X X Q X X X 
X Q X X X X X 
X X X X X X Q 
X X X X Q X X 
X X Q X X X X 
Q X X X X X X 
<-------7------
-------7------>
X X X X X X Q 
X X X X Q X X 
X X Q X X X X 
Q X X X X X X 
X X X X X Q X 
X X X Q X X X 
X Q X X X X X 
<-------7------
-------7------>
X X X X X Q X 
X X Q X X X X 
X X X X X X Q 
X X X Q X X X 
Q X X X X&nbs