下面通过对八皇后问题对递归算法做出进一步的了解:
从八皇后的例子看出搜速深度有限,仅有几层,而且不可能出现重复状态的问题,因此BACKTRACK过程完全适用,对于八数码问题则不然,必须设置深度范围限制及出现重复状态引起的死循环这两个回溯点.
下面 是八皇后的程序代码:
#include <iostream>
using namespace std;
const int SIDELEN = 8;
int qunPsn[SIDELEN + 1]; //in order to caculate easily, we start the array from index 1st
int pRow = 0;
int count;
bool Safty(int clnPsn, int Row);
int Abs(int tmp);
int main()
{pRow = 1;
/*initialize the array*/
for (int i = 0; i < SIDELEN + 1; i ++) qunPsn[i] = 0;
count = 0;
do
{qunPsn[pRow]++;
while(qunPsn[pRow] <= SIDELEN && !Safty(qunPsn[pRow], pRow)) qunPsn[pRow]++;
if (qunPsn[pRow] <= SIDELEN && pRow == 8) count++;
else if (qunPsn[pRow] <= SIDELEN && pRow < 8) pRow++;
else qunPsn[pRow--] = 0;
}while(pRow);
cout << "TotalMethod = " << count << endl;
char tmp;
cin >> tmp;
return 0;
}
bool Safty(int clnPsn, int row)
{
for(int i = 1; i < row; i++)
{if ( qunPsn[i] == clnPsn || Abs(clnPsn - qunPsn[i]) == Abs(row - i) ) return false;
}
return true;
}
int Abs(int tmp)
{
return (tmp > 0 ? tmp : (0 - tmp));
}
