回溯法

回溯法是一种比枚取发更好的算法，回溯法有一定的框架，这里先给出回溯的法的一般框架：

//m表示数组有m个元素，n表示数组的最大元素值为n
输入正整数n, m(n>=m)
i = 0; 
a[i] = <元素初始值>

while (1)
{
    // i每次取得的值，和前面已得到的值进行比较,看是否能满足
    for (g = 1, k = i - 1; k >= 0; k--)
    {
        if (<约束条件1>)
            g = 0;          //检测约束条件，不满足返回
    }

    if (g && <约束条件2>)
    {
        print(a[0:m])      //输出一个解
    }

    if (g && i < m)
    {
        i++;
        a[i] = <元素初始值>;
        contiue;
    }
    

    while (a[i] == <回溯点> && i > 0)   
    {
        i--;      //向前回溯
    }

    // 达到退出循环的条件 
    if (i == 0 && a[i] == <回溯点>)
    {
        break;
    } else 
    {
        a[i]++;
    }

}

下面用回溯法来解决一个典型的回溯问题，八皇后问题，问题描述就省率了，直接上算法

#include <stdio.h>
#include <stdlib.h>

int main(int argc, const char *argv[])
{
    int i, j, k, g;
    // raw表示有8行，col表示有8列 
    int raw = 8, col = 8;
    int a[8];
    i = 0; 
    a[i] = 0;

    while (1)
    {
        // a[i]每次取得的位置，和前面已得到的位置进行比较,看是否能满足
        for (g = 1, k = i - 1; k >= 0; k--)
        {
        	if (g == 0)
        		break;
            // a[i] == a[k]是检测是否和某个皇后在同一列
            // abs(a[i] - a[k]) == (i - k)是检测是否和某个皇后在同一个对角线上
            if (a[i] == a[k] || abs(a[i] - a[k]) == (i - k))
                g = 0;          //检测约束条件，不满足返回
        }
        
        // 如果到了最后一行且有一个位置可放 
        if (g && i == (raw - 1))
        {
            for (j = 0; j < raw; j++)
            {
                printf("%d, ", a[j]);
            }
            printf("\n");
        }

	// 如果没有到最后一行且上一行的有个位置可放 
        if (g && i < (raw - 1))
        {
            i++;
            a[i] = 0;
            continue;
        }
		
        while (a[i] == (col - 1) && i > 0)   
        {
            i--;      //向前回溯
        }

        // 达到退出循环的条件 
        if (i == 0 && a[i] == (col - 1))
        {
            break;
        } else 
        {
            a[i]++;
        }
    }	     
    return 0;
}