写一个C++代码解决八皇后问题

#include <stdio.h>
int a[9], book[9], sum = 0;// 八皇后问题
void dfs(int step)
{
int i, j;
// 如果步数达到8，那么说明已经找到了一个可行解
if (step == 8)
{
sum++;
printf("第%d种解法\n", sum);
for (i = 0; i < 8; i++)
{
printf("%d", a[i]);
}
printf("\n");
return;
}
for (i = 0; i < 8; i++)
{
// 如果没有被占用
if (book[i] == 0)
{
// 假设第step步可以放置
a[step] = i;
// 将这一列置为占用
book[i] = 1;
// 放置下一步皇后
dfs(step + 1);
// 恢复现场
book[i] = 0;
}
}
return;
}int main()
{
dfs(0);
return 0;
}

相关问题

C++代码用概率算法解决八皇后问题

以下是一种用概率算法解决八皇后问题的C++代码：

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

const int N = 8; // 皇后个数
int col[N]; // 列
int w[2 * N - 1]; // 主对角线
int e[2 * N - 1]; // 副对角线

// 判断是否能在第row行第col列放置皇后
bool check(int row, int col) {
    return !col[row] && !w[row - col + N - 1] && !e[row + col];
}

// 随机放置皇后
void place(int row) {
    if (row == N) return; // 找到了解
    int cnt = 0;
    int pos[N]; // 可以放置的列的位置
    for (int i = 0; i < N; i++) {
        if (check(row, i)) {
            pos[cnt++] = i;
        }
    }
    if (cnt == 0) return; // 没有可行的位置
    int x = rand() % cnt; // 随机选择一个位置
    col[row] = pos[x];
    w[row - col[row] + N - 1] = 1;
    e[row + col[row]] = 1;
    place(row + 1); // 递归放置下一行的皇后
}

// 打印结果
void print() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (col[i] == j) {
                cout << "Q ";
            } else {
                cout << ". ";
            }
        }
        cout << endl;
    }
    cout << endl;
}

int main() {
    srand(time(nullptr));
    int count = 0; // 解的个数
    for (int i = 0; i < 1000000; i++) { // 进行100万次随机尝试
        for (int j = 0; j < N; j++) {
            col[j] = w[j] = e[j] = 0;
        }
        place(0);
        if (col[0] != -1) { // 找到了解
            count++;
            cout << "Solution " << count << ":" << endl;
            print();
        }
    }
    cout << "Total solutions: " << count << endl;
    return 0;
}

该算法会进行100万次随机尝试，尝试次数可以根据实际情况进行调整。每次尝试时，先随机放置第一行的皇后，然后递归地放置下一行的皇后。在放置皇后时，先找出可以放置的列的位置，然后随机选择一个位置放置。如果找不到可行的位置，则回溯到上一行重新放置皇后。最后，统计解的个数并输出每个解的棋盘布局。

给出解决八皇后问题的c++代码

### 回答1：
以下是使用C语言解决八皇后问题的代码：

#include <stdio.h>
#include <stdlib.h>

#define N 8

int board[N][N] = {0}; // 用于存储棋盘
int count = 0; // 解的数量

// 打印解法
void print_solution() {
    int i, j;
    printf("Solution %d:\n", ++count);
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            printf("%c ", board[i][j] ? 'Q' : '.');
        }
        printf("\n");
    }
}

// 检查是否可以在(row, col)位置放置皇后
int check(int row, int col) {
    int i, j;

    // 检查列
    for (i = 0; i < row; i++) {
        if (board[i][col]) {
            return 0;
        }
    }

    // 检查左上方
    for (i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j]) {
            return 0;
        }
    }

    // 检查右上方
    for (i = row - 1, j = col + 1; i >= 0 && j < N; i--, j++) {
        if (board[i][j]) {
            return 0;
        }
    }

    return 1;
}

// 解决八皇后问题
void solve(int row) {
    int col;

    // 找到解
    if (row == N) {
        print_solution();
        return;
    }

    // 在每一列尝试放置皇后
    for (col = 0; col < N; col++) {
        if (check(row, col)) {
            board[row][col] = 1;
            solve(row + 1);
            board[row][col] = 0;
        }
    }
}

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

该代码使用递归算法解决八皇后问题，通过在每一行中尝试在每一列中放置一个皇后，然后递归到下一行，直到找到解为止。在找到解时，该代码会将解打印出来。

### 回答2：
以下是一个用C代码解决八皇后问题的示例：

#include <stdio.h>

#define N 8

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

int isSafe(int board[N][N], int row, int col) {
    // 检查同一行是否有皇后
    for (int i = 0; i < col; i++) {
        if (board[row][i]) {
            return 0;
        }
    }
    // 检查左上对角线是否有皇后
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j]) {
            return 0;
        }
    }
    // 检查左下对角线是否有皇后
    for (int i = row, j = col; i < N && j >= 0; i++, j--) {
        if (board[i][j]) {
            return 0;
        }
    }
    return 1;
}

int solveNQueens(int board[N][N], int col) {
    if (col == N) {
        // 所有皇后都已放置，打印解决方案
        printSolution(board);
        return 1;
    }
    int count = 0;
    for (int i = 0; i < N; i++) {
        if (isSafe(board, i, col)) {
            // 递归放置下一个皇后
            board[i][col] = 1;
            count += solveNQueens(board, col + 1);
            // 回溯，将该位置重新置为0
            board[i][col] = 0;
        }
    }
    return count;
}

int main() {
    int board[N][N] = {0};  // 初始化棋盘
    int totalSolutions = solveNQueens(board, 0);
    printf("Total solutions: %d\n", totalSolutions);
    return 0;
}

这是一个经典的回溯算法解决八皇后问题的实现。它使用递归的方式依次将皇后放置在每一列，然后检查当前位置是否安全，即是否与已放置的皇后冲突（同行、同列或对角线）。如果安全，递归调用下一列的放置。当所有皇后都已放置，即col达到N时，打印解决方案并返回1。在每一列中，对于每一行，都会尝试放置皇后并继续递归。如果找到了一个解决方案，则计数器count增加1，并进行回溯，重置该位置并尝试下一个可能的位置。

在主函数中，我们初始化棋盘并调用solveNQueens函数开始解决八皇后问题。最后，我们输出总解决方案的数量。

### 回答3：
八皇后问题是指在8×8的国际象棋上摆放八个皇后，使得它们彼此之间无法攻击到对方。以下是一个C语言解决八皇后问题的代码示例：

#include <stdio.h>
#define N 8

int board[N][N];

// 检查在特定位置(row, col)上是否可以放置皇后
int canPlaceQueen(int row, int col) {
    int i, j;

    // 检查当前列上是否已经有皇后
    for (i = 0; i < row; i++) {
        if (board[i][col] == 1) {
            return 0;
        }
    }

    // 检查当前位置的左上方是否有皇后
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 1) {
            return 0;
        }
    }

    // 检查当前位置的右上方是否有皇后
    for (i = row, j = col; i >= 0 && j < N; i--, j++) {
        if (board[i][j] == 1) {
            return 0;
        }
    }

    return 1;
}

// 使用回溯法求解八皇后问题
int solveNQueens(int row) {
    int i;

    // 完成所有行的放置，则找到了一个解
    if (row >= N) {
        return 1;
    }

    // 遍历当前行的每一列
    for (i = 0; i < N; i++) {
        // 检查当前位置是否可以放置皇后
        if (canPlaceQueen(row, i) == 1) {
            // 在当前位置放置皇后
            board[row][i] = 1;

            // 递归地检查下一行是否可以放置皇后
            if (solveNQueens(row + 1) == 1) {
                return 1;
            }

            // 如果下一行不能放置皇后，则回溯，尝试下一个位置
            board[row][i] = 0;
        }
    }

    return 0;
}

// 打印解决八皇后问题的结果
void printSolution() {
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }
}

int main() {
    if (solveNQueens(0) == 1) {
        printSolution();
    } else {
        printf("No solution found.");
    }
    return 0;
}

以上是八皇后问题的C语言解决代码。代码中使用回溯法递归地在每一行的每一列尝试放置皇后，通过检查当前位置的列、左上方和右上方是否已经有皇后来确定是否可以放置。如果成功放置所有皇后，则打印出结果；否则输出无解。