八皇後問題是在8*8的棋盤上放置8枚皇後，使得棋盤中每個縱向、橫向、左上至右下斜向、右上至左下斜向均只有一枚皇後。八皇後的一個可行解如圖所示：
思路
對於八皇後的求解可采用回溯算法，從上至下依次在每一行放置皇後，進行搜索，若在某一行的任意一列放置皇後均不能滿足要求，則不再向下搜索，而進行回溯，回溯至有其他列可放置皇後的一行，再向下搜索，直到搜索至最後一行，找到可行解，輸出。
可以使用遞歸函數實現上述回溯算法，遞歸函數用於求解在某一行放置皇後，具體代碼如下所示
。
代碼
1. #include <stdlib.h>
2. #include <stdio.h>
3.
4. int m[8][8] = {0};//表示棋盤，初始為0，表示未放置皇後
5. int num = 0;//解數目
6.
7. //對於棋盤前row-1行已放置好皇後
8. //檢查在第row行、第column列放置一枚皇後是否可行
9. bool check(int row,int column)
10. {
11. if(row==1) return true;
12. int i,j;
13. //縱向只能有一枚皇後
14. for(i=0;i<=row-2;i++)
15. {
16. if(m[i][column-1]==1) return false;
17. }
18. //左上至右下只能有一枚皇後
19. i = row-2;
20. j = i-(row-column);
21. while(i>=0&&j>=0)
22. {
23. if(m[i][j]==1) return false;
24. i--;
25. j--;
26. }
27. //右上至左下只能有一枚皇後
28. i = row-2;
29. j = row+column-i-2;
30. while(i>=0&&j<=7)
31. {
32. if(m[i][j]==1) return false;
33. i--;
34. j++;
35. }
36. return true;
37. }
38.
39. //當已放置8枚皇後，為可行解時，輸出棋盤
40. void output()
41. {
42. int i,j;
43. num++;
44. printf("answer %d:\n",num);
45. for(i=0;i<8;i++)
46. {
47. for(j=0;j<8;j++) printf("%d ",m[i][j]);
48. printf("\n");
49. }
50. }
51.
52. //采用遞歸函數實現八皇後回溯算法
53. //該函數求解當棋盤前row-1行已放置好皇後，在第row行放置皇後
54. void solve(int row)
55. {
56. int j;
57. //考慮在第row行的各列放置皇後
58. for (j=0;j<8;j++)
59. {
60. //在其中一列放置皇後
61. m[row-1][j] = 1;
62. //檢查在該列放置皇後是否可行
63. if (check(row,j+1)==true)
64. {
65. //若該列可放置皇後，且該列為最後一列，則找到一可行解，輸出
66. if(row==8) output();
67. //若該列可放置皇後，則向下一行，繼續搜索、求解
68. else solve(row+1);
69. }
70. //取出該列的皇後，進行回溯，在其他列放置皇後
71. m[row-1][j] = 0;
72. }
73. }
74.
75. //主函數
76. int main()
77. {
78. //求解八皇後問題
79. solve(1);
80. return 0;
81. }
