//八皇后問題的實(shí)現(xiàn)
#include <iostream>
#include <string>
using namespace std;
//QueenChess類聲明
class QueenChess
{
   public:
       QueenChess();     //構(gòu)造函數(shù)
       void Solve();     //求解八皇后問題，并給出放置成功的棋盤總個(gè)數(shù) 
   private:
       string chessState[8];     //用于存放棋盤狀態(tài)
       int solves;          //八個(gè)皇后放置成功的棋盤解的總個(gè)數(shù)
       bool SafeJudge(int row,int col) const;  //判斷位置(row,col)是否安全
       void PlaceQueen(int row);         //在第row行放置一個(gè)皇后
       void DrawChess() const;          //打印八個(gè)皇后放置成功的棋盤 
};

//構(gòu)造函數(shù)，將棋盤初始化
QueenChess::QueenChess()
{
   solves=0;
   int i=0,j=0;
   for(;i<8;++i)
   chessState[i]="--------";
}

//求解八皇后問題，并給出放置成功的棋盤總個(gè)數(shù)
void QueenChess::Solve()
{
   //從第0行開始放置皇后
   PlaceQueen(0);
   cout<<"/n八皇后問題總共的解的個(gè)數(shù)是："<<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);
           //已經(jīng)放置了八個(gè)皇后，打印出成功的棋盤，并將解數(shù)加1
           else
           {
             solves++;
             DrawChess();
           } 
       }//end if
       //不安全，將該處的皇后拿走，嘗試下一列位置
       chessState[row]="--------"; 
   } 
}

//判斷是否(row,col)是安全位置
bool QueenChess::SafeJudge(int row,int col) const
{
   int qRow,qCol;
   //檢查前面各行，看與前面的皇后是否發(fā)生攻擊
   for(qRow=0;qRow<row;qRow++)
   {
      string rowState=chessState[qRow];
      //尋找第qRow行放置皇后的列數(shù)
      qCol=rowState.find("Q");
      //如果兩個(gè)皇后在同一行、同一列或兩條對(duì)角線上，則說明該位置不安全
      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<<" 個(gè)解為："<<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
   //每打印一個(gè)成功的八皇后棋盤，暫停一下
   //system("pause"); 
}

//main函數(shù)進(jìn)行測(cè)試 
int main()
{
  QueenChess chess;
  chess.Solve();
  system("pause");
  return 0; 
}