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 @ 2007-12-14 21:14 小屁 阅读(807) | 评论 (2) | 编辑 收藏

仅列出标题