Life is filled with wonder

八皇后

写了两天,
应用递归和回溯.
对如何组织类,
更一步加深
/Files/xyq002444/Queens.rar
八皇后主程序的算法
import java.util.*;

public class QueenSolver {

    private int count;  //皇后的数目
    private Queen queens[];
    private Queue<Queen[]> queue;

    public QueenSolver(int count) {
        this.count = count;
        queens = new Queen[count];
        queue = new QueenList<Queen[]>();
        this.initialize();
        this.process();
    }
    //初始化
    private void initialize() {
        for (int i = 0; i < count; i++) {
            queens[i] = new Queen(i + 1, 0);
        }
    }
    //能否放置一个皇后
    private boolean place(Queen queen) {
        for (int i = 0; i < queen.x - 1; i++) {
            if (queens[i].y == queen.y || queens[i].getX_Y() == queen.getX_Y() || queens[i].getAddXY() == queen.getAddXY()) {
                return false;
            }
        }
        return true;
    }

    private void process() {
        int k = 1;
        queens[k - 1].y = 0;
        while (k > 0) {
            queens[k - 1].y = queens[k - 1].y + 1;
            while (queens[k - 1].y <= count && !this.place(queens[k - 1])) {
                queens[k - 1].y = queens[k - 1].y + 1;
            }
            if (queens[k - 1].y <= count) {
                if (k == count) {
                    //                   this.printPosition(queens);
                    Queen[] queenClone = new Queen[queens.length];
                    for (int i = 0; i < queenClone.length; i++) {
                        queenClone[i] = new Queen(queens[i].x, queens[i].y);
                    }
                    for (int i = 0; i < queens.length; i++) {
                        queens[i].setXPosition();
                        queens[i].setYPosition();
                    }
                    queue.offer(queenClone);
                } else {
                    k = k + 1;
                    queens[k - 1].y = 0;
                }
            } else {
                k = k - 1;
            }
        }
    }

    public void printPosition(Queen[] queens) {
        for (Queen queen : queens) {
            System.out.println(queen.x + " y: " + queen.y);
        }
    }

    public Queue<Queen[]> getQueue() {
        return this.queue;
    }
}

posted on 2007-12-14 21:14 小屁 阅读(815) 评论(2)  编辑  收藏 所属分类: java

评论

# re: 八皇后 2007-12-14 21:34 小屁

演示程序 jar文件, 直接运行  回复  更多评论   

# re: 八皇后 2007-12-15 00:51 李伟彬

check out 一下www.operamasks.org的源码，发现老袁新创了一门名为elite的动态语言。在elite下，8皇后问题的解法如下：

/* 利用列表聚合解决8皇后问题 */
define queens(n) {
define scan(i) {
if i==0 then [[]]
else [[q:qs] where qs in scan(i-1), q in [1..n], safe(q, qs)];
}
scan(n);
}

define safe(x, qs) {
define n = 1;
for (y in qs) {
if (x==y || x==y+n || x==y-n)
return false;
n++;
}
return true;
}

define count = 0;
for (x in queens(8)) {
cout << ++count << ": " << x << endl;
}  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: