程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++完成八皇後成績的辦法

C++完成八皇後成績的辦法

編輯:關於C++

C++完成八皇後成績的辦法。本站提示廣大學習愛好者:(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++算法設計有所贊助。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved