回溯算法相当于穷举搜索的巧妙实现，穷举算法是每一种可能都去尝试， 回溯法会在尝试的过程中做出判断，当发现一些不符合标准的组合方案，直接跳过不去尝试。因此， 回溯算法能节省时间代价； 回溯算法实质上还是暴力算法，但是回溯算法并不直接尝试所有的可能，会删除不可能的方案； 在一步内删除一大组可能性的做法叫做裁剪；
在尝试解决问题时候， 每进行一步， 都是抱着试试看的态度；如果发现当前选择并不是最好的，或者这样继续下去可定达不到目标时候， 就放弃本次操作，返回上一层操作，重新做选择； （走不通就回退）；
回溯法与递归的区别： 1） 回溯法： 从问题本身出发，寻找可能实现的所有情况。和穷举法的思想相近，不同在于穷举法是将所有的情况都列举出来以后再一一筛选，而回溯法在列举过程如果发现当前情况根本不可能存在，就停止后续的所有工作，返回上一步进行新的尝试。 2） 递归： 递归是从问题的结果出发，例如求 n！，要想知道 n！的结果，就需要知道 n*(n-1)! 的结果，而要想知道 (n-1)! 结果，就需要提前知道 (n-1)*(n-2)!。这样不断地向自己提问，不断地调用自己的思想就是递归。 回溯和递归唯一的联系就是，回溯法可以用递归思想实现。
问题描述： 八皇后问题是以国际象棋为背景的问题：有八个皇后（可以当成八个棋子），如何在 8*8 的棋盘中放置八个皇后，使得任意两个皇后都不在同一条横线、纵线或者斜线上。
八皇后问题解决思路： 1） 从棋盘的第一行开始， 从第一个位置开始， 依次判断当前位置是否能够放置皇后；判断依据是：与之前行的数据比较， 不能与之前的同列， 或是处在对角线上； 2） 如果在当前行的所有列位置上都通过检验， 就返回到上一行重新选择， 然后继续试探； 3） 如果试探到最后一行，并且通过试探并摆放成功， 直接打印出棋盘。然后将棋盘恢复，以放置下一次尝试；
具体代码实现如下：
#include <stdio.h> #include <stdlib.h> #define N 8 int Queen[N] = { 0 }; int Count = 0; int Check(int row, int col) { //遍历当前行之前的所有行，与当前行的数据比较，以判断是否要继续进行下去 for (int index = 0; index < row; index++) { int data = Queen[index]; //用来比较的数据是(index, data)与(row, col) if (data == col) return 0; if ((index + data) == (row + col)) return 0; if ((index - data) == (row - col)) return 0; } return 1; } //根据一组Queen数组打印出一个棋盘 void printChess() { for (int i = 0; i < N; i++) { int flag = Queen[i]; for (int j = 0; j < flag; j++) printf("- "); printf("# "); for (int j = flag + 1; j < N; j++) printf("- "); printf("\n"); } printf("================\n"); } //对于第row行， 确定在该行的哪一个位置摆放棋子 void EightQueen(int row){ for (int col = 0; col < N; col++) { if (Check(row, col)) {//如果测试成功， 就在该行放置棋子 Queen[row] = col; //如果这是最后一行，并且最后一行的棋子放置成功了， 就打印整个棋盘 if (row == N-1) { Count++; printChess(); Queen[row] = 0; //完成棋盘打印之后， Queen必须清零 return; } //当前行row完成棋子放置之后， 对下一行尝试放置棋子 EightQueen(row + 1); //当row行成功放置棋子后， 对row+1行进行递归调用; //但这个递归调用返回之后, 已经完成了对row+1行的所有列的所有测试 //此时需要对row行的下一个列col+1进行测试 //此时Queen[row] 保存的是col，因此需要将Queen[row] 清零 Queen[row] = 0; } } } int main() { EightQueen(0); printf("the sum of plan: %d\n", Count); return 0; }