八皇后递归回溯解法_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 八皇后递归回溯解法

八皇后递归回溯解法

 2011/9/16 8:11:48  wanghailiang333  http://wanghailiang.iteye.com  我要评论(0)
  • 摘要:这两天看了下有关递归回溯的问题,自己写了一个八皇后的递归回溯求解答数量的程序,自己HI~一下。#include<iostream>#include<cstring>usingnamespacestd;constintMAX=8;//棋盘大小intG[MAX][MAX];intsolveNum=0;intcanPut(int_i,int_j){inti,j;//upi=_i;j=_j;while(i>0){if(!G[--i][j])return0;
  • 标签:递归

这两天看了下有关递归回溯的问题,自己写了一个八皇后的递归回溯求解答数量的程序,自己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;
}
?
发表评论
用户名: 匿名