欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

八皇后问题

程序员文章站 2022-05-25 12:33:05
...

问题描述
在8*8的国际象棋棋盘中,摆放8个皇后,使得每一行、每一列、每一条斜线上都只有一个皇后。
问题分析
先在第一行的第一个位置摆放第一个皇后
八皇后问题
接着在第二行顺序查找摆皇后的位子
八皇后问题
以此类推:
八皇后问题
八皇后问题
下一行没有符合摆放皇后的位置。说明上一行摆放的皇后位置不合适。返回上一行重新摆放皇后。(开始回溯)
八皇后问题
当前行依旧摆放不了皇后,继续回溯
八皇后问题
以此类推直到八个皇后都放到棋盘上。
算法描述:
八皇后问题
记录每个坐标的状态:
用数组:
col[8]——–记录每一列的状态
left[15]——记录每一条左斜线的状态
right[15]—–记录每一条右斜线的状态
坐标和左右斜线的关系:
(i,j)
left[i+j]
right[7+i-j]
用Queen[8]来记录皇后的坐标—-下标代表皇后所在的行,所对应的值代表皇后所在的列。

#include<stdio.h>
#include<stdlib.h>
int col[8] = { 0 };//用来记录皇后在每一行的状态
int Queen[8];//用来记录皇后的坐标
int left[15] = { 0 }, right[15] = { 0 };//分别用来记录皇后在每一条斜线(左右)的状态
int count = 0;//用来记录摆法的组数
//输出八皇后
void printQueen(int Queen[8]){
    for (int i = 0; i < 8; i++){
        for (int j = 0; j < 8; j++){
            if (Queen[i] == j){
                printf(" $  ");
            }
            else{
                printf(" +  ");
            }
        }
        printf("\n\n");
    }
    printf("\n\n");
}
//八皇后问题
void queen(int i){
    for (int j = 0; j < 8; j++){
        if (!col[j] && !left[i + j] && !right[7 + i - j]){
            //证明当前位置和之前摆放皇后的位置不发生冲突,(当前位置可以摆放皇后)
            Queen[i] = j;//在当前位置摆放皇后
            //更改当前位置的状态
            col[j] = left[i + j] = right[7 + i - j] = 1;
            if (i < 7){
                queen(i + 1);//摆放下一个皇后
                //当前行摆放不了皇后,开始回溯,更改上一个皇后的位置
                col[j] = left[i + j] = right[7 + i - j] = 0;

            }
            else{
                printf("第%d组\n", ++count);
                printQueen(Queen);
                //找下一组解
                col[j] = left[i + j] = right[7 + i - j] = 0;
            }
        }
    }
}
int main(void){
    queen(0);
    printf("共计:%d\n", count);
    system("pause");
    return 0;
}

调试结果:
八皇后问题

相关标签: 八皇后