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

pixie0096

朕想知道

前面那个人好丑

朕想知道

不要打扰我

1

kelvinlewis777

朕想知道

兀凉

签到

1481821848

12

吕乐甜

朕想知道

milesl

什么情况

y12

真想知道

言覃Jack

真想知道

EmmmmmmTRUE

朕想知道

欧奇诺

.

嘟嘟橙

朕想知道

可爱的华子

朕想知道

Draem

Draem

#include <stdio.h>

int count = 0;

int check(int i, int j, int (*queen)[8]);
void setQueen(int i, int (*queen)[8]);

int check(int i, int j, int (*queen)[8])
{
        int s, t;

        // 判断行
        for (s = i, t = 0; t < 8; t++)
        {
                if (queen[s][t] == 1 && t != j)
                {
                        return 0;
                }
        }

        // 判断列
        for (t = j, s = 0; s < 8; s++)
        {
                if (queen[s][t] == 1 && s != i)
                {
                        return 0;
                }
        }

        // 判断左上方
        for (s = i-1, t = j-1; s >= 0 && t >= 0; s--, t--)
        {
                if (queen[s][t] == 1)
                {
                        return 0;
                }
        }

        // 判断右上方
        for (s = i+1, t = j+1; s < 8 && t < 8; s++, t++)
        {
                if (queen[s][t] == 1)
                {
                        return 0;
                }
        }

        // 判断左下方
        for (s = i+1, t = j-1; s < 8 && t >= 0; s++, t--)
        {
                if (queen[s][t] == 1)
                {
                        return 0;
                }
        }

        // 判断右下方
        for (s = i+1, t = j+1; s < 8 && t < 8; s++, t++)
        {
                if (queen[s][t] == 1)
                {
                        return 0;
                }
        }

        // 经过上面层层关卡还能存活，那么说明符合条件,返回1
        return 1;
}

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

        // 所有皇后放置完毕
        if (col == 8)
        {
                for (i = 0; i < 8; i++)
                {
                        for (j = 0; j < 8; j++)
                        {
                                if (queen[i][j] != 0)
                                {
                                        printf("Q ");
                                }
                                else
                                {
                                        printf("* ");
                                }
                        }
                        putchar('\n');
                }

                putchar('\n');
                count++;

                return;
        }

        // 迭代每一行
        for (row = 0; row < 8; row++)
        {
                // 检查每一行中对应的每一列能否放置皇后
                if (check(row, col, queen))
                {
                        // 如果queen[row][col]符合条件，则放置皇后
                        queen[row][col] = 1;
                        // col+1，进入下一层递归
                        setQueen(col+1, queen);
                        // 只有两种情况会执行下面语句
                        // 1. col+1遇到所有的row都不合适
                        // 2. 完成整个二维数组的放置
                        // 无论哪种情况，
                        queen[row][col] = 0;
                }
        }
}

int main(void)
{
        int queen[8][8];
        int i, j;

        // 初始化二维数组，1表示已放置皇后，0表示没有
        for (i = 0; i < 8; i++)
        {
                for (j = 0; j < 8; j++)
                {
                        queen[i][j] = 0;
                }
        }

        setQueen(0, queen);

        return 0;
}

诚信肥宅

1

风与尘的誓约

汉末天子

正想知道

苏瓦奥术

朕想知道