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

betty3

朕想知道

wlwen1117

1

wednesdayyy

朕想知道

SAiKETSU

84144402100

1

Mamma

学习学习

鱼c123456

1. #include <stdio.h>
   
2. 
   
3. #define Q 8
   
4. 
   
5. int count;
   
6. 
   
7. int check(int row, int col, int (*queen)[Q]);
   
8. void setQueen(int col, int (*queen)[Q]);
   
9. 
   
10. int check(int row, int col, int (*queen)[Q])
    
11. {
    
12.         int i;
    
13. 
    
14.         for (i = 0; i < Q; i++)
    
15.         {
    
16.                 if (queen[i][col] == 1)
    
17.                 {
    
18.                         return 0;
    
19.                 }
    
20.                 if (queen[row][i] == 1)
    
21.                 {
    
22.                         return 0;
    
23.                 }
    
24.         }
    
25. 
    
26.         for (i = 0; i < col; i++)
    
27.         {
    
28.                 if (row-(i+1) >= 0)
    
29.                 {
    
30.                         if (queen[row-(i+1)][col-(i+1)] == 1)
    
31.                         {
    
32.                                 return 0;
    
33.                         }
    
34.                 }
    
35.                 if (row+(i+1) < Q)
    
36.                 {
    
37.                         if (queen[row+(i+1)][col-(i+1)] == 1)
    
38.                         {
    
39.                                 return 0;
    
40.                         }
    
41.                 }
    
42.         }
    
43. 
    
44.         for (i = 1; i < Q-col; i++)
    
45.         {
    
46.                 if (row-i >= 0)
    
47.                 {
    
48.                         if (queen[row-i][col+i] == 1)
    
49.                         {
    
50.                                 return 0;
    
51.                         }
    
52.                 }
    
53.                 if (row+i < Q)
    
54.                 {
    
55.                         if (queen[row+i][col+i] == 1)
    
56.                         {
    
57.                                 return 0;
    
58.                         }
    
59.                 }
    
60.         }
    
61. 
    
62.         return 1;
    
63. }
    
64. 
    
65. void setQueen(int col, int (*queen)[Q])
    
66. {
    
67.         int i, j, row;
    
68. 
    
69.         // 如果 col == 4, 打印四皇后棋盘
    
70.         if (col == Q)
    
71.         {
    
72.                 for (i = 0; i < Q; i++)
    
73.                 {
    
74.                         for (j = 0; j < Q; j++)
    
75.                         {
    
76.                                 printf("%d ", queen[i][j]);
    
77.                         }
    
78.                         putchar('\n');
    
79.                 }
    
80.                 putchar('\n');
    
81. 
    
82.                 count++;
    
83. 
    
84.                 return;
    
85.         }
    
86. 
    
87.         for (row = 0; row < Q; row++)
    
88.         {
    
89.                 if (check(row, col, queen))
    
90.                 {
    
91.                         queen[row][col] = 1;
    
92.                         setQueen(col+1, queen);
    
93.                         queen[row][col] = 0;
    
94.                 }
    
95.         }
    
96. }
    
97. 
    
98. 
    
99. int main(void)
    
100. {
     
101.         int array[Q][Q] = {0};
     
102.         int (*queen)[Q] = array;
     
103. 
     
104.         setQueen(0, queen);
     
105. 
     
106.         printf("%d\n", count);
     
107. 
     
108.         return 0;
     
109. }
     

复制代码

aqi123

朕想知道

lpzju

朕想知道

Ian_Li

回复“朕想知道”查看完整代码！

皮强强

朕不想知道

076923441086

答案出现

zft

ooooops

Little_Prince

朕想知道

马良ccc

朕想知道

夏季的春秋

朕想知道

groottt

朕想知道

零度体温

朕想知道

yukikonfire

1