回溯法

共计 979 个字符，预计需要花费 3 分钟才能阅读完成。

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

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