递归+回溯
基本思想就是：
1、用一个标记数组记录当前那些数字已经被用了
2、枚举第一个位置所有点的可能情况，然后将第一个位置使用的元素进行标记，然后DFS（i，0）
3、DFS（num， level）要做的事情就是，先将该数放进g[level] = num; （即将当前数放进该层中），然后去遍历vis[] 数组，看那些数还能被使用，不能用的跳过，能用的先标记，再DFS（i，level+1） 再取消标记。DFS（）结束的标志是，当填完当前位置元素后，没有元素能被放置，（即所有的元素已经使用完了）这时候就进行回溯。
#include#include #include #include using namespace std;int n;int vis[10];int g[10];int ans = 0;void DFS(int num, int level){ g[level] = num; if(level == n-1) { ans ++; for(int i = 0; i < n; ++i) { printf("%d ", g[i]); } puts(""); return; } for(int i = 1; i <= n; ++i) { if(!vis[i]) { vis[i] = 1; DFS(i, level+1); vis[i] = 0; } }}int main(){ while(cin >> n) { ans = 0; for(int i = 1; i <= n; ++i) { memset(vis, 0, sizeof(vis)); memset(g, 0, sizeof(g)); vis[i] = 1; DFS(i, 0); vis[i] = 0; } printf("n = %d, ans = %d\n", n, ans); } return 0;}
八皇后问题（在一个8*8的棋盘上放置 queue， 要求每行每列，各个对角线不能有两个queue）
想法：和用DFS写全排列想法类似。用vis_col[] 数组去标记每一列，DFS的过程去一行一行递归，然后回溯。其中就是加了对两个queue是否在一列的判断。
#include#include #include using namespace std;int g[10][10];int vis_col[10];int check(int row, int col){ for(int i = 0; i < 8; ++i) { for(int j = 0; j < 8; ++j) { if(g[i][j] == 1) { if(abs(i - row) == abs(j - col)) return 1; } } } return 0;}int ans = 0;void DFS(int row, int col){ g[row][col] = 1; if(row == 7) { ans ++; for(int i = 0; i < 8; ++i) { for(int j = 0; j < 8; ++j) printf("%d ", g[i][j]); puts(""); } g[row][col] = 0; return; } for(int i = 0; i < 8; ++i) { if(!vis_col[i] && !check(row+1, i)) { //printf("%d ", i); vis_col[i] = 1; DFS(row+1, i); vis_col[i] = 0; } } g[row][col] = 0;}int main(){ //freopen("out.txt", "w", stdout); memset(g, 0, sizeof(g)); memset(vis_col, 0, sizeof(vis_col)); for(int i = 0; i < 8; ++i) { vis_col[i] = 1; DFS(0, i); vis_col[i] = 0; puts(""); } printf("ans is %d \n", ans); return 0;}