八皇后问题的进化(2)-用递归函数实现

我的思路是，先用递归函数找到一种解法。然后再用它找出所有的解法。这篇blog中是找出一种解法的基础递归版本。

除了递归函数外，大部分函数沿用的是《八皇后最基础实现》 中的内容，比如条件测试函数，棋盘 显示函数，因为它们不需要太多的“进化”。

运行结果如图：

 
/**
* The famous 8 queens problem.
*
* @file
* @brief
*		The famous 8 queens problem.
* @author		Gary Gao	<[e-mail]>
* @date   2011/06/26
*
*/
/*
**	约定：棋盘的坐标是行r0-r7,列c0-c7
*/
#include <stdio.h>
#define SUCCEEDED	  0
#define FAILED   	 -1
#define CHESSBD_WIDTH 8
//#define DEBUG_A
void show_chessbd();
int put_queen(int);
int search_next(int,int[],int[]);
int test(int[],int,int[],int);
int get_queen_pos(int);
int chessbd[CHESSBD_WIDTH][CHESSBD_WIDTH];
int row_marks[CHESSBD_WIDTH];
int col_marks[CHESSBD_WIDTH];
/**
* @brief 	main
*
*/
int main(int argc,char* argv[])
{
	put_queen(0);
	show_chessbd();
	return 0;
}
/**
* @brief 	解决八皇后问题的递归函数
*
* @param[in] 		r_pos				- 指定从第r_pos行寻找.
* @return								- 返回SUCCEEDED如果能够成功在当前行(r_pos)摆放皇后.否则返回FAILED.
*/
int put_queen(int r_pos)
{
	int ret;
	int search_ret ;
	int put_ret;
	if(r_pos == CHESSBD_WIDTH){
		ret = SUCCEEDED;	//基本
	}else{
		search_ret = search_next(r_pos,row_marks,col_marks);
		put_ret = FAILED;
		while(search_ret == SUCCEEDED && put_ret == FAILED){
			put_ret = put_queen(r_pos+1);
			if(put_ret == FAILED){
				search_ret = search_next(r_pos,row_marks,col_marks);
			}else{	//put_ret == SUCCEEDED
				ret = SUCCEEDED;
				break;
			}
		}
		if(search_ret == FAILED){	//程序运行到这里，说明在当前行(r_pos)没有找到摆放皇后的位置.
			ret = FAILED;
		}
	}
#ifdef DEBUG_A
	show_chessbd();
	printf("@Debug:/t/nsearch_ret:%4d,put_ret:%4d,r_pos:%4d,ret:%4d",search_ret,put_ret,r_pos,ret);
	getchar();
#endif
	return ret;
}
/**
* @brief 	摆放皇后——在指定行寻找下一个可以摆放皇后的位置,同时在找到后设置占用标记
*
* @param[in] 		r_num				- 被测试的Row positon.
* @param[in] 		row_marks			- 行占用标记.
* @param[in] 		col_marks			- 列占用标记.
* @return								- 返回SUCCEEDED如果能够成功摆放皇后.否则返回FAILED.
*/
int search_next(int r_pos,int row_marks[],int col_marks[] )
{
	int j;
	int c_pos;
	int test_ret = FAILED;
	//先撤销上次的标记
	c_pos = get_queen_pos(r_pos);
	if(chessbd[r_pos][c_pos] == 1)
	{
		chessbd[r_pos][c_pos] = 0;
		row_marks[r_pos] = 0;
		col_marks[c_pos] = 0;
		//
		c_pos++;
	}
	//然后寻找当前行(r_pos)新的皇后摆放位置
	for( j = c_pos ; j< CHESSBD_WIDTH ; j++ ){
		test_ret = test(row_marks,r_pos,col_marks,j );
		if(test_ret == SUCCEEDED){
			c_pos = j;
			break;
		}
	}
	//如果有满足条件(即可以摆放皇后)，设置皇后占用标记
	if(test_ret == SUCCEEDED){
		chessbd[r_pos][c_pos] = 1;
		row_marks[r_pos] = 1;
		col_marks[c_pos] = 1;
	}
	return test_ret;
}
/**
* @brief		显示棋盘
*
*/
void show_chessbd()
{
	int i,j;
	for(j = 0 ; j < CHESSBD_WIDTH; j++){
		if(j == 0){
			printf("%8d",j);
		}else{
			printf("%4d",j);
		}
		if(j == CHESSBD_WIDTH-1){
			printf("/n");
		}
	}
	for(i = 0 ; i < CHESSBD_WIDTH ; i++ ){
		printf("%4d",i);
		for(j = 0 ; j < CHESSBD_WIDTH ; j++){
			printf("%4d",chessbd[i][j]);
		}
		printf("/n/n");
	}
}
/**
* @brief 	测试给定的position是否满足摆放皇后的条件.
*
* @param[in] 		row_marks			- 行占用标记.
* @param[in] 		r_num				- 被测试的Row positon.
* @param[in] 		col_marks			- 列占用标记.
* @param[in] 		c_num				- 被测试的Column positon.
* @return								- 返回SUCCEEDED如果满足摆放皇后的条件.否则返回FAILED.
*/
int test(
		int row_marks[],int r_num,
		int col_marks[],int c_num
		)
{
	int ret;
	int i,j;
	ret = SUCCEEDED;
	//test row
	if(row_marks[r_num] == 1 ){
		ret = FAILED;
	}
	//test column
	if(col_marks[c_num] == 1 ){
		ret = FAILED;
	}
	//test主对角线
	i = r_num-1;
	j = c_num-1;
	for( i,j ; i >= 0  && j >= 0 ;i--,j--){
		if(chessbd[i][j] == 1){
			ret = FAILED;
			break;
		}
	}
	//test副对角线
	i = r_num-1;
	j = c_num+1;
	for(i,j ; i >= 0 && j < CHESSBD_WIDTH;i--,j++){
		if(chessbd[i][j] == 1){
			ret = FAILED;
			break;
		}
	}
	return ret;
}
/**
* @brief 	Get the position of queen in the specified row
*
* @param[in] 		row_num	- Row position.
* @return						- Column position of the queen in the specified row.
*/
int get_queen_pos(int row_num)
{
	int col;
	int j;
	//chessbd
	col = 0;
	for( j = 0 ; j < CHESSBD_WIDTH; j++){
		if( chessbd[row_num][j] == 1){
			col = j;
			break;
		}
	}
	return col;
}
/**
 * Log20110626:
 * 		用递归改写八皇后问题，找到一种解法。
 *
 */
 /*
  * Task20110626:
  * 	改写程序，找出所有的解法。
  * 	添加注释
  *		变量定义时的初始值（全局变量，局部变量）问题，因为一直不明晰，经常酿成大错。
  */