宁波网站优化公司价格,wordpress主题评论制作,织梦建设网站需要什么软件,网站定制制作八皇后问题说明
八皇后问题#xff0c;是一个古老而著名的问题#xff0c;是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯贝瑟尔于 1848 年提出#xff1a;在 88 格的国际象棋上摆放八个皇后#xff0c;使其不能互相攻击#xff0c;即#xff1a;任意两个皇后都不…八皇后问题说明
八皇后问题是一个古老而著名的问题是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出在 8×8 格的国际象棋上摆放八个皇后使其不能互相攻击即任意两个皇后都不能处于同一行、同一列或同一斜线上问有多少种摆法。
思路分析
第一个皇后先放第一行第一列第二个皇后放在第二行第一列然后判断是否OK如果不OK继续放在第二列、第三列依次把所有列都放完找到一个合适的位置继续第三个皇后还是第一列、第二列…直到第8个皇后也能放在一个不冲突的位置算是找到了一个正确解当得到一个正确解时在栈回退到上一个栈时就会开始回溯即将第一个皇后放到第一列的所有正确解全部得到。然后回头继续第一个皇后放第二列后面继续循环 1,23,4 的步骤
代码实现如下
public class EightQueens {private static final int N 8; //棋盘大小为8x8private static int[] queens new int[N];// 一维数组表示每一行皇后所在的列数private static int count 0;//编写一个 main 方法public static void main(String[] args) {solve(0); //从第 0 行开始放置皇后System.out.println(最多有 count 种排序);}//递归处理皇后在每行的位置并放到 queens数组中private static void solve(int row){if( row N ){ //所有行都放置好了皇后找到一个解print();return;}for(int col 0; col N; col){if (isSafe(row, col)) { // 当前位置安全可以放置皇后queens[row] col; // 在当前行将皇后放在第col列solve(row 1); // 递归放置下一行的皇后}}}//判断是否在每一行、每一列、对角线private static boolean isSafe(int row, int col) {// 检查当前位置是否安全for (int i 0; i row; i) {// 检查是否同一列或者同一对角线上已经存在皇后if (queens[i] col || queens[i] - col i - row || queens[i] - col row - i) {return false; // 不安全}}return true; // 安全}//打印输出全部解private static void print(){count;for(int i 0; i N; i){System.out.print(queens[i] );}System.out.println();}}执行结果
