这两天看了下有关递归回溯的问题,自己写了一个八皇后的递归回溯求解答数量的程序,自己HI~一下。
?
#include <iostream> #include <cstring> using namespace std; const int MAX = 8; //棋盘大小 int G[MAX][MAX]; int solveNum = 0; int canPut(int _i,int _j){ int i,j; //up i = _i; j = _j; while(i>0){ if(!G[--i][j]) return 0; } //left up i = _i; j = _j; while(i>0 && j>0){ if(!G[--i][--j]) return 0; } //right up i = _i; j = _j; while(i>0 && j<MAX-1){ if(!G[--i][++j]) return 0; } return 1; } void Solve(int i,int j){ if(i == MAX){ solveNum++; }else{ if(canPut(i,j)){ G[i][j] = 0; Solve(i+1,0); G[i][j] = -1; //回溯 } if((j+1)<MAX) Solve(i,j+1); } } int main(){ memset(G , -1 , sizeof(G)); Solve(0,0); cout<<solveNum<<endl; return 0; }?