N 皇后求解回溯算法

1. /*******************************************************
2. *n后求解问题
3. *******************************************************/
4. #include<iostream.h>
5. #include<stdio.h>
6. #include<math.h>
7. #include<conio.h>
9. #defineMAXNUMBER20//最大求解数
11. //输出n后的解
12. /******************************************************
13. *例如8皇后的一组解为：
14. *15863724
15. *其含义为
16. *第1个皇后位于第1行第1列
17. *第2个皇后位于第2行第5列
18. *第3个皇后位于第3行第8列
19. *第4个皇后位于第4行第6列
20. *......
21. *第i个皇后位于第i行第x[i]列(i>=1)
22. ******************************************************/
23. voidoutput_queens(intx[],intn)
24. {
25. for(inti=1;i<=n;i++)
26. printf("%3d",x[i]);
27. printf("\n");
28. }
29. //判断第k个皇后是否合法
30. boolcheck(intx[],intk)
31. {
32. for(inti=1;i<k;i++)
33. {//列冲突x[i]==x[k]或斜线冲突abs(k-i)==abs(x[k]-x[i])
34. if(x[i]==x[k]||abs(k-i)==abs(x[k]-x[i]))
35. returnfalse;
36. }
37. returntrue;
38. }
39. /*******************************************************
40. *n后问题求解
41. *input:n,thenumberofqueens
42. *output:thevectorofsolution,X
43. *******************************************************/
44. intn_queens(intn,intx[])
45. {
46. intnCount=0;//解的个数
47. intk=1;//先处理第1个皇后
48. x[1]=0;
50. while(k>0)
51. {
52. x[k]=x[k]+1;//在当前列加1的位置搜索
54. while(x[k]<=n&&!check(x,k))
55. x[k]=x[k]+1;//如果当前列x[k]不满足条件则搜索下一列x[k]+1
57. if(x[k]<=n)
58. {//列x[k]满足条件
59. if(k==n)
60. {//当前是最后一个皇后=>得到一组解
61. //break;//若此处break则只得到一组解
62. nCount++;//解的个数加1
63. output_queens(x,n);//输出n后的解
65. }else
66. {//计算第k+1个皇后
67. k++;
68. x[k]=0;
69. }
70. }else
71. {//不存在满足条件的列=>回溯
72. x[k]=0;
73. k--;
74. }
75. }
76. returnnCount;
77. }
79. voidmain()
80. {
81. intn=8;
82. intx[MAXNUMBER]={0};
84. printf("GameStart:\n");
86. intnCount=n_queens(8,x);
87. printf("TotalNumber:%4d\n",nCount);
89. printf("Gameover!!!\n\n\n");
90. }