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

以下是使用非递归回溯算法完成数独求解的C语言代码：

#include <stdio.h>

#define N 9
#define UNASSIGNED 0

int grid[N][N];

// 检查在指定行和列中填入数字 n 是否有效
int is_valid(int row, int col, int n) {
    // 检查行中是否有重复数字
    for (int i = 0; i < N; i++) {
        if (grid[row][i] == n) {
            return 0;
        }
    }

    // 检查列中是否有重复数字
    for (int i = 0; i < N; i++) {
        if (grid[i][col] == n) {
            return 0;
        }
    }

    // 检查九宫格中是否有重复数字
    int box_row = row - row % 3;
    int box_col = col - col % 3;
    for (int i = box_row; i < box_row + 3; i++) {
        for (int j = box_col; j < box_col + 3; j++) {
            if (grid[i][j] == n) {
                return 0;
            }
        }
    }

    return 1;
}

// 在数独中查找未分配的位置
int find_unassigned(int *row, int *col) {
    for (*row = 0; *row < N; (*row)++) {
        for (*col = 0; *col < N; (*col)++) {
            if (grid[*row][*col] == UNASSIGNED) {
                return 1;
            }
        }
    }
    return 0;
}

// 使用非递归回溯算法求解数独
int solve_sudoku() {
    int row, col, num, found_unassigned;
    int stack_row[N*N], stack_col[N*N], stack_num[N*N], stack_top = -1;

    found_unassigned = find_unassigned(&row, &col);
    while (found_unassigned) {
        // 尝试填入数字 1~9
        num = 1;
        while (num <= 9) {
            if (is_valid(row, col, num)) {
                // 填入数字并将位置入栈
                grid[row][col] = num;
                stack_top++;
                stack_row[stack_top] = row;
                stack_col[stack_top] = col;
                stack_num[stack_top] = num;

                // 查找下一个未分配的位置
                found_unassigned = find_unassigned(&row, &col);
                break;
            }
            num++;
        }

        // 如果无法填入任何数字，则回溯
        if (num > 9) {
            // 回溯到最近的未分配位置并尝试填入下一个数字
            do {
                if (stack_top < 0) {
                    // 数独无解
                    return 0;
                }
                row = stack_row[stack_top];
                col = stack_col[stack_top];
                num = stack_num[stack_top];
                stack_top--;
                grid[row][col] = UNASSIGNED;
                found_unassigned = 1;
                for (int i = num + 1; i <= 9; i++) {
                    if (is_valid(row, col, i)) {
                        num = i;
                        grid[row][col] = num;
                        stack_top++;
                        stack_row[stack_top] = row;
                        stack_col[stack_top] = col;
                        stack_num[stack_top] = num;
                        found_unassigned = find_unassigned(&row, &col);
                        break;
                    }
                }
            } while (!found_unassigned);
        }
    }

    // 数独已解决
    return 1;
}

// 输出数独
void print_sudoku() {
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            printf("%d ", grid[row][col]);
        }
        printf("\n");
    }
}

int main() {
    // 读取数独
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            scanf("%d", &grid[row][col]);
        }
    }

    // 解决数独并输出结果
    if (solve_sudoku()) {
        print_sudoku();
    } else {
        printf("This sudoku cannot be solved.\n");
    }

    return 0;
}

在这个实现中，我们使用了一个栈来保存回溯过程中的状态。每当我们尝试在数独中填入一个数字时，如果该数字有效，则将该位置和数字入栈，并继续查找下一个未分配的位置；如果该数字无效，则继续尝试下一个数字。当无法填入任何数字时，我们从栈中取出最近的未分配位置，并尝试填入下一个数字，直到找到一个有效的数字或者回溯到数独的起始位置为止。如果无法找到任何未分配的位置，则数独无解。