回溯：递归的一种，或者说是通过递归这种代码结构来实现回溯这个目的。回溯法可以被认为是一个有过剪枝的DFS过程。把问题分解成若干步骤 并递归求解时如果当前步骤没有合法选择 则函数返回上一级递归调用 这种现象叫做回朔
回溯的一般结构：
void dfs(int 当前状态){
if(当前状态为边界状态){
记录或输出
return;
}
for(i=0;i<n;i++){ //横向遍历解答树所有子节点
//扩展出一个子状态。
修改了全局变量
if(子状态满足约束条件){
dfs(子状态)
}
恢复全局变量//回溯部分
}
}
#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;
}
