通用解题思想：回溯法（附八皇后问题解析）

pixie0096

朕想知道

前面那个人好丑

朕想知道

不要打扰我

1

kelvinlewis777

朕想知道

兀凉

签到

1481821848

12

吕乐甜

朕想知道

milesl

什么情况

y12

真想知道

言覃Jack

真想知道

EmmmmmmTRUE

朕想知道

欧奇诺

.

嘟嘟橙

朕想知道

可爱的华子

朕想知道

Draem

Draem

1. #include <stdio.h>
   
2. 
   
3. int count = 0;
   
4. 
   
5. int check(int i, int j, int (*queen)[8]);
   
6. void setQueen(int i, int (*queen)[8]);
   
7. 
   
8. int check(int i, int j, int (*queen)[8])
   
9. {
   
10.         int s, t;
    
11. 
    
12.         // 判断行
    
13.         for (s = i, t = 0; t < 8; t++)
    
14.         {
    
15.                 if (queen[s][t] == 1 && t != j)
    
16.                 {
    
17.                         return 0;
    
18.                 }
    
19.         }
    
20. 
    
21.         // 判断列
    
22.         for (t = j, s = 0; s < 8; s++)
    
23.         {
    
24.                 if (queen[s][t] == 1 && s != i)
    
25.                 {
    
26.                         return 0;
    
27.                 }
    
28.         }
    
29. 
    
30.         // 判断左上方
    
31.         for (s = i-1, t = j-1; s >= 0 && t >= 0; s--, t--)
    
32.         {
    
33.                 if (queen[s][t] == 1)
    
34.                 {
    
35.                         return 0;
    
36.                 }
    
37.         }
    
38. 
    
39.         // 判断右上方
    
40.         for (s = i+1, t = j+1; s < 8 && t < 8; s++, t++)
    
41.         {
    
42.                 if (queen[s][t] == 1)
    
43.                 {
    
44.                         return 0;
    
45.                 }
    
46.         }
    
47. 
    
48.         // 判断左下方
    
49.         for (s = i+1, t = j-1; s < 8 && t >= 0; s++, t--)
    
50.         {
    
51.                 if (queen[s][t] == 1)
    
52.                 {
    
53.                         return 0;
    
54.                 }
    
55.         }
    
56. 
    
57.         // 判断右下方
    
58.         for (s = i+1, t = j+1; s < 8 && t < 8; s++, t++)
    
59.         {
    
60.                 if (queen[s][t] == 1)
    
61.                 {
    
62.                         return 0;
    
63.                 }
    
64.         }
    
65. 
    
66.         // 经过上面层层关卡还能存活，那么说明符合条件,返回1
    
67.         return 1;
    
68. }
    
69. 
    
70. void setQueen(int col, int (*queen)[8])
    
71. {
    
72.         int i, j, row;
    
73. 
    
74.         // 所有皇后放置完毕
    
75.         if (col == 8)
    
76.         {
    
77.                 for (i = 0; i < 8; i++)
    
78.                 {
    
79.                         for (j = 0; j < 8; j++)
    
80.                         {
    
81.                                 if (queen[i][j] != 0)
    
82.                                 {
    
83.                                         printf("Q ");
    
84.                                 }
    
85.                                 else
    
86.                                 {
    
87.                                         printf("* ");
    
88.                                 }
    
89.                         }
    
90.                         putchar('\n');
    
91.                 }
    
92. 
    
93.                 putchar('\n');
    
94.                 count++;
    
95. 
    
96.                 return;
    
97.         }
    
98. 
    
99.         // 迭代每一行
    
100.         for (row = 0; row < 8; row++)
     
101.         {
     
102.                 // 检查每一行中对应的每一列能否放置皇后
     
103.                 if (check(row, col, queen))
     
104.                 {
     
105.                         // 如果queen[row][col]符合条件，则放置皇后
     
106.                         queen[row][col] = 1;
     
107.                         // col+1，进入下一层递归
     
108.                         setQueen(col+1, queen);
     
109.                         // 只有两种情况会执行下面语句
     
110.                         // 1. col+1遇到所有的row都不合适
     
111.                         // 2. 完成整个二维数组的放置
     
112.                         // 无论哪种情况，
     
113.                         queen[row][col] = 0;
     
114.                 }
     
115.         }
     
116. }
     
117. 
     
118. int main(void)
     
119. {
     
120.         int queen[8][8];
     
121.         int i, j;
     
122. 
     
123.         // 初始化二维数组，1表示已放置皇后，0表示没有
     
124.         for (i = 0; i < 8; i++)
     
125.         {
     
126.                 for (j = 0; j < 8; j++)
     
127.                 {
     
128.                         queen[i][j] = 0;
     
129.                 }
     
130.         }
     
131. 
     
132.         setQueen(0, queen);
     
133. 
     
134.         return 0;
     
135. }

复制代码

诚信肥宅

1

风与尘的誓约

汉末天子

正想知道

苏瓦奥术

朕想知道