算法进化历程之“n皇后问题”

巧若拙（欢迎转载，但请注明出处：http://blog.csdn.net/qiaoruozhuo）

题目来源于国际象棋的玩法，因为皇后所在的位置可以纵向、横向、两个斜向四个方向的“捕捉”，也就是说不存在两个皇后同行或同列，或在同一斜线上。而N皇后问题就是如何布置N个皇后在N*N棋盘里使不存在两个皇后在同行同列和同一斜线上。

     解决N皇后问题的最好最著名的算法就是回溯法。根据不同的数据结构和判断棋盘中某位置是否可以摆放皇后的判断方法，我们有多种实现该算法的方式。

       方法一：

       使用二维数组map[MAX][MAX]存储棋盘，初始化棋盘各元素值为0，皇后所在位置元素值为1。摆放结束后，输出棋盘。

       本算法采用递归方式遍历棋盘中每一个位置，利用函数Place(introw, int col, int n)，判断map[row][col]位置是否可以放棋子。

       代码如下：

void Queen_1(int row, int n)//n皇后问题主递归函数 
{
	int col;
	
	if (row == n)//全部摆上
	{
		count++;
		printf("第%d盘：\n", count); 
		Print(n);
		return ;
	} 
	
	for (col=0; col<n; col++)
	{
		if (Place(row, col, n))
		{
			map[row][col] = 1;
			Queen_1(row+1, n);
			map[row][col] = 0;
		}
	}
}

void Print(int n)//输出一个解
{
	int i, j;
	
	for (i=0; i<n; i++)
	{
		for (j=0; j<n; j++)
		{
			if (map[i][j] == 1) 
				printf("%c", 2);
			else
				printf("#");
		}
		printf("\n");
	}
	printf("\n");
} 

int Place(int row, int col, int n)//判断map[row][col]位置是否可以放棋子 
{
	int i;
	
	for (i=0; i<=row; i++)
	{
		if (map[i][col] == 1)//同一列 
			return 0;
		if (col >= i && map[row-i][col-i] == 1)//左斜线 
			return 0;
		if (col+i<n && map[row-i][col+i] == 1)//右斜线 
			return 0;
	}
	
	return 1;
}

方法二：

       方法一中的Place()函数是根据已摆棋子的情况，来判断当前位置是否可以放棋子，这种方法很常见。除此之外，还可以修改当前棋子所能影响的位置的值（我的方法是使该处值增2），表示该位置不能再摆放新的棋子。待撤销当前棋子后，再把对应影响位置的值改回来。

       代码如下：

void Queen_2(int row, int n)//n皇后问题主递归函数 
{
	int i, j;
	
	if (row == n)//全部摆上
	{
		count++;
		printf("第%d盘：\n", count); 
		Print(n);
		return ;
	} 
	
	for (i=0; i<n; i++)
	{
		if (map[row][i] == 0)
		{
			map[row][i] = 1;
			
			for(j=1; j<n-row; j++)//标记不可放子处 
			{
				map[row+j][i] += 2;
				if (i >= j)  //左斜线 
					map[row+j][i-j] += 2;
				if (i+j < n)  //右斜线 
					map[row+j][i+j] += 2;
			}
			
			Queen_2(row+1, n);
			
			for(j=1; j<n-row; j++)//还原
			{
				map[row+j][i] -= 2;
				if (i >= j)  //左斜线 
					map[row+j][i-j] -= 2;
				if (i+j < n)  //右斜线 
					map[row+j][i+j] -= 2;
			}
			map[row][i] = 0;
		}
	}
}

方法三：

       前面两种方法都是采用了二维数组来存储棋盘信息，其实用一维数组也能存储完整的棋盘信息。我们设board[row] = col;表示第row行的皇后摆在第col列。

       同样采用递归方式的回溯算法，但Place()函数和Print()函数的写法都略有不同。

代码如下：

void Queen_3(int row, int n)//n皇后问题主递归函数 
{
	int col, i, j;
	
	if (row == n)//全部摆上
	{
		count++;
		printf("第%d盘：\n", count); 
		Print_2(n);
		return ;
	} 
	
	for (col=0; col<n; col++)
	{
		board[row] = col;
		if (Place_2(row))
		{
			Queen_3(row+1, n);
		}
	}
}

int Place_2(int row)//判断当前棋局是否满足条件 
{
	int i;
	
	for (i=0; i<row; i++)
	{
		if (board[i] == board[row])//同一列 
			return 0;
		if (board[i] < board[row] && (row-i) == (board[row]-board[i]))//左斜线 
			return 0;
		if (board[i] > board[row] && (row-i) == (board[i]-board[row]))//右斜线 
			return 0;
	}
	
	return 1;
}

void Print_2(int n)//输出一个解
{
	int i, j;
	
	for (i=0; i<n; i++)
	{
		for (j=0; j<n; j++)
		{
			if (j == board[i]) 
				printf("%c", 2);
			else
				printf("#");
		}
		printf("\n");
	}
	printf("\n");
}

方法四：

       有递归方式的回溯算法，自然就有对应的非递归方法，我们可以采用深度优先搜索的通用转换方法，把递归方式转换为非递归方式。（关于非递归转换，我的博客中已经整理的大量例子，感兴趣的网友可以到http://blog.csdn.net/qiaoruozhuo查看“非递归优化”文章分类）

       代码如下：

void Queen_4(int n)//n皇后问题非递归函数 
{
	int row, col, i, j;
	
	row = 0;
	board[0] = -1;
	while (row >= 0)
	{
		board[row]++; 
		if (row < n)
		{
			if (board[row] < n && Place_2(row))//初始化下一行 
				board[++row] = -1;
			else if(board[row] == n)//返回上一行 
				row--;
		}
		else
		{
			count++;
			printf("第%d盘：\n", count); 
			Print_2(n); 
			row--;
		} 
	}
}

解决n皇后问题的算法还有很多，我在另外一篇文章《优化的n皇后问题》中，介绍了采用输出对称图形的方法，该算法思路源自方法四，但只考虑第一行的皇后摆在棋盘左侧的情况（若n为奇数则单独计算第一行皇后在正中间的情况），得到一个解后，直接输出它的对称解，这样只需要一半的计算量。

       还有人是使用位运算来判断某位置是否可以摆放棋子，效率很高，大家可以去研究一下。

算法进化历程之“n皇后问题”