八数码问题c++代码彦

八数码问题，也称为"15 puzzle"，是一个经典的回溯算法问题，通常使用棋盘表示8个数字(1到8)和一个空位(0)，目标是通过旋转数字使得它们按照升序排列并把空位填入合适的位置。以下是一个简单的C++代码示例：

#include <iostream>
#include <vector>

using namespace std;

enum Direction { UP, DOWN, LEFT, RIGHT };

bool isSafe(vector<int>& board, int row, int col, int num) {
    for (int i = 0; i <= row; ++i)
        if (board[i] == num)
            return false;
    for (int i = col; i >= 0; --i)
        if (board[row] == board[i])
            return false;
    return true;
}

void swap(vector<int>& board, int row1, int col1, int row2, int col2) {
    int temp = board[row1];
    board[row1] = board[row2];
    board[row2] = temp;
}

void solve(int board[], int row, int col, int n) {
    if (row == n - 1) {
        // 如果已经到达目的地，完成一次解
        cout << "Solution found:\n";
        for (int i = 0; i < n * n; ++i)
            cout << board[i] << ' ';
        cout << endl;
    } else if (row < n - 1) {
        // 检查上移是否合法
        if (isSafe(board, row + 1, col, board[row]))
            solve(board, row + 1, col, n);
    }
    // ...继续检查其他方向

    // 回溯：还原之前的操作
    // ...类似地检查下移、左移和右移，并添加相应的条件
}

int main() {
    vector<int> board(n * n, 0); // 初始化一个n*n大小的矩阵
    // ...填充初始状态
    solve(board.data(), 0, 0, n); // 开始求解
    return 0;
}