回溯

回溯：递归的一种，或者说是通过递归这种代码结构来实现回溯这个目的。回溯法可以被认为是一个有过剪枝的DFS过程。把问题分解成若干步骤 并递归求解时如果当前步骤没有合法选择 则函数返回上一级递归调用 这种现象叫做回朔

回溯的一般结构：

void dfs(int 当前状态){
          if(当前状态为边界状态){
            记录或输出
            return;
          }
          for(i=0;i<n;i++){     //横向遍历解答树所有子节点
               //扩展出一个子状态。
               修改了全局变量
               if(子状态满足约束条件){
                  dfs(子状态)
               }
                恢复全局变量//回溯部分
            }
    }

8 皇后问题

#include "stdio.h"
#define N 8
int n = N;
int ans = 0;
int C[N];
void f(int cur){
    if(cur == n)    {
        ans++;
    
        for( int i = 0; i<N ;i++){
            int x = C[i];
            for (int j = 0; j < N; j++) {
                if(x == j){ printf("1 ");continue;}
                printf("0 ");
            }
            printf("\n");
        }
    printf("\n");printf("\n");
    }
    
    for(int i = 0;i < n; i++){
        int ok = 1;
        C[cur] = i  ; //cur 行 放 第 i 列
        for(int j = 0; j < cur; j++)//列数在变     /****对于坐标(x,y)与（m,n）若在主对角线上 y-x = n-m 副对角线 y+x = m+n *****/
            if( C[cur] == C[j]/*是否同一列*/ || cur - C[cur] == j - C[j] /*检查主对角线*/ || cur + C[cur] == j + C[j] /*副对角线*/){//按行放置不用检查行
                ok = 0; break;//不符合
        }
        if(ok) f(cur+1);//若合法 继续 下一行放置
    }
}

int main(){
    f(0);
    printf("%d\n",ans);
    return 0;
}