eightqueen.java

八皇后问题图形界面实现

/*
 * EightQueen.java
 *
 * Created on 2007年10月13日, 下午4:56
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package eightqueen;

/**
 *
 * @author linda
 */

public class EightQueen {
    static final int QueenMax = 8;//定义皇后的个数
    static int oktimes = 0;//定义解法的种数（8皇后问题有92种解法）
    static int chess[] = new int[QueenMax];//每一个皇后的放置位置
    public static String rows[]=new String[92];//保存92种解法的字符串

    public static void main(String args[]) {//主方法
        for (int i=0;i< QueenMax;i++)
            chess[i]=-1;    
            placequeen(0);//递归调用placequeen方法
            FrameQueen queen=new FrameQueen();//显示主窗口
            System.out.println("\n八皇后问题共有"+oktimes+"个解法。");
    }

    /*
     *placequeen方法功能就是获得每一种解法的字符串,保存在rows数组中,用的是递归方法。
     *八皇后问题递归算法：
     *如果有一个皇后位置为 chess[i]=j，
     *则不安全的地方是 k行的j位置,j+k-i位置,j-k+i位置。
    */
    public static void placequeen(int num) { //num 为现在要放置的行数
        int i=0;
        boolean qsave[] = new boolean[QueenMax];
        for(;i< QueenMax;i++) 
            qsave[i]=true;
        i=0;
        //下面先把安全位数组完成
        //i 是现在要检查的数组值
        while (i< num) {
            qsave[chess[i]]=false;
            int k=num-i;
            if ( (chess[i]+k >= 0) && (chess[i]+k < QueenMax) ) 
                qsave[chess[i]+k]=false;
            if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) ) 
                qsave[chess[i]-k]=false;
            i++;
        }

        //下面遍历安全位
        for(i=0;i< QueenMax;i++) {
            if (qsave[i]==false)
                continue;
            if (num< QueenMax-1) {
                chess[num]=i;
            placequeen(num+1);//递归调用
            }
            else { //产生每一种解法的解法字符串，其中+代表皇后位置
                chess[num]=i;
                oktimes++;	
                String row="";
                for (i=0;i< QueenMax;i++) {
                    if (chess[i]==0);
                    else 
                        for(int j=0;j< chess[i];j++) row+="-";
                    row+="+";
                    int j = chess[i];
                    while(j< QueenMax-1) {
        		row+="-";
        		j++;
                    }
                    rows[oktimes-1]=row;
                }
            }
        }
        //遍历完成就停止
    }
}