概述

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

思路

采用递归回溯法，在判断方案不可行时，及时中止本次递归。八皇后问题实际是组合问题的应用，对于初学者可以先参考本博客的基础组合问题（从1~9选取数字）。 八皇后问题，可以演变为N皇后，M方格问题，只需要修改源码中的全局变量进行配置。

源码

本文主要是以C、C++、QT为基础进行编程，运行前简单修改即可。测试入口函数为 void Test_EightQueens()。

/* 用于表示64方格的具体位置 */ /********************** 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 **********************/ //********************************************** quint32 QUEEN_SUM = 8;//皇后个数 quint32 POSITION_SUM = 64;//方格个数 quint64 g_ResultSum = 0; //用于输出具体位置 void Queen_Output(int *pPo) { static quint8 print_num = 0; QString str; if(NULL == pPo) { ERROR_DEBUG; return; } if(print_num>=10) { return; } for(quint32 i=0; i<QUEEN_SUM; i++) { str += QString::number(pPo[i]); str += " "; } qDebug()<<str; } //用于判断本次方案是否可行 bool Queen_IsPositionValid(int *pPo, quint32 selectNum, quint32 newPo) { quint32 u32Po,i=0; quint8 u8Line1 = 0, u8LineNew = 0; quint32 LINE_MAX = (quint32)sqrt(POSITION_SUM); if(NULL == pPo || selectNum >= QUEEN_SUM) { ERROR_DEBUG; return false; } while(i<selectNum) { u32Po = pPo[i++]; u8Line1 = (u32Po-1)/LINE_MAX; u8LineNew = (newPo-1)/LINE_MAX; if(u8Line1 == u8LineNew)//同行 { return false; } if(newPo%LINE_MAX == u32Po%LINE_MAX)//同列 { return false; } //Diagonal相同 if(abs(u32Po%LINE_MAX - newPo%LINE_MAX) == abs(u8Line1-u8LineNew)) { return false; } } return true; } bool Queen_GetResult(quint32 startPostion, quint32 positionSum, int *pPo, quint32 index) { if(NULL == pPo || index >= QUEEN_SUM) { ERROR_DEBUG; return false; } for(quint32 i=startPostion; i<=positionSum; i++) { if(!Queen_IsPositionValid(pPo, index, i)) { continue;//位置不合法 } pPo[index] = i; if(index < (QUEEN_SUM-1))//还没有找全 { if(!Queen_GetResult(i+1, positionSum, pPo, index+1)) { return false; } } else//已找到所有皇后的位置 { g_ResultSum++; Queen_Output(pPo); } } return true; } void Test_EightQueens() { int a[QUEEN_SUM];//用于临时存储 Queen_GetResult(1, POSITION_SUM, a, 0); qDebug()<<"g_ResultSum: "<<g_ResultSum; }

运行结果

方案数量：g_ResultSum: 92 具体方案，可以自行运行查看。