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++算法設計有所贊助。