数据结构重读 – 回溯法与树的遍历 (幂集问题 八皇后问题)

有许多问题,可以利用试探和回溯的搜索技术求解。

求解的过程实际是先序遍历一棵“状态树”的过程

例1:有集合A = {1, 2, …n},求A的全部子集。

思路:从求全部子集(幂集)这个事情上,实际上对每个元素只有两个状态:要么在一个子集中,要么不在。

因此,可以逐一对A中每个元素进行“取”和“舍”,从而构造一棵完全二叉树。

算法如下:

注意这里是1~n,不是0~n

void mj(int n, int pos, int* flag)
{
    if(pos>n)    
    {
        int i = 1;
        for(i=1;i<=n;i++)
        {
            if(flag[i])
            {
                printf("%d ", i);
            }
        }
        printf("\n");
    } else
    {
        flag[pos] = 0;
        mj(n, pos+1, flag);
        flag[pos] = 1;
        mj(n, pos+1, flag);
    }
}

 

然而,很多问题用回溯法求解时,描述求解过程的状态树并不是一棵满二叉树。当位于和解矛盾的状态时,不能继续试探下去,而要剪去哪些不满足条件的分支。

下面来看一下八皇后问题:

八皇后问题即有八个皇后,要放到8×8的棋盘上,要求任何时刻,棋盘的同一行、同一列、同一对角线都只有一个皇后。

最基础解法就是回溯。

首先说下合法条件:

(1)行、列不说了。
(2)假设两个皇后位于(i, j)和(m, n),则斜对角线的条件是abs(m-i) = abs(n-j)。

此外,我们可以不用n*n的数组记录皇后位置,而是用n数组表示,其中a[0]表示第0行皇后位于第几列。

其他就很简单了!

#include <stdio.h>
#include <string.h>

#define MAX 8

int is_valid(int* arr, int n, int row, int col)
{	
	int i,j;
	if(row>=n || col>=n || row<0 || col<0)
	{
		return 0;
	}
	// No need to check same row
	// Check xie
	for(i=0;i<row;i++)
	{
		// Check same col 
		if(arr[i]==col)
		{
			return 0;
		}
		// Check xie 1
		// two queen (i, j) and (k, l) xie is |k-i| = |l-j|
		if(abs(row-i)==abs(col-arr[i]))
		{
			return 0;
		}
	}
	return 1;
}

int res = 0;
void four_queen(int row, int* arr, int n)
{
	if(row==n)
	{
		// Successfully place 4 queen
		int i,j;
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				if(j==arr[i])
				{
					printf("%2d", 1);
				}else
				{
					printf("%2d", 0);
				}
			}
			printf("\n");
		}
		printf("\n");
		res++;
	}else
	{
		// Choose four col for current row
		int i;
		for(i=0;i<n;i++)
		{
			if(is_valid(arr, n, row, i))
			{
				arr[row] = i;
				four_queen(row+1, arr, n);
			}
		}
	}
}


int main()
{
	int arr[MAX];
	memset(arr, 0, sizeof(int)*MAX);
	res = 0;
	four_queen(0, arr, MAX);
	printf("%d\b", res);
	return 0;
}

 

Leave a Reply

Your email address will not be published.