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

本文实例讲述了C语言基于回溯算法解决八皇后问题的方法。分享给大家供大家参考，具体如下：

问题描述：

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例：在8X8格的国际象棋棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

问题求解：

采用回溯算法，即从第一行开始，依次探查可以放置皇后的位置，若找到，则放置皇后，开始探查下一行；若该行没有位置可以放置皇后，则回溯至上一行，清除该行放置皇后的信息，从该行原本放置皇后的下一个位置开始探查可以放置皇后的位置。求所有解时，每找到一组解，就清除这一组解最后一个皇后的位置信息，开始探查该行另外一个可以放置皇后的位置，依次回溯求解。

存储结构：

一维数组：col[8]：存放第i列有无皇后的标记信息
一维数组：left[15]：存放每一条左斜线上的有无皇后的标记信息
一维数组：right[15]：存放每一条右直线上有无皇后的标记信息
一维数组：Q[8]：存放第i行的皇后的列下标

代码实现：

#include<stdio.h>
#define N 8
int col[N] = { 0 };
int right[2 * N - 1] = { 0 };
int left[2 * N - 1] = { 0 };
int Q[N];
int cnt = 0;
void Print()
{
  int i;
  for (i = 0; i < N; i++)
  {
    for (int j = 0; j < N; j++)
    {
      if (Q[i] == j)
        printf("■");
      else
        printf("□");
    }
    printf("\n");
  }
  printf("==========================\n");
  cnt++;
}
void Queen(int i)
{
  int j;
  for (j = 0; j < N; j++)
  {
    if ((!col[j]) && (!left[i + j]) && (!right[7 + i - j]))
    {
      Q[i] = j;//放皇后
      col[j] = 1;
      left[i + j] = 1;
      right[N - 1 + i - j] = 1;//已有皇后的标记
      if (i < N - 1)
      {
        Queen(i + 1);
      }
      else
      {
        Print();
      }
      col[j] = 0;
      right[N - 1 + i - j] = 0;
      left[i + j] = 0;//清除标记，查找下一组解
    }
  }
}
int main(void)
{
  Queen(0);
  printf("%d", cnt);
  getchar();
  return 0;
}

运行结果：

一共92组解，前面结果略去。。

希望本文所述对大家C语言程序设计有所帮助。

赞 (0)

相关推荐

  • 利用C语言解决八皇后问题以及解析

    利用C语言解决八皇后问题以及解析

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

  • PHP基于回溯算法解决n皇后问题的方法示例

    本文实例讲述了PHP基于回溯算法解决n皇后问题的方法.分享给大家供大家参考,具体如下: 这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题. 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向

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

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

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

  • 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

  • python 使用递归回溯完美解决八皇后的问题

    八皇后问题描述:在一个8✖️8的棋盘上,任意摆放8个棋子,要求任意两个棋子不能在同一行,同一列,同一斜线上,问有多少种解法. 规则分析: 任意两个棋子不能在同一行比较好办,设置一个队列,队列里的每个元素代表一行,就能达到要求 任意两个棋子不能在同一列也比较好处理,设置的队列里每个元素的数值代表着每行棋子的列号,比如(0,7,3),表示第一行的棋子放在第一列,第二行的棋子放在第8列,第3行的棋子放在第4列(从0开始计算列号) 任意两个棋子不能在同一斜线上,可以把整个棋盘当作是一个XOY平面,原点在

  • Java使用递归回溯完美解决八皇后的问题

    Java使用递归回溯完美解决八皇后的问题

    八皇后问题 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例.该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 解决思路 ①第一个皇后先放第一行第一列. ②第二个皇后放在第二行第一列.然后判断是否OK,如果不0K, 继续放在第二列.第三列.依次把所有列都放完,找到一个合适. ③继续第三个皇后, 还是第一列.第二列-直到第8个皇后也能放在一个不冲突的位置,算是找

  • C语言基于贪心算法解决装箱问题的方法

    本文实例讲述了C语言基于贪心算法解决装箱问题的方法.分享给大家供大家参考,具体如下: 问题描述: 有一些箱子,容量为V,同时有n个物品,每个物品有一个体积(小于等于箱子容量),要求将物品全部装入箱子中,使占用的箱子数尽量少. 贪心算法中要求每一步的解都是当前步骤中的最优解.原问题的解可以通过一系列局部最优的选择来达到,这种选择并不依赖于子问题的解. 算法思想: 1.数据结构 要求求解箱子数目,也就是说不能确定会占用多少个箱子,因此采用链表的形式来存储箱子及其信息. 同时,每个箱子中物品的数目也无

  • Python解决八皇后问题示例

    Python解决八皇后问题示例

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

  • C语言回溯法解八皇后问题(八皇后算法)

    C语言回溯法解八皇后问题(八皇后算法)

    八皇后问题(N皇后问题)的回溯法求解 一.问题描述 在一个国际象棋棋盘上放置八个皇后,使得任何两个皇后之间不相互攻击,求出所有的布棋方法,并推广到N皇后情况. 二.参考资料 啥文字都不用看,B站上有个非常详细的动画视频解说,上链接!!! Click Here! 三.源代码 #include<iostream> #include<vector> #include<string> using namespace std; void put_queen(int x, int

  • Python基于回溯法解决01背包问题实例

    Python基于回溯法解决01背包问题实例

    本文实例讲述了Python基于回溯法解决01背包问题.分享给大家供大家参考,具体如下: 同样的01背包问题,前面采用动态规划的方法,现在用回溯法解决.回溯法采用深度优先策略搜索问题的解,不多说,代码如下: bestV=0 curW=0 curV=0 bestx=None def backtrack(i): global bestV,curW,curV,x,bestx if i>=n: if bestV<curV: bestV=curV bestx=x[:] else: if curW+w[i]

随机推荐