n皇后
解决一个回溯问题，实际就是一个决策树（在每个节点上都在做决策）的遍历过程。只需要思考三个问题：
- 路径：已经做出的选择
- 选择列表：当前可以做的选择
- 结束条件：到达决策树底层，无法再做选择的条件（路径==选择列表长度）
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
#include<cstdio>
#include<cstdlib>
#include<iostream>
usingnamespacestd;
constintN=20;
intcounter,n;//计数器：记录n皇后一共有几个解
inta[N];//表示第i行上的皇后放在a[i]列上；例a[3]=7，表示第3行的皇后放在第7列
//检查第x行的皇后能否放在第y列
boolcheck(intx,inty){
//枚举前面x行
for(inti=1;i<x;i++){
if(a[i]==y) returnfalse;//第i行已经存在皇后位于第y列
if(i+a[i]==x+y) returnfalse;//右倾对角线上的点(x,y)，x+y都相等
if(i-a[i]==x-y) returnfalse;//左倾对角线上的点(x,y),x-y都相等
}
returntrue;
}
voiddfs(introw){//解决第row行皇后放在哪里
//到达边界
if(row==n+1){
//已经解决n行，产生了一组解
counter++;
return;
}
//未到达边界，则当前行的皇后有n种可能的放置
for(inti=1;i<=n;i++){
//对当前位置i进行check，能否放置
if(check(row,i)){
a[row]=i;//放置当前行皇后
dfs(row+1);//解决下一行的皇后位置，当其递归出时，说明已经产生了一组解
a[row]=0;//回收当前列皇后，准备将其放在下一列
}
}
}
intmain(){
cin>>n;
dfs(1);
cout<<counter;
return0;
}
图着色问题
给定无向连通图G和m种不同的颜色。
- 无相连通图G
- m种不同的颜色
- G中每个顶点都要着色，且每条边的两个顶点颜色不同
- 求共有多少种着色方法
//n:点个数
//c:邻接矩阵 c[i][j]=1表示i与j相连，=0表示不相连
//m:颜色数
//所有数组下标从1开始
voidGraphColor(intn,intc[][],intm){
for(inti=1;i<=n;i++)//将数组color[n]初始化为0，表示顶点i尚未着色
color[i]=0;
k=1;
while(k>=1){
}
}
