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

时间:2021-08-20 12:51:30

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

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

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

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

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

下面是实现的代码:

 

?
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//八皇后问题的实现
#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++算法设计有所帮助。