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

betty3

朕想知道

wlwen1117

1

wednesdayyy

朕想知道

SAiKETSU

84144402100

1

Mamma

学习学习

鱼c123456

#include <stdio.h>

#define Q 8

int count;

int check(int row, int col, int (*queen)[Q]);
void setQueen(int col, int (*queen)[Q]);

int check(int row, int col, int (*queen)[Q])
{
        int i;

        for (i = 0; i < Q; i++)
        {
                if (queen[i][col] == 1)
                {
                        return 0;
                }
                if (queen[row][i] == 1)
                {
                        return 0;
                }
        }

        for (i = 0; i < col; i++)
        {
                if (row-(i+1) >= 0)
                {
                        if (queen[row-(i+1)][col-(i+1)] == 1)
                        {
                                return 0;
                        }
                }
                if (row+(i+1) < Q)
                {
                        if (queen[row+(i+1)][col-(i+1)] == 1)
                        {
                                return 0;
                        }
                }
        }

        for (i = 1; i < Q-col; i++)
        {
                if (row-i >= 0)
                {
                        if (queen[row-i][col+i] == 1)
                        {
                                return 0;
                        }
                }
                if (row+i < Q)
                {
                        if (queen[row+i][col+i] == 1)
                        {
                                return 0;
                        }
                }
        }

        return 1;
}

void setQueen(int col, int (*queen)[Q])
{
        int i, j, row;

        // 如果 col == 4, 打印四皇后棋盘
        if (col == Q)
        {
                for (i = 0; i < Q; i++)
                {
                        for (j = 0; j < Q; j++)
                        {
                                printf("%d ", queen[i][j]);
                        }
                        putchar('\n');
                }
                putchar('\n');

                count++;

                return;
        }

        for (row = 0; row < Q; row++)
        {
                if (check(row, col, queen))
                {
                        queen[row][col] = 1;
                        setQueen(col+1, queen);
                        queen[row][col] = 0;
                }
        }
}


int main(void)
{
        int array[Q][Q] = {0};
        int (*queen)[Q] = array;

        setQueen(0, queen);

        printf("%d\n", count);

        return 0;
}

aqi123

朕想知道

lpzju

朕想知道

Ian_Li

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

皮强强

朕不想知道

076923441086

答案出现

zft

ooooops

Little_Prince

朕想知道

马良ccc

朕想知道

夏季的春秋

朕想知道

groottt

朕想知道

零度体温

朕想知道

yukikonfire

1