可爱的琪琪，开心快乐每一天
温馨小屋
可爱的琪琪，开心快乐每一天
posts - 7,comments - 39,trackbacks - 0
八皇后问题
     网上看面试题时看到，摘抄别人写的一个程序，并做了一些注解，翻译为java版，记录一下
package chenqi;

/**
 * 要求：试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解。
 * 提示：在国际象棋上放置皇后时，任何一个皇后的水平、竖直和斜45º都不能有另一个皇后。
 * 解决该问题采用逐次试探的方法，即采用递归调用putchess函数的方法。
 * 首先将第一个皇后放于第一行第一列，然后开始向下一行递归。
 * 每一步递归中，首先检测待放置位置是否与已放置的皇后冲突，如不冲突，则进行下一行的放置，
 * 否则，选择该行的下一个位置进行检测。如整行的位置都冲突，则回到上一行，重新选择位置源码:
 * @author Administrator
 *
 */
public class EightQueen {

    //8根线代表8列，数组中每个对象存的值表示皇后在该列的位置
    int[] line = new int[8];
    int answer=0;
    
    /**
     * 判断是否有冲突---用试探法，判断是否与其他列有冲突
     * @param t
     * @return 返回0表示没有冲突,返回1表示有冲突
     */
    private int Judge(int t) {
        int i, n = 0;
        for (i = 0; i < t; i++) {
            //第一种冲突情况：2列处于同一行冲突
            if (line[i] == line[t]) {
                n = 1;
                break;
            }
            //2列处于斜向上45度对角线冲突
            if (line[i] + i == line[t] + t) {
                n = 1;
                break;
            }
            //2列处于斜向下45度对角线冲突
            if (line[i] - i == line[t] - t) {
                n = 1;
                break;
            }
        }
        return n;
    }
    
    /**
     * 主要控制函数
     * @param n
     */
    private void control(int n)
    {
        int t = 8;
        for (line[n] = 0; line[n] < t; line[n]++) {
            if (Judge(n) == 1)
                continue;
            else if (n != 7)
                control(n + 1);
            else
                show();
        }
    }
    
    /**
     * 显示摆放的结果
     * 
     */
    private void show() {
        int i, j;
        for (i = 0; i < 8; i++) {
            for (j = 0; j < 8; j++) {
                if (line[i] == j)
                    System.out.print("Q");
                else
                    System.out.print("*");
            }
            System.out.println();
        }
        answer++;
        System.out.println();
        System.out.println(answer);
    }


    
    public static void main(String[] args) {
        EightQueen s = new EightQueen();
        s.control(0);
        System.out.println(s.answer);
    }
    
}
这段代码感觉又简洁又易懂，再次感谢他的作者：
http://blog.chinaunix.net/u/26924/showart_228365.html
posted on 2007-02-28 23:38 陈琪 阅读(452) 评论(0)  编辑  收藏 所属分类: java

只有注册用户登录后才能发表评论。
网站导航:
 
Copyright ©2024 陈琪 Powered By博客园 模板提供：沪江博客