bahunghou.txt

从八皇后的例子看出搜速深度有限,仅有几层,而且不可能出现重复状态的问题,因此BACKTRACK过程完全适用,对于八数码问题则不然,必须设置深度范围限制及出现重复状态引起的死循环这两个回溯点.

下面通过对八皇后问题对递归算法做出进一步的了解:
　　 从八皇后的例子看出搜速深度有限,仅有几层,而且不可能出现重复状态的问题,因此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));
　　}