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

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

例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;
}