用非递归回溯算法完成数独求解。 “数独”是一种智力游戏，一般认为起源于“正交拉丁方”，经日本 人推广后风靡全球。如下图是一个数独的示例，玩家需要根据9 ×9盘面上的已知数字，推理出所有剩余空格的数字，并且满足每 一行、每一列、每一个同色九宫内的数字均含1～9不重复： 5 3 8 2 7 5 4 5 3 7 6 3 2 8 6 5 9 4 3 97 数独的答案一般都是唯一的，如果有多个解也称为无解。用c++

下面是用非递归回溯算法完成数独求解的C++代码示例：

#include <iostream>
using namespace std;

const int N = 9; // 数独的边长
int grid[N][N]; // 数独矩阵

bool is_valid(int x, int y, int num)
{
    // 判断该数字是否与同行、同列、同宫内的数字重复
    for (int i = 0; i < N; i++) {
        if (grid[x][i] == num) return false;
        if (grid[i][y] == num) return false;
        int r = (x / 3) * 3 + i / 3, c = (y / 3) * 3 + i % 3;
        if (grid[r][c] == num) return false;
    }
    return true;
}

bool solve()
{
    int x = -1, y = -1;
    // 找到一个未填数字的位置
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 0) {
                x = i, y = j;
                break;
            }
        }
        if (x != -1) break;
    }
    // 如果所有位置都已填好，则数独已解决
    if (x == -1) return true;
    // 尝试填入数字 1~9
    for (int num = 1; num <= 9; num++) {
        if (is_valid(x, y, num)) {
            grid[x][y] = num;
            if (solve()) return true; // 继续递归求解
            grid[x][y] = 0; // 恢复未填状态
        }
    }
    return false; // 无解
}

int main()
{
    // 读入数独矩阵
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> grid[i][j];
        }
    }
    // 求解数独
    if (solve()) {
        // 输出解
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cout << grid[i][j] << " ";
            }
            cout << endl;
        }
    } else {
        cout << "No solution" << endl;
    }
    return 0;
}

该算法的基本思路是：依次尝试填入数字 1~9，如果当前格子可以填入该数字，则递归求解下一个格子的填法；如果当前格子不可填入该数字，则尝试下一个数字。如果所有数字都尝试过仍无法填入，则回溯到上一个格子，恢复未填状态，继续尝试下一个数字。直到所有格子都填好，或者发现无解为止。