^{<noscript id="69jaz"></noscript>}

八皇后問題（N皇后問題）

2019-11-08 03:08:01

字體：大中小

來源：轉載

供稿：網友

問題：在一個N*N的棋盤上擺放N個“皇后”，且兩兩不在同一直線和斜線上，求有多少種擺法

解法：使用遞歸和回溯的思想求解

代碼：

#include <iostream>using namespace std;const int N = 8;// N皇后問題int map[N][N];// 棋盤數組，存儲可直達該點的皇后個數static int methods = 0;// 遍歷的方法數bool put(int pi, int pj){ if (pi == N-1){ //return true;// 若需輸出其中一種解法，取消本行注釋即可 methods++; return false; } map[pi][pj] = N; for (int i = 0; i < N; i++){ for (int j = 0; j < N; j++){ if (i == pi || j == pj || i + j == pi + pj || i - j == pi - pj){// 橫縱斜線 map[i][j]++;// 可直達該點的皇后個數加1 } } } for (int j = 0; j < N; j++){ if (map[pi + 1][j] == 0){ if (put(pi + 1, j) == true){ return true; }// 下一行放置新的棋子 } } for (int i = 0; i < N; i++){ for (int j = 0; j < N; j++){ if (i == pi || j == pj || i + j == pi + pj || i - j == pi - pj){// 橫縱斜線 map[i][j]--;// 撤銷“可直達該點的皇后個數加1” } } } map[pi][pj] = 0; return false;}int main(){ for (int j = 0; j < N; j++){ if (put(0, j) == true){ for (int i = 0; i < N; i++){ for (int j = 0; j < N; j++){ if (map[i][j] == N + 1)// “自增1”過1次 cout << "●";// 此處放棋子 else cout << "○";// 此處為空 } cout << endl; } return 1; } } cout << "Kinds of handgrasp:" << methods << endl; return 0;}

上一篇：數據結構實驗之棧六：下一較大值（二）

下一篇：圖結構練習——最短路徑（Dijkstra算法）