首页 > 代码库 > N皇后问题--递归回溯
N皇后问题--递归回溯
著名的N皇后问题，就是先按照行一行一行的找，先找第一行，第一行找到一列能满足条件，继续找下一行，如果下一行也找到一列能满足条件，继续找下一行，一次类推，最终找到解， 但是，如果找不到的话， 就说明上一行放的位置错误， 所以回溯到上一行中，继续找下一列，如果找不到，继续回溯，大体就是这么执行找到解的。
下面是代码：
1 #include <stdio.h> 2 3 const int MAX = 30; 4 int n; 5 int a[MAX];//保存当前列值 6 int vis1[MAX];//标记当前列 7 int vis2[MAX];//标记副对角线 8 int vis3[MAX];//标记主对角线 9 int cnt;10 void dfs(int cur)11 {12 if(cur == n)//如果找完了，打印出来 13 {14 for(int i = 0; i < n; i++)15 printf("%d ", a[i]);16 printf("\n");17 cnt++;18 return;19 }20 int i = cur + 1;//此时是按照行来找的，所以直接遍历列就行 21 for(int j = 1; j <= n; j++)22 {23 //如果列，主对角线，副对角线都满足条件，就能放 24 if(vis1[j] == 0 && vis2[i + j] == 0 && vis3[i - j + 14] == 0)25 {26 //标记 27 vis1[j] = 1;28 vis2[i + j] = 1;29 vis3[i - j + 14] = 1;30 //如果满足条件，就将当前的列值给到a数组中 31 a[cur] = j;32 //找下一列 33 dfs(cur + 1);34 //取消标记， 35 vis1[j] = 0;36 vis2[i + j] = 0;37 vis3[i - j + 14] = 0;38 }39 40 }41 }42 int main()43 {44 while(~scanf("%d", &n))45 {46 cnt = 0;47 dfs(0);48 printf("%d\n", cnt);//统计总数 49 }50 return 0;51 }
N皇后问题--递归回溯
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。