欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

八皇后问题java解法

程序员文章站 2022-04-15 19:01:37
...

八皇后问题

八皇后问题是:在八行八列的格子上放8个皇后(棋子),使得任意两个皇后都攻击不到对方,即使得他们都不在同一行同一列和同一斜线上。

    int[] result ;//最终的结果数组
    int queenNum;// 皇后的数量,N皇后
    int k = 0;
    public void static main(String[] args) {

        queenNum = 8;
        result = new int[queenNum];
        questionN(0);

    }

//  核心回溯算法
    public void questionN(int n) {
        if(n == queenNum){
            k++;
            Log.e("-----","解法:"+k);
            for(int i = 0;i<queenNum;i++){
                Log.e("-----","第"+(i+1)+"行放置位置:"+(result[i]+1));
            }
            return ;
        }

        for (int i = 0;i<queenNum;i++){
            result[n] = i;
            if(checkValid(result,n)){
                questionN(n+1);
            }
        }

    }

// 检验合法性
    public boolean checkValid(int[] result,int n){
        for(int j = 0;j<n;j++){
            if(result[j] == result[n]){// 是否在同一条直线上
                return false;
            }else if(Math.abs(result[j]-result[n])==Math.abs(j-n)){//是否在同一条斜线上
                return  false;
            }
        }
        return true;
    }
相关标签: 安卓 安卓开发