《C系列-实例相关》基于C语言的n皇后问题

基于C语言的n皇后问题

1.逻辑梳理

• 1.利用回溯法解决N皇后问题，逐行和逐列查找满足条件的位置
• 2.如果一整行都找不到满足条件的位置，那么回溯到上一行
• 3.解决N皇后问题，就是建立N*N的矩阵，但是N皇后超过20对电脑要求比较高
• 4.N皇后问题中，需要满足三个约束条件，不在同一行、同一列、同一斜线
• 5.当N=2,3时都受到约束条件的限制
• 6.在queens函数中调用dispasoulution(n);函数，实现输出解功能。place(k)；函数实现确定皇后放置位置问题
• 7.在主函数中，用户从键盘输入n值，通过判断用户输入值的可行性，给出合理建议。

2.逻辑开发

2.1 dispasoulution函数

1. void dispasoulution(int n)//输出一个解
2. {
3. static int count=0;//定义静态变量来统计解的个数
4. int i;
5. printf("第%d个解:",++count);//每输出一次执行一次++
6. for(i=1;i<=n;i++)
7. printf("(%d,%d)",i,q[i]);//利用for循环依次输出解
8. printf("\n");
9. }

复制代码

2.2 place函数

1. int place(int k)//调用place函数判断能否放置该皇后
2. {
3. int i=1;
4. while(i<k)
5. {
6. if((q[i]==q[k])||(abs(q[i]-q[k])==abs(i-k)))//判断是否满足约束关系，不能同列，不能同对角线
7. return 0;
8. i++;
9. }
10. return 1;
11. }

复制代码

2.3 queens函数

1. void queens(int n)
2. {
3. int k=1;//表示皇后个数或行数
4. q[k]=0;//表示当前列，从开头存放
5. while(1)
6. {
7. q[k]=q[k]+1;//测试下一列
8. while(q[k]<=n&&!place(k))
9. q[k]=q[k]+1;
10. if(q[k]<=n)//找到第k个皇后的合适位置
11. {
12. if(k==n)//（皇后全部放置）
13. dispasoulution(n);//当满足k==n时，输出这个解
14. else
15. {
16. k++;//向下一行放置皇后
17. q[k]=0;//从第一列开始
18. }
19. }
20. else//如果没有找到合适的存放皇后的位置
21. {
22. if(k==1) exit(0);//如果回溯完成，算法结束
23. k--;//回溯到上一行
24. }
25. }
27. }

复制代码

2.4 again函数

1. void again()
2. {
3. int n;
4. printf("请重新输入一个合适的N值：\n");
5. scanf("%d",&n);
6. if(n==1&&n>=4||n<=20)
7. queens(n);
8. else
9. printf("禁止再次输入\n");
10. }

复制代码

2.5 主函数

1. int main()
2. {
3. int n;
4. printf("n皇后问题(n<20)\nn=");
5. scanf("%d",&n);
6. if(n>1&&n<4||n>20)
7. {
8. printf("n值不满足情况！\n");
9. again();
10. }
11. else
12. {
13. printf("n皇后的问题求解如下：\n");
14. queens(n);
15. }
16. }

复制代码

3.完整代码

1. #include<stdio.h>
2. #include<stdlib.h>
3. const int MAXN=20;//表示最多存放的皇后个数
4. int q[MAXN];//利用q[MAXN]来记录执行的列数
5. void dispasoulution(int n)//输出一个解
6. {
7. static int count=0;//定义静态变量来统计解的个数
8. int i;
9. printf("第%d个解:",++count);//每输出一次执行一次++
10. for(i=1;i<=n;i++)
11. printf("(%d,%d)",i,q[i]);//利用for循环依次输出解
12. printf("\n");
13. }
14. int place(int k)//调用place函数判断能否放置该皇后
15. {
16. int i=1;
17. while(i<k)
18. {
19. if((q[i]==q[k])||(abs(q[i]-q[k])==abs(i-k)))//判断是否满足约束关系，不能同列，不能同对角线
20. return 0;
21. i++;
22. }
23. return 1;
24. }
25. void queens(int n)
26. {
27. int k=1;//表示皇后个数或行数
28. q[k]=0;//表示当前列，从开头存放
29. while(1)
30. {
31. q[k]=q[k]+1;//测试下一列
32. while(q[k]<=n&&!place(k))
33. q[k]=q[k]+1;
34. if(q[k]<=n)//找到第k个皇后的合适位置
35. {
36. if(k==n)//（皇后全部放置）
37. dispasoulution(n);//当满足k==n时，输出这个解
38. else
39. {
40. k++;//向下一行放置皇后
41. q[k]=0;//从第一列开始
42. }
43. }
44. else//如果没有找到合适的存放皇后的位置
45. {
46. if(k==1) exit(0);//如果回溯完成，算法结束
47. k--;//回溯到上一行
48. }
49. }
51. }
52. void again()
53. {
54. int n;
55. printf("请重新输入一个合适的N值：\n");
56. scanf("%d",&n);
57. if(n==1&&n>=4||n<=20)
58. queens(n);
59. else
60. printf("禁止再次输入\n");
61. }
62. int main()
63. {
64. int n;
65. printf("n皇后问题(n<20)\nn=");
66. scanf("%d",&n);
67. if(n>1&&n<4||n>20)
68. {
69. printf("n值不满足情况！\n");
70. again();
71. }
72. else
73. {
74. printf("n皇后的问题求解如下：\n");
75. queens(n);
76. }
77. }

复制代码