八皇后问题

Bertha 。 2022-05-18 05:58 239阅读 0赞

在国际象棋中，皇后是最强大的一枚棋子，可以吃掉与其在同一行、列和斜线的敌方棋子.八皇后问题是这样一个问题：将八个皇后摆在一张8\*8的国际象棋棋盘上，使每个皇后都无法吃掉别的皇后，一共有多少种摆法？  
八皇后问题是典型的回溯法解决的问题,所谓回溯法，名字高大上，思想很朴素。设想把你放在一个迷宫里，想要走出迷宫，最直接的办法是什么呢？每条路尝试。先选一条路走起，走不通就往回退尝试别的路，走不通继续往回退，直到找到出口或所有路都试过走不出去为止。  
![queen][]

public class Solution {
        int n=8;     //八个皇后
        int total=0; //总共的解法
        int []c=new int[n];
        //八皇后问题共有92种解法(回溯法、递归实现)
        public void maxQueen(int row) {
              if(row==n){
                  total++;
              }
              else{
                 for(int col=0;col!=n;col++){
                  c[row]=col;
                  if(isOk(row))
                  {
                     maxQueen(row+1); //递归调用，进行下一行的安排
                  }
                 }
              }       
        }
        //判断一个位置是否可以放置皇后
        public boolean isOk(int row){
          for(int j=0;j!=row;j++){
             if((c[row]==c[j])||(row-c[row]==j-c[j])||(row+c[row]==j+c[j]))
                return false;
          }
          return true;
        }
    
        public static void main(String[]args){
          Solution s=new Solution();
          s.maxQueen(0);
          System.out.println(s.total);
        }
    }

![这里写图片描述][70]  
[参考文献1][1]  
[参考文献2][2]

[queen]: /images/20220518/e432426b88d24c76a5f2748401c39397.png
[70]: /images/20220518/3908330bce844de193392257355e7024.png
[1]: https://www.cnblogs.com/bigmoyan/p/4521683.html
[2]: https://blog.csdn.net/ns_code/article/details/26614999

发表评论取消回复

表情：

评论列表（有 0 条评论，239人围观）

还没有评论，来说两句吧...

相关阅读

相关八皇后问题

八皇后问题作者： Ackarlix 八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯 1850 年提出：在 8X8 格的国际象棋上

灰太狼/ 2022年09月19日 15:20/ 0 赞/ 46 阅读

相关八皇后问题

\include<stdio.h> \include<stdlib.h> \define max 8 int queen\[max\],s

﹏ヽ暗。殇╰゛Y/ 2022年08月07日 01:40/ 0 赞/ 203 阅读

相关八皇后问题

在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。试解出92种结果。 ![Cent

冷不防/ 2022年08月03日 00:49/ 0 赞/ 277 阅读

相关八皇后问题

一、问题描述 ![Center][] 在8x8的国际棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能同一行、同一列、同一斜线上。八皇后问题可以扩展为n

╰+哭是因爲堅強的太久メ/ 2022年07月14日 00:17/ 0 赞/ 232 阅读

相关八皇后问题

回溯法求解八皇后问题 n皇后问题：n皇后问题是指在一个n\n的国际象棋棋盘上放置n个皇后，使得这n个皇后两两不在同一行，同一列，同一条对角线上，求合法的方案数。如

小灰灰/ 2022年06月11日 08:49/ 0 赞/ 287 阅读

相关八皇后问题

枚举法 include<iostream> using namespace std; int a[9]; int check(int n,

蔚落/ 2022年06月06日 00:38/ 0 赞/ 240 阅读

相关八皇后问题

即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。由于皇后们是不能放在同一行的，所以我们可以去掉“行”这个因素，即我第1次考虑把皇后放在第1行的某

柔情只为你懂/ 2022年05月28日 01:47/ 0 赞/ 251 阅读

相关八皇后问题

　在国际象棋中，皇后是最强大的一枚棋子，可以吃掉与其在同一行、列和斜线的敌方棋子.八皇后问题是这样一个问题：将八个皇后摆在一张8\8的国际象棋棋盘上，使每个皇后都无法吃掉别的皇

Bertha 。/ 2022年05月18日 05:58/ 0 赞/ 240 阅读

相关八皇后问题

include <iostream> include <cmath> include <cstring> using namespace std

港控/mmm°/ 2022年01月31日 00:29/ 0 赞/ 308 阅读

相关八皇后问题

八皇后问题，以国际象棋为背景：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任意两个皇后都不能处于

叁歲伎倆/ 2021年09月25日 15:34/ 0 赞/ 477 阅读