欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言八皇后问题

程序员文章站 2022-03-19 20:55:11
在国际象棋里面,皇后是最具有杀伤力的武器,它可以对它的十字形和对角线元素进行攻击。八皇后问题就是在8*8的棋盘上的每一行都放置一个皇后,使他们无法进行互相攻击。 思路: 1.编...

在国际象棋里面,皇后是最具有杀伤力的武器,它可以对它的十字形和对角线元素进行攻击。八皇后问题就是在8*8的棋盘上的每一行都放置一个皇后,使他们无法进行互相攻击。

思路:

1.编写一个函数,将一个皇后放在第一列,如果存在攻击就把皇后放在第二列,如果每列都存在互相攻击的情况,则这个函数返回

2.若皇后可以放在这个位置,则应该递归的调用本身,把皇后放在下一行,当递归函数返回时候,就证明本行这个位置放置导致下一行皇后无处可放,则将本行皇后向后移动一个位置,判断是否可以放置皇后,如果可以则进入递归函数里面,若不可以则在将本行皇后向后挪动一列

首先我们应该编写检查函数:

int isSafe(int (*chess)[EIGHT], int row, int col)
{
	int rowIndex;
	int colIndex;
	
	for(rowIndex = row-1; rowIndex >= 0; rowIndex--){//直上方
			if(chess[rowIndex][col])
				return FALSE;
void eightQueen(int (*chess)[EIGHT], int row) { int colIndex; if(row >= EIGHT){ showChess(chess); } else{ for(colIndex = 0; colIndex < EIGHT; colIndex++){ //chess[row][colIndex] = 1; if(isSafe(chess, row, colIndex) == TRUE){//如果可以放置皇后 chess[row][colIndex] = 1;//放置皇后 eightQueen(chess, row+1);//进行递归 chess[row][colIndex] = 0;//递归返回时,证明此列不适合,下一列放置皇后 } } } }

递归函数:
void eightQueen(int (*chess)[EIGHT], int row)
{

	int colIndex;
	
	if(row >= EIGHT){
		showChess(chess);
	}
	else{
		for(colIndex = 0; colIndex < EIGHT; colIndex++){
			//chess[row][colIndex] = 1;
			if(isSafe(chess, row, colIndex) == TRUE){//如果可以放置皇后
				chess[row][colIndex] = 1;//放置皇后
				eightQueen(chess, row+1);//进行递归
				chess[row][colIndex] = 0;//递归返回时,证明此列不适合,下一列放置皇后
			}
		}
	}
输出函数:

void showChess(int (*chess)[EIGHT]){
	int i;
	int j;
	static int count;

	printf("解%d:\n", ++count);
	for(i = 0; i < EIGHT; i++){
		for(j = 0; j < EIGHT; j++){
			printf("%4d", chess[i][j]);
		}
		printf("\n");
	}
}
主函数:

void main()
{
	int chess[EIGHT][EIGHT] = {0};//定义并且初始化棋盘
	
	eightQueen(chess, 0);//进行处理
	
}