回溯算法

回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

用回溯法解题的一般步骤：

　　（1）针对所给问题，定义问题的解空间；

　 （2）确定易于搜索的解空间结构；

　（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

用回溯法解决八皇后问题的C语言程序
　　#include<stdio.h>
　　#include<stdlib.h>
　　int col[9] = {0}, a[9];
　　int b[17], c[17];
　　main()
　　
{
    　　int m, good;
    　　int i, j, k;
    　　char q;
    　　for(i = 0; i < 17; i++)
        　　{
        　　if(i < 9) a[i] = 1;
        　　b[i] = 1;
        c[i] = 1;
        　　
    }
    　　good = 1;
    　　col[1] = 1;
    　　m = 1;
    　　while(col[0] != 1)
        　　{
        　　if(good)
            　　if(m == 8)
                　　{
                　　for(i = 1; i < 9; i++)
                    　　printf("col[%d] %d/n", i, col[i]);
                　　printf("input 'q' to quit/n");
                　　scanf("%c", &q);
                　　getchar();
                　　if(q == 'q' || q == 'Q') exit(0);
                　　while(col[m] == 8)
                    　　{
                    　　m--;
                    　　a[col[m]] = b[m+col[m]] = c[8+m-col[m]] = 1;
                    　　
                }
                　　a[col[m]] = b[m+col[m]] = c[8+m-col[m]] = 1;
                　　col[m]++;
                　　
            }
            　　else
                　　{
                　　a[col[m]] = b[m+col[m]] = c[8+m-col[m]] = 0;
                　　m++;
                　　col[m] = 1;
                　　
            }
        　　else
            　　{
            　　while(col[m] == 8)
                　　{
                　　m--;
                　　a[col[m]] = b[m+col[m]] = c[8+m-col[m]] = 1;
                　　
            }
            　　col[m]++;
            　　
        }
        　　good = a[col[m]] && b[m+col[m]] && c[8+m-col[m]];
        　　
    }
    　　
}