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

克里斯保罗

朕想知道

夜雨闻铃

朕想知道

echohah

朕想知道

乔宽

朕想知道

ShaoDaria

朕想知道

ShaoDaria

朕想知道

陌曦衣

让我瞅瞅

AINR

1

huoxr

想看

月无涯

kk

飘逸的光头

看答案

joker__

朕想知道

DT_Nelson

I want to know.

DT_Nelson

1. #include <stdio.h>
   
2. 
   
3. #define S 8
   
4. 
   
5. int chbrd[S][S];
   
6. int count = 0;
   
7. 
   
8. void init(void){
   
9.         int i, j;
   
10.         for(i = 0; i < S; i++){
    
11.                 for(j = 0; j < S; j++){
    
12.                         chbrd[i][j] = 0;
    
13.                 }
    
14.         }
    
15. }
    
16. 
    
17. void disp(void){
    
18.         int i, j;
    
19.         for(i = 0; i < S; i++){
    
20.                 for(j = 0; j < S; j++){
    
21.                         printf("%d ", chbrd[i][j]);
    
22.                 }
    
23.                 putchar('\n');
    
24.         }
    
25.         putchar('\n');
    
26. }
    
27. 
    
28. _Bool issafe(int x, int y){
    
29.         int i, j;
    
30.         for(i = 0; i < S; i++){
    
31.                 if(chbrd[x][i] == 1){
    
32.                         return 0;
    
33.                 }
    
34.         }
    
35.         for(i = 0; i < S; i++){
    
36.                 if(chbrd[i][y] == 1){
    
37.                         return 0;
    
38.                 }
    
39.         }
    
40. 
    
41.         for(i = x, j = y; i>=0 && j<S; i--, j++){
    
42.                 if(chbrd[i][j] == 1){
    
43.                         return 0;
    
44.                 }
    
45.         }
    
46.         for(i = x, j = y; i>=0 && j>=0; i--, j--){
    
47.                 if(chbrd[i][j] == 1){
    
48.                         return 0;
    
49.                 }
    
50.         }
    
51.         return 1;
    
52. }
    
53. 
    
54. void next_queen(int x){
    
55.         int i, j;
    
56.         if(x == S){
    
57.                 count++;
    
58.                 disp();
    
59.                 return;
    
60.         }
    
61.         for(i = 0; i < S; i++){
    
62.                 if(!issafe(x, i)){
    
63.                         continue;
    
64.                 }
    
65.                 chbrd[x][i] = 1;
    
66.                 next_queen(x+1);
    
67.                 chbrd[x][i] = 0;
    
68.         }
    
69. }
    
70. 
    
71. int main(void){
    
72.         init();
    
73.         next_queen(0);
    
74.         printf("There are %d solutions in total.\n", count);
    
75.         return 0;
    
76. }

复制代码

juhugufudu

aa

清尘yt

打卡学习

可爱的失踪人口

朕想知道

gzq07

朕想知道

Juejiu66

xx

分析的化身

朕想知道