C++实现八皇后问题的方法_C 语言

本文实例展示了C++实现八皇后问题的方法,是数据结构与算法中非常经典的一个算法。分享给大家供大家参考之用。具体方法如下:

一般在八皇后问题中,我们要求解的是一个8*8的国际象棋棋盘中,放下8个皇后且互相不能攻击的排列总数。皇后的攻击范围为整行,整列,以及其斜对角线。

由于皇后的攻击范围特性,注定我们每行只能放下一个皇后,于是我们要做的只是逐行放下皇后。八皇后问题是回溯法的典型问题。这里我们用的方法很简单:

从第一行开始逐个检索安全位置摆放皇后,一旦有安全位置则考虑下一行的安全位置。如果发现某行没有安全位置,则返回上一行继续检索安全位置;如果发现在最后一行找到了安全位置则输出整个棋盘。

原理很简单,整个程序中表现了这个思想的函数是void Solve()

下面是实现的代码:

 //八皇后问题的实现
#include <iostream>
#include <string>
using namespace std;
//QueenChess类声明
class QueenChess
{
   public:
       QueenChess();     //构造函数
       void Solve();     //求解八皇后问题,并给出放置成功的棋盘总个数
   private:
       string chessState[8];     //用于存放棋盘状态
       int solves;          //八个皇后放置成功的棋盘解的总个数
       bool SafeJudge(int row,int col) const;  //判断位置(row,col)是否安全
       void PlaceQueen(int row);         //在第row行放置一个皇后
       void DrawChess() const;          //打印八个皇后放置成功的棋盘
};

//构造函数,将棋盘初始化
QueenChess::QueenChess()
{
   solves=0;
   int i=0,j=0;
   for(;i<8;++i)
   chessState[i]="--------";
}

//求解八皇后问题,并给出放置成功的棋盘总个数
void QueenChess::Solve()
{
   //从第0行开始放置皇后
   PlaceQueen(0);
   cout<<"/n八皇后问题总共的解的个数是:"<<solves<<endl;
}

//在第row行的各列放置皇后
void QueenChess::PlaceQueen(int row)
{
   //穷尽第row行的所有列
   for(int col=0;col<8;col++)
   {
       if(SafeJudge(row,col))
       {
           //位置(row,col)安全,则放一皇后
           chessState[row][col]='Q';
           //若还没有放到第八行,则尝试下一行
           if(row<7)
            PlaceQueen(row+1);
           //已经放置了八个皇后,打印出成功的棋盘,并将解数加1
           else
           {
             solves++;
             DrawChess();
           }
       }//end if
       //不安全,将该处的皇后拿走,尝试下一列位置
       chessState[row]="--------";
   }
}

//判断是否(row,col)是安全位置
bool QueenChess::SafeJudge(int row,int col) const
{
   int qRow,qCol;
   //检查前面各行,看与前面的皇后是否发生攻击
   for(qRow=0;qRow<row;qRow++)
   {
      string rowState=chessState[qRow];
      //寻找第qRow行放置皇后的列数
      qCol=rowState.find("Q");
      //如果两个皇后在同一行、同一列或两条对角线上,则说明该位置不安全
      if(qRow==row||qCol==col||(qCol-qRow)==(col-row)||(qCol+qRow)==(col+row))
       return false;
   } //end if
   return true;
}

//打印成功的棋盘
void QueenChess::DrawChess() const
{
   int i,j;
   cout<<"/n八皇后问题的第"<<solves<<" 个解为:"<<endl;
   cout<<" 0 1 2 3 4 5 6 7"<<endl;
   for(i=0;i<8;++i)
   {
      cout<<i<<" ";
      for(j=0;j<8;++j)
      cout<<chessState[i][j]<<" ";
      cout<<endl;
   } //end for
   //每打印一个成功的八皇后棋盘,暂停一下
   //system("pause");
}

//main函数进行测试
int main()
{
  QueenChess chess;
  chess.Solve();
  system("pause");
  return 0;
}

希望本文所述实例对大家C++算法设计有所帮助。

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索c++
八皇后
八皇后问题 c语言、八皇后问题递归c语言、八皇后问题c语言 思路、八皇后问题 c语言代码、八皇后问题的图形实现,以便于您获取更多的相关知识。

时间: 2024-09-22 16:04:01

C++实现八皇后问题的方法_C 语言的相关文章

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

  本文实例讲述了python基于右递归解决八皇后问题的方法.分享给大家供大家参考.具体分析如下: 凡是线性回溯都可以归结为右递归的形式,也即是二叉树,因此对于只要求一个解的问题,采用右递归实现的程序要比回溯法要优美的多. ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 def Test(queen,n): '''这个就不用说了吧,就是检验第n(下标,0-7)行皇后的位置是否合理''' q=que

排列和组合算法的实现方法_C语言经典案例_C 语言

排列和组合算法是考查递归的常见算法,这两种算法能用递归简洁地实现. 本人在经过多次摸索和思考之后,总结如下,以供参考. 程序代码如下: #include <stdio.h> #include <stdlib.h> char array[] = "abcd"; #define N 4 #define M 3 int queue[N] = {0}; int top = 0; int flag[N] = {0}; void perm(int s, int n) { i

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

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

C语言通过深度优先搜索来解电梯问题和N皇后问题的示例_C 语言

N皇后问题问题描述: 在n×n格的棋盘上放置彼此不受攻击的n个皇后.按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子.n后问题等价于再n×n的棋盘上放置n个皇后,任何2个皇后不妨在同一行或同一列或同一斜线上. 需求输入: 给定棋盘的大小n (n ≤ 13) 需求输出: 输出有多少种放置方法. #include <stdio.h> #include <math.h> #define MAX 101 int total = 0; char m[MAX][MAX]

提高C++程序运行效率的10个简单方法_C 语言

本文以C/C++程序为例讲述了程序运行效率的10个简单方法,分享给大家供大家参考之用.具体分析如下: 对于每一个程序员来说,程序的运行效率都是一个值得重视,并为之付出努力的问题.但是程序性能的优化也是一门复杂的学问,需要很多的知识,然而并不是每个程序员都具备这样的知识,而且论述如何优化程序提高程序运行效率的书籍也很少.但是这并不等于我们可以忽略程序的运行效率,下面就介绍一下本人积累的一些简单实用的提高程序运行效率的方法,希望对大家有所帮助. 一.尽量减少值传递,多用引用来传递参数.至于其中的原因

使用C语言实现CRC校验的方法_C 语言

CRC(Cyclic Redundancy Check)校验应用较为广泛,以前为了处理简单,在程序中大多数采用LRC(Longitudinal Redundancy Check)校验,LRC校验很好理解,编程实现简单.用了一天时间研究了CRC的C语言实现,理解和掌握了基本原理和C语言编程.结合自己的理解简单写下来. 1.CRC简介 CRC检验的基本思想是利用线性编码理论,在发送端根据要传送的k位二进制码序列,以一定的规则产生一个检验码r位(就是CRC码),附在信息后面,构成一个新的二进制码序列数

使用WindowsAPI获取录音音频的方法_C 语言

本文实例介绍了使用winmm.h进行音频流的获取的方法,具体步骤如下: 一.首先需要包含以下引用对象 #include <Windows.h> #include "mmsystem.h" #pragma comment(lib, "winmm.lib") 二.音频的获取需要调用7个函数 1. waveInGetNumDevs:返回系统中就绪的波形声音输入设备的数量 UINT waveInGetNumDevs(VOID); 2. waveInGetDevC

C++实现将输入复制到输出的方法_C 语言

本文实例讲述了C++实现将输入复制到输出的方法.分享给大家供大家参考.具体实现方法如下: 将输入复制到输出的程序, 并将其中的制表符替换为\t, 把回退符替换为\b, 把反斜杠替按为\\ #include <stdio.h> main() { int ch; ch=getchar(); while(ch != EOF){ if(ch == '\t'){ putchar('\\'); putchar('t'); } else if(ch == '\b'){ putchar('\\'); putc

减小VC6编译生成的exe文件的大小的方法_C 语言

1.减小VC6编译生成的exe文件的大小,最有效的方法就是: 步骤: 1.使用release版本 2.代码中增加:#pragma comment(linker, "/OPT:nowin98 ") 3.project--> setting--> c/c++--> link-> 勾上Ignore all default libraries 4.project--> setting--> c/c++--> link-> object/libra