一、題意解析
國際象棋中的皇後，可以橫向、縱向、斜向移動。如何在一個8X8的棋盤上放置8個皇後，使得任意兩個皇後都不在同一條橫線、豎線、斜線方向上？八皇後問題是一個古老的問題，于1848年由一位國際象棋棋手提出：在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處于同一行、同一列或同一斜線上，如何求解？以高斯為代表的許多數學家先後研究過這個問題。後來，當計算機問世，通過計算機程式的運算可以輕松解出這個問題。
二、如何解決八皇後問題？
所謂遞歸回溯，本質上是一種枚舉法。這種方法從棋盤的第一行開始嘗試擺放第一個皇後，擺放成功後，遞歸一層，再遵循規則在棋盤第二行來擺放第二個皇後。如果目前位置無法擺放，則向右移動一格再次嘗試，如果擺放成功，則繼續遞歸一層，擺放第三個皇後......
如果某一層看遍了所有格子，都無法成功擺放，則回溯到上一個皇後，讓上一個皇後右移一格，再進行遞歸。如果八個皇後都擺放完畢且符合規則，那麼就得到了其中一種正确的解法。說起來有些抽象，我們來看一看遞歸回溯的詳細過程。
1.第一層遞歸，嘗試在第一行擺放第一個皇後：
2.第二層遞歸，嘗試在第二行擺放第二個皇後（前兩格被第一個皇後封鎖，隻能落在第三格）：
3.第三層遞歸，嘗試在第三行擺放第三個皇後（前四格被第一第二個皇後封鎖，隻能落在第五格）：
4.第四層遞歸，嘗試在第四行擺放第四個皇後（第一格被第二個皇後封鎖，隻能落在第二格）：
5.第五層遞歸，嘗試在第五行擺放第五個皇後（前三格被前面的皇後封鎖，隻能落在第四格）：
6.由于所有格子都“綠了”，第六行已經沒辦法擺放皇後，于是進行回溯，重新擺放第五個皇後到第八格。：
7.第六行仍然沒有辦法擺放皇後，第五行也已經嘗試遍了，于是回溯到第四行，重新擺放第四個皇後到第七格。：
8.繼續擺放第五個皇後，以此類推......
代碼：列印所有的擺放方法以及方法總數
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<sstream>
#include<iostream>
using namespace std;
int num=0;
void output(bool arr[8][8])
{
num++;
printf("\n");
for(int i=0;i<8;i++)
{
for(int j=0;j<8;j++)
printf("%d ",arr[i][j]);
printf("\n");
}
}
bool check(bool arr[8][8],int row,int column)///檢查落子是否合法，參數分别是行，列
{
if(row==0) ///第一行落子肯定合法
return true;
///一行隻擺一個就換行，是以不用判斷行是否合法
int i,j;///判斷同一列上有沒有棋子
for(i=0;i<row;i++)
{
if(arr[i][column])
return false;
}
i=row-1;
j=column-1;///判斷左上斜線是否有棋子
while(i>=0&&j>=0)
{
if( arr[i][j] )
{
return false;
}
i--;
j--;
}
i=row-1;
j=column+1;///判斷右上斜線是否有棋子
while(i>=0&&j<8)
{
if( arr[i][j] )
{
return false;
}
i--;
j++;
}
return true;
}
void slove(bool arr[8][8],int row)///回溯法，核心代碼
{///從第一行第一列開始擺放，如果合法就繼續擺，深度搜尋所有答案
for(int column=0;column<8;column++)
{
arr[row][column]=true;///擺下去先，再判斷是否落子合法
if( check(arr,row,column) )
{
if( row+1==8 ) ///擺到第八行，并且落子合法，則棋盤正确擺放了
output(arr);
else
slove(arr,row+1);///如果該落子合法，又沒有到第八行，則繼續下一行開擺
}
arr[row][column]=false;///不擺這一顆子，擺下一顆子進行深度搜尋
}
}
int main()
{
bool chess[8][8];
memset(chess,false,sizeof(chess));
slove(chess,0);
printf("num=%d\n",num);
return 0;
} 轉載于:https://www.cnblogs.com/shoulinniao/p/10260317.html