八皇后问题实现代码分享

main.cpp


代码如下:

#include<iostream>
#include<cstring>

using namespace std;

const int N = 7;

int count = 0;

void QueenPrint(int LayOut[N][N])  //打印结果
{
 cout<<"第"<<++count<<"种布局："<<endl;
 for(int i = 0; i < N; i++)
 {
  for(int j = 0; j < N; j++)
  {
   if(LayOut[i][j] == 1)
   {
     cout<<' '<<'Q'<<' ';
   }
   else
   {
    cout<<' '<<'*'<<' ';
   }
  }
  cout<<endl;
 }
 cout<<endl;
}
bool Queen(int LayOut[N][N], const int i, const int j)  //判断LayOut[i][j]是否适合放置皇后
{
 int k1 = 0;
 for(; k1 < N; k1++)   //判断该行有没有皇后
 {
  if(LayOut[i][k1] == 1)
  {
   return false;
  }
 }
 int k2 = 0;
 for(; k2 < N; k2++ )  //判断该列有没有皇后
 {
  if(LayOut[k2][j] == 1)
  {
   return false;
  }
 }

int t1 = i,t2 = j;                   //判断左上有没有皇后
 for(;t1 >= 0 && t2 >= 0;t1--,t2-- ) 
 {
   if(LayOut[t1][t2] == 1)
  {
   return false;
  }
 }

int n1 = i, n2 = j;                 //判断右上有没有皇后
 for(;n1 >= 0 && n2 < N;n1--,n2++ )
 {
   if(LayOut[n1][n2] == 1)
  {
   return false;
  }
 }

return true;
}
/*
void EightQueen(int LayOut[N][N],int i, int j) // i为行，j为列
{

if( i < N  )
 {
   if( j < N)
   {
    if(Queen(LayOut,i,j))
    {
     LayOut[i][j] = 1;
     j = 0;
     EightQueen(LayOut,i+1, j);
    }
    else
    {
     EightQueen(LayOut,i, j+1);

}

}
 }
 else
 {
  QueenPrint(LayOut);
 }

}*/

void EightQueen(int LayOut[N][N],int i) // i为行
{ 
 if( i == N)
 {
  QueenPrint(LayOut);
  //memset( LayOut, 0, sizeof(LayOut));
 }
 else
 {

int j = 0;
  for( ; j < N; j++ )
  {
   if( Queen( LayOut, i, j))
   {
    LayOut[i][j] = 1;
    EightQueen( LayOut,i+1);
    LayOut[i][j] = 0;
   } 
  }

}
}

int main()
{
 int LayOut[N][N];
 memset( LayOut, 0, sizeof(LayOut));
 EightQueen(LayOut,0);
 cout<<"共"<<count<<"中结果！"<<endl;
 return 0;
}

赞 (0)

相关推荐

  • 八皇后问题的相关C++代码解答示例

    八皇后问题的相关C++代码解答示例

    八皇后问题即指在一个8*8的棋盘上放置8个皇后,不允许任何两个皇后在棋盘的同一行.同一列和同一对角线上.关键字:递归.上溯.通用技巧: 经观察发现,对8 x 8的二维数组上的某点a[i][j](0<=i,j<=7) 其主对角线(即左上至右下)上的每个点的i-j+7的值(范围在(0,14))均相等: 其从对角线(即右上至左下)上的每个点的i+j的值(范围在(0,14))均相等: 且每个主对角线之间的i-j+7的值均不同,每个从对角线之间的i-j+7的值亦不同: 如a[3][4]: 主:3-4+7

  • javascript递归回溯法解八皇后问题

    下面给大家分享的是回溯法解八皇后, 带详细注解,这里就不多废话了. function NQueens(order) { if (order < 4) { console.log('N Queens problem apply for order bigger than 3 ! '); return; } var nQueens = []; var backTracking = false; rowLoop: for (var row=0; row<order; row++) { //若出现ro

  • C++实现八皇后问题的方法

    本文实例展示了C++实现八皇后问题的方法,是数据结构与算法中非常经典的一个算法.分享给大家供大家参考之用.具体方法如下: 一般在八皇后问题中,我们要求解的是一个8*8的国际象棋棋盘中,放下8个皇后且互相不能攻击的排列总数.皇后的攻击范围为整行,整列,以及其斜对角线. 由于皇后的攻击范围特性,注定我们每行只能放下一个皇后,于是我们要做的只是逐行放下皇后.八皇后问题是回溯法的典型问题.这里我们用的方法很简单: 从第一行开始逐个检索安全位置摆放皇后,一旦有安全位置则考虑下一行的安全位置.如果发现某行没

  • c++递归实现n皇后问题代码(八皇后问题)

    还是先来看看最基础的8皇后问题: 在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 扩展到N皇后问题是一样的.一看,似乎要用到二维数组.其实不需要.一维数组就能判断,比如Arr[i],就可以表示一个元素位于第i行第Arr[i]列--应用广泛的小技巧.而且在这里我们不用考虑去存储整个矩阵,如果Arr[i]存在,那么我们在打印的时候,打印到皇后位置的时候输出1,非皇后位输出0即可. 这种思路的实现方式网上大把,包括前面提到的那

  • C#用递归算法解决八皇后问题

    C#用递归算法解决八皇后问题

    1.引子 中国有一句古话,叫做"不撞南墙不回头",生动的说明了一个人的固执,有点贬义,但是在软件编程中,这种思路确是一种解决问题最简单的算法,它通过一种类似于蛮干的思路,一步一步地往前走,每走一步都更靠近目标结果一些,直到遇到障碍物,我们才考虑往回走.然后再继续尝试向前.通过这样的波浪式前进方法,最终达到目的地.当然整个过程需要很多往返,这样的前进方式,效率比较低下. 2.适用范围 适用于那些不存在简明的数学模型以阐明问题的本质,或者存在数学模型,但是难于实现的问题. 3.应用场景 在

  • python基于右递归解决八皇后问题的方法

    本文实例讲述了python基于右递归解决八皇后问题的方法.分享给大家供大家参考.具体分析如下: 凡是线性回溯都可以归结为右递归的形式,也即是二叉树,因此对于只要求一个解的问题,采用右递归实现的程序要比回溯法要优美的多. def Test(queen,n): '''这个就不用说了吧,就是检验第n(下标,0-7)行皇后的位置是否合理''' q=queen[n] for i in xrange(n): if queen[i]==q or queen[i]-q==n-i or queen[i]-q==i

  • JavaScript解八皇后问题的方法总结

    JavaScript解八皇后问题的方法总结

    关于八皇后问题的 JavaScript 解法,总觉得是需要学习一下算法的,哪天要用到的时候发现真不会就尴尬了 背景 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上 八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为 n×n ,而皇后个数也变成n .当且仅当n = 1或n ≥ 4时问题有解 盲目的枚举算法 通过N重循环,枚举满足约束条件的解(

  • java实现八皇后问题示例分享

    java实现八皇后问题示例分享

    问题描述:将八个皇后放在棋盘上,任何两个皇后都不能互相攻击(即没有任何两个皇后在同一行.同一列或者同一对角线上)如图所示   在本文中,对于两道题采用了稍微不同的解决方式,但都使用的是一维数组.6.20中,要求求出一种有效布局,我建立了一个 有八个元素的一位数组,通过随意打乱数组的值,通过值与下标的比较,直至得出一个有效布局:6.22中,要求求出所有有效布局,这里我使用了八进制数,遍历了  从001234567-076543210的所有数字,通过将其转化为八进制字符串,每位与其下标相比较,输出满

  • 八皇后问题实现代码分享

    main.cpp 复制代码 代码如下: #include<iostream>#include<cstring> using namespace std; const int N = 7; int count = 0; void QueenPrint(int LayOut[N][N])  //打印结果{ cout<<"第"<<++count<<"种布局:"<<endl; for(int i = 0

  • Python实现八皇后问题示例代码

    八皇后问题描述 问题: 国际象棋棋盘是8 * 8的方格,每个方格里放一个棋子.皇后这种棋子可以攻击同一行或者同一列或者斜线(左上左下右上右下四个方向)上的棋子.在一个棋盘上如果要放八个皇后,使得她们互相之间不能攻击(即任意两两之间都不同行不同列不同斜线),求出一种(进一步的,所有)布局方式. 首先,我们想到递归和非递归两类算法来解决这个问题.首先说说递归地算法. 很自然的,我们可以基于行来做判断标准.八个皇后都不同行这是肯定的,也就说每行有且仅有一个皇后,问题就在于皇后要放在哪个列.当然八个列下

  • C语言八皇后问题解决方法示例【暴力法与回溯法】

    本文实例讲述了C语言八皇后问题解决方法.分享给大家供大家参考,具体如下: 1.概述: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上. 2.暴力法求解: #include<cstdio> #include<cmath> const int maxn=11; int count=0; //P为当前排列,hashTable记录整数x是否已经在

  • C++基于回溯法解决八皇后问题示例

    C++基于回溯法解决八皇后问题示例

    本文实例讲述了C++基于回溯法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯:否则,进入该子树,继续按深度优先策略搜索. 回溯法指导思想--走不通,就掉头.设计过程:确

  • Python解决八皇后问题示例

    Python解决八皇后问题示例

    本文实例讲述了Python解决八皇后问题的方法.分享给大家供大家参考,具体如下: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上.八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2.而且仅当 n2 = 1 或 n1 ≥ 3 时问题有解. 这是一个典型的回溯算法,我们可以将问题进行分解: 首先,我们要想到某种方

  • C语言基于回溯算法解决八皇后问题的方法

    C语言基于回溯算法解决八皇后问题的方法

    本文实例讲述了C语言基于回溯算法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 问题描述: 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例:在8X8格的国际象棋棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 问题求解: 采用回溯算法,即从第一行开始,依次探查可以放置皇后的位置,若找到,则放置皇后,开始探查下一行:若该行没有位置可以放置皇后,则回溯至上一行,清除该行放置皇后的信息,从该行原本放置皇后的下一个位置开始探查可

  • python八皇后问题的解决方法

    本文为大家分享了python八皇后问题的解决方法,供大家参考,具体内容如下 题目: 给定一个 N*N 正方形棋盘,在上面放置 N个棋子,又叫皇后,使每两个棋子都不在同一条横线上.竖线上.斜线上.一般我们都讨论8皇后,但是只要N > 4,都会存在解的. 分析: 方法1:根据定义来处理,即每往棋盘中放置皇后的时候,都要判断哪些位置可以放新加入的皇后,而哪些地方如果放置皇后的话,会造成冲突.我下面写的这个代码就是基于此. 方法2.我看了下别人的优化,主要是采用位运算来实现计算复杂度降低的,我没有用Py

随机推荐