aiaiask.com©

开花即结果 提问即答案

八皇后问题的起源与C语言解决方案
原始问题:

八皇后问题的起源与C语言解决方案

解析:这是一个经典的回溯算法问题,我们可以使用递归的方式来解决。首先,我们需要一个数组来存储每一行皇后的位置。然后,我们从第一行开始,尝试在每一列放置皇后,如果当前位置不会导致冲突,我们就将皇后放在这个位置,并继续下一行。如果发现无法放置皇后,我们就回溯到上一行,改变皇后的位置。当所有皇后都放置好后,我们就找到了一个解。

代码如下:

#include <stdio.h>

#define N 8
int board[N][N];

void printSolution() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf(" %d ", board[i][j]);
        printf("
");
    }
}

int isSafe(int row, int col) {
    int i, j;
    for (i = 0; i < col; i++)
        if (board[row][i])
            return 0;
    for (i=row, j=col; i>=0 && j>=0; i--, j--)
        if (board[i][j])
            return 0;
    for (i=row, j=col; j>=0 && i<N; i++, j--)
        if (board[i][j])
            return 0;
    return 1;
}

int solveNQUtil(int col) {
    if (col >= N)
        return 1;
    for (int i = 0; i < N; i++) {
        if (isSafe(i, col)) {
            board[i][col] = 1;
            if (solveNQUtil(col + 1))
                return 1;
            board[i][col] = 0; // backtracking
        }
    }
    return 0; // solution does not exist
}

int solveNQ() {
    if (solveNQUtil(0) == 0) {
        printf("Solution does not exist");
        return 0;
    }
    printSolution();
    return 1;
}

int main() {
    solveNQ();
    return 0;
}

这段代码首先定义了一个8x8的棋盘,然后定义了一个函数来检查在给定的位置放置皇后是否安全。然后,我们使用递归的方式尝试在每一列放置皇后,如果当前位置不会导致冲突,我们就将皇后放在这个位置,并继续下一行。如果发现无法放置皇后,我们就回溯到上一行,改变皇后的位置。当所有皇后都放置好后,我们就找到了一个解。

八皇后问题的起源与C语言解决方案
https://www.aiaiask.com/ask/85807.html
AI / 模型DeepSeek
时间 / DATEApril 25, 2024, 10:53 AM
语言zh-CN
IP / 区域四川 成都