现在的位置: 首页 > 综合 > 正文

8皇后问题(递归方法实现)

2018年03月16日 ⁄ 综合 ⁄ 共 1885字 ⁄ 字号 评论关闭

8皇后问题实现思路:用一个二维数组board[8][8]来表示棋盘、二维数组中的元素来表示方格,因此board[0][0]、board[0][1]、、、board[7][7]一共64个元素分别代表棋盘上64个方块。board[i][j]=1代表棋盘上第i行第j列的方格放置皇后了,board[i][j]=0代表棋盘上第i行第j列的方格没有皇后,其中0<=i<=7,0<=j<=7。

皇后的攻击范围见下图(5角星代表皇后):


   程序实现见源代码:

#include"iostream"
using namespace std;
#include "stdlib.h"

#define  QUEUE_NUM	8
#define  QUEUE		1
#define	 NO_QUEUE	0

void handle(void);

int main(void)
{
	handle();
	return 0;
}


//判断当前位置所在的列、斜线上是否安全 安全返回true 不安全返回false
bool is_safe(bool(*board)[QUEUE_NUM],int row,int col)
{
	bool col_flag = false;
	bool diag_flag = false;

	//当前位置所在的列是否有皇后
	for(int i=0;i<QUEUE_NUM;i++)
	{
		if(board[i][col] ==	QUEUE)
		{
			col_flag = true;
			break;
		}
	}
    //当前位置所在的斜线上是否有皇后
	for(int i=0;i<QUEUE_NUM;i++)
	{
		for(int j=0;j<QUEUE_NUM;j++)
		{
			if(abs(j-col) == abs(i-row))		//在一条斜线上时斜率相等
			{
				if(board[i][j] == QUEUE)
				{
					diag_flag = true;
					break;
				}
			
			}
		}
	}
	
	if(col_flag || diag_flag)
	{
		return false;
	}
	else
	{
		return true;
	}
}



/************************************************************************
(*board)[QUEUE_NUM]:				指向棋盘行的指针  
row:								在第row行放置皇后	
scheme_num:						摆放的方案数
/************************************************************************/

void queue(bool(*board)[QUEUE_NUM],int row,int& scheme_num)
{
	//另开辟存储空间,存储当前方案。避免修改以前的方案
	bool cur_board[QUEUE_NUM][QUEUE_NUM];
	
	for(int i=0;i<QUEUE_NUM;i++)
	{
		for(int j=0;j<QUEUE_NUM;j++)
		{
			cur_board[i][j] =board[i][j];
		}
	}
	
	if(QUEUE_NUM == row)
	{
		//皇后已经放置完,输出当前方案
		scheme_num++;
		cout<<"第"<<scheme_num<<"种放置方案:"<<endl;
		for(int i=0;i<QUEUE_NUM;i++)
		{
			for(int j=0;j<QUEUE_NUM;j++)
			{
				cout<<cur_board[i][j]<<' ';
			}
			cout<<endl;
		}
		cout<<endl<<endl;
	}
	else
	{
		for(int col=0;col<QUEUE_NUM;col++)
		{
			//判断当前位置所在的列与斜线上是否危险
			if(is_safe(cur_board, row, col))
			{	
				//保证当前位置所在的行没有皇后
				for(int j=0;j<col;j++)
				{
					cur_board[row][j] = NO_QUEUE;
				}
				//在当前位置放置皇后
				cur_board[row][col] = QUEUE;
				queue(cur_board,row+1,scheme_num);
			}
		}
	
	}
}

void handle(void)
{
	//board是一个二维数组用来表示一个棋盘、元素为1表示该位置已经放置了皇后、为0表示该位置没有放置皇后
	bool board[QUEUE_NUM][QUEUE_NUM];
	for(int row=0;row<QUEUE_NUM;row++)
	{
		for(int col=0;col<QUEUE_NUM;col++)
		{
			board[row][col] =NO_QUEUE;
		}
	}
	int scheme_num = 0;
	queue( board, 0, scheme_num);
}

抱歉!评论已关闭.