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

hjers

1

1003826976

11111

Akihisa

cc

克里斯保罗

朕想知道

夜雨闻铃

朕想知道

echohah

朕想知道

乔宽

朕想知道

ShaoDaria

朕想知道

ShaoDaria

朕想知道

陌曦衣

让我瞅瞅

AINR

1

huoxr

想看

月无涯

kk

飘逸的光头

看答案

joker__

朕想知道

DT_Nelson

I want to know.

DT_Nelson

#include <stdio.h>

#define S 8

int chbrd[S][S];
int count = 0;

void init(void){
        int i, j;
        for(i = 0; i < S; i++){
                for(j = 0; j < S; j++){
                        chbrd[i][j] = 0;
                }
        }
}

void disp(void){
        int i, j;
        for(i = 0; i < S; i++){
                for(j = 0; j < S; j++){
                        printf("%d ", chbrd[i][j]);
                }
                putchar('\n');
        }
        putchar('\n');
}

_Bool issafe(int x, int y){
        int i, j;
        for(i = 0; i < S; i++){
                if(chbrd[x][i] == 1){
                        return 0;
                }
        }
        for(i = 0; i < S; i++){
                if(chbrd[i][y] == 1){
                        return 0;
                }
        }

        for(i = x, j = y; i>=0 && j<S; i--, j++){
                if(chbrd[i][j] == 1){
                        return 0;
                }
        }
        for(i = x, j = y; i>=0 && j>=0; i--, j--){
                if(chbrd[i][j] == 1){
                        return 0;
                }
        }
        return 1;
}

void next_queen(int x){
        int i, j;
        if(x == S){
                count++;
                disp();
                return;
        }
        for(i = 0; i < S; i++){
                if(!issafe(x, i)){
                        continue;
                }
                chbrd[x][i] = 1;
                next_queen(x+1);
                chbrd[x][i] = 0;
        }
}

int main(void){
        init();
        next_queen(0);
        printf("There are %d solutions in total.\n", count);
        return 0;
}

juhugufudu

aa

清尘yt

打卡学习

可爱的失踪人口

朕想知道