八皇后问题的解决

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了八皇后问题的解决，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2521字，纯文字阅读大概需要4分钟。

内容图文

八皇后问题

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。

这是栈的一个典型应用。我们先将皇后放在(0,0)点的位置，然后在第二行依次试探，依次进行，如果在某一行没有位置了，弹出前一行，将x的位置加1，再进行试探。

但是我想找出所有的解，那么需要在每次找到解之后，只保留栈的第一位，并且将第一位的x的值加1
使用Java：

package com.stack.queen;


import java.util.EmptyStackException;
import java.util.Objects;
import java.util.Stack;

// 皇后类
public class Queen {
    int x, y;

    // 判断两个点是否冲突，如果true，表示皇后之间相互冲突
    public boolean isContradict(Queen queen) {
        return this.x == queen.x || this.y == queen.y || (this.x + this.y == queen.x + queen.y)
                || (this.x - this.y == queen.x - queen.y);
    }

    // 重写equals方法,用于判断两个皇后是否冲突,相等代表冲突
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Queen queen = (Queen) o;
        return this.isContradict(queen);
    }

    // 构造方法
    public Queen(int x, int y) {
        this.x = x;
        this.y = y;
    }

    // 重写Hash方法
    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }

    // addX 将Queen的x值增加1,并且返回增加后的x的值
    public int addX() {
        this.x++;
        return this.x;
    }

    // main函数
    public static void main(String[] args) {
        findWay(7);
    }

    // 静态函数，用于寻找stack中是否有"相等"的元素
    public static <T> boolean find(Stack<T> stack, T elem) {
        if (stack.empty()) return false;
        for (T currentElem : stack) {
            if (currentElem.equals(elem)) return true;
        }
        return false;
    }

    // 返回寻找到的八皇后的位置
    public static void findWay(int n) {
        Stack<Queen> stack = new Stack<>();
        Queen queen = new Queen(0, 0);
        // 把起始的皇后位置放进栈中
        stack.push(queen);
        // 当栈的大小大于n时停止
        while (stack.size() < n) {
            queen = new Queen(0, queen.y + 1);
            while (find(stack, queen)) {
                while (queen.addX() >=n) {
                    if (queen.x>=n && queen.y==0){
                        return;
                    }
                    queen = stack.pop();
                    queen.addX();
                }
            }
            stack.push(queen);
            if (queen.y==n-1){
                for (Queen q : stack) {
                    q.printAxis();
                }
                System.out.println("**************");
                queen= stack.firstElement();
                if (queen.x==n-1) {
                    return;
                }
                stack.clear();
                queen.addX();
                stack.push(queen);
            }
        }
    }
	// 用于测试的函数
    public void printAxis(String msg) {
        System.out.printf("[%s] 皇后横坐标为%d,纵坐标为%d\n", msg, this.x, this.y);
    }
	// 用于测试的函数	
    public void printAxis() {
        System.out.printf("皇后横坐标为%d,纵坐标为%d\n", this.x, this.y);
    }
}

内容总结

以上是互联网集市为您收集整理的八皇后问题的解决全部内容，希望文章能够帮你解决八皇后问题的解决所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---