首页 > > 程序设计 > C/C++ >

八皇后问题

2018-06-17 21:12:16来源：未知阅读 ()

  1 #pragma once
  2 #ifndef _CHESS_HPP_
  3 #define _CHESS_HPP_
  4 #include<array>
  5 #include<stack>
  6 #include<tuple>
  7 #include<Paint/Nocopyable.h>
  8 #define Init   0
  9 #define Count  8
 10 typedef unsigned short int UInt16;
 11 typedef std::tuple<UInt16, UInt16, bool> IsHave;
 12 typedef std::array<std::array<UInt16, Count>, Count> Map;
 13 
 14 struct Chessman {
 15     UInt16 Row;
 16     UInt16 Col;
 17     static UInt16 Flag;
 18     virtual ~Chessman(){}
 19     Chessman() :Row(0), Col(0) {}
 20     Chessman(UInt16 row, UInt16 col) :Row(row), Col(col) {}
 21     IsHave Peek(Map &TheMap) {
 22         UInt16 row = Row;
 23         UInt16 col = Col;
 24         do{
 25             if (col < Count - 1)
 26                 ++col;
 27             else {
 28                 ++row;
 29                 col = 0;
 30             }
 31             if (row == Count)
 32                 return { 0,0,false };
 33         } while (TheMap[row][col] != Init);
 34         return { row,col,true };
 35     }
 36     void Capture(Map &TheMap) {
 37         ++Flag;
 38         for (size_t i = 0; i < Count; ++i)
 39             if (TheMap[i][Col] == Init)
 40                 TheMap[i][Col] = Flag;
 41         for (size_t i = 0; i < Count; ++i)
 42             if (TheMap[Row][i] == Init)
 43                 TheMap[Row][i] = Flag;
 44         if (Row == Col)
 45             for (size_t i = 0; i < Count; ++i)
 46                 if (TheMap[i][i] == Init)
 47                     TheMap[i][i] = Flag;
 48         if (Row + Col - 1 == Count)
 49             for (size_t i = 0; i < Count; ++i)
 50                 if (TheMap[i][Count - 1 - i] == Init)
 51                     TheMap[i][Count - 1 - i] = Flag;
 52     }
 53     void Revert(Map &TheMap) {
 54         for (size_t i = 0; i < Count; ++i)
 55             if (TheMap[i][Col] == Flag)
 56                 TheMap[i][Col] = Init;
 57         for (size_t i = 0; i < Count; ++i)
 58             if (TheMap[Row][i] == Flag)
 59                 TheMap[Row][i] = Init;
 60         if (Row == Col)
 61             for (size_t i = 0; i < Count; ++i)
 62                 if (TheMap[i][i] == Flag)
 63                     TheMap[i][i] = Init;
 64         if (Row + Col - 1 == Count)
 65             for (size_t i = 0; i < Count; ++i)
 66                 if (TheMap[i][Count - 1 - i] == Flag)
 67                     TheMap[i][Count - 1 - i] = Init;
 68         --Flag;
 69     }
 70 };
 71 UInt16 Chessman::Flag = Init;
 72 
 73 class ChessMap :Paint::Nocopyable{
 74 private:
 75     typedef std::stack<Chessman> CMstack;
 76 private:
 77     UInt16 Time;
 78     Map TheMap;
 79     CMstack TheStack;
 80 public:
 81     virtual ~ChessMap() {}
 82     ChessMap() :TheMap({ {Init} }), Time(0) {}
 83 public:
 84     CMstack Run() {
 85         Chessman CM;
 86         if (TheStack.empty()) {
 87             CM = { 0,0 };
 88             CM.Capture(TheMap);
 89             TheStack.push(CM);
 90         }
 91         else {
 92             CM = TheStack.top();
 93             CM.Revert(TheMap);
 94             TheStack.pop();
 95         }
 96         while (TheStack.size() != Count){
 97             auto XY = CM.Peek(TheMap);
 98             if (std::get<2>(XY)) {
 99                 CM = { std::get<0>(XY),std::get<1>(XY) };
100                 CM.Capture(TheMap);
101                 TheStack.push(CM);
102                 if (TheStack.size() == Count)
103                     Time++;
104                 continue;
105             }
106             else if (TheStack.empty())
107                 return {};
108             CM = TheStack.top();
109             CM.Revert(TheMap);
110             TheStack.pop();
111         }
112         return TheStack;
113     }
114 };
115 ChessMap EightQueens;
116 #endif //_CHESS_HPP_

 1 #include<iostream>
 2 #include"EightQueens.hpp"
 3 using namespace std;
 4 int main() {
 5     //EightQueens;
 6     for (int i = 0; i < 3; ++i) {
 7         auto Get = EightQueens.Run();
 8         while (!Get.empty()) {
 9             auto cm = Get.top();
10             cout << cm.Row << ends << cm.Col << endl;
11             Get.pop();
12         }
13         cout << endl;
14     }
15     system("pause");
16     return 0;
17 }