c - C 中的递归回溯算法求解数独

Question

我必须在大学的数独.c 中实现递归求解方法。
我努力尝试，但我的所有实现都不起作用。
我是 C 编程的绝对新手，所以我对使用这个数独回溯算法感到绝望。

有人可以帮助我吗？

solve方法是空的，所以这个方法中的所有内容都只是我的尝试。

数独.h

#ifndef _SUDOKU_H_
#define _SUDOKU_H_

#define SIZE 9
#define SQRT_SIZE 3

void init(int begin[SIZE][SIZE]);
void print();
int checkValueInField(int value, int row, int col);
int setValueInField(int value, int row, int col);
int removeValueFromField(int row, int col);
int getValueFromField(int row, int col);
int solve(int row, int col);

#endif /* _SUDOKU_H_ */

数独.c

#include "sudoku.h"
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define SIZE 9
#define SQRT_SIZE 3

int field[SIZE][SIZE];
int initial[SIZE][SIZE];


/* Initializes the sudoku array.
 * The field initial keeps the original start value for
 * figuring out if a value is fixed or can be changed. */
void init(int begin[SIZE][SIZE]) {
    memcpy(field, begin, SIZE * SIZE * sizeof(int));
    memcpy(initial, begin, SIZE * SIZE * sizeof(int));
}

/* really pretty prints the sudoku array */
void print() {
    int row, col;
    // print the first line
    printf("||");
    for (col = 0; col < SIZE - 1; col++) {
        if (col % SQRT_SIZE == SQRT_SIZE - 1)
            printf("===++");
        else
            printf("===+");
    }
    printf("===||\n");
    // loop through all rows of the array
    for (row = 0; row < SIZE; row++) {
        // print the line with field values
        for (col = 0; col < SIZE; col++) {
            if (col % SQRT_SIZE == 0)
                printf("|| ");
            else
                printf("| ");
            if (field[row][col] == 0)
                printf("  ");
            else
                printf("%d ", field[row][col]);
        }
        // print the separation line;
        // depending on the result of the modulo operation
        // print a single or double line
        printf("||\n||");
        if (row % SQRT_SIZE == SQRT_SIZE - 1) {
            for (col = 0; col < SIZE - 1; col++) {
                if (col % SQRT_SIZE == SQRT_SIZE - 1)
                    printf("===++");
                else
                    printf("===+");
            }
            printf("===||\n");
        }
        else {
            for (col = 0; col < SIZE - 1; col++) {
                if (col % SQRT_SIZE == SQRT_SIZE - 1)
                    printf("---++");
                else
                    printf("---+");
            }
            printf("---||\n");
        }
    }
}

/* Checks if the value is valid and can be set into the field.
 * The function returns false if the value is already present or
 * has been one of the initial values. */
int checkValueInField(int value, int row, int col) {
    int i, r, c;
    int squareRow;
    int squareCol;
    // checks for initial values
    if (initial[row][col] != 0) {
        if (initial[row][col] == value)
            return 1;
        else
            return 0;
    }

    // check horizontally
    for (i = 0; i < SIZE; i++) {
        if (field[row][i] == value) return 0;
    }

    // check vertically
    for (i = 0; i < SIZE; i++) {
        if (field[i][col] == value) return 0;
    }

    // check square
    squareRow = row / SQRT_SIZE;
    squareCol = col / SQRT_SIZE;
    for (r = squareRow * SQRT_SIZE; r < squareRow * SQRT_SIZE + SQRT_SIZE; r++) {
        for (c = squareCol * SQRT_SIZE; c < squareCol * SQRT_SIZE + SQRT_SIZE; c++) {
            if (field[r][c] == value) return 0;
        }
    }

    return 1;
}

/* Set a value in the sudoku field if the field is empty.
 * The method returns false if the field contains a fixed number. */
int setValueInField(int value, int row, int col) {
    if (initial[row][col] == 0) {
        field[row][col] = value;
        return 1;
    }
    else if (initial[row][col] == value)
        return 1;
    return 0;
}

/* Removes a value in the sudoku field if it doesn't contain an initial value.
 * The method returns false if the field contains a fixed number and cannot be
 * removed. */
int removeValueFromField(int row, int col) {
    if (initial[row][col] == 0) {
        field[row][col] = 0;
        return 1;
    }
    return 0;
}

/* Returns the value in the field */
int getValueFromField(int row, int col) {
    return field[row][col];
}

/* Return true if you've found a valid solution for the sudoku. Use the
 * return value to abort the backtracking algorithm if you've found the
 * first solution, otherwise you would search for a possible solution. */
int solve(int row, int col) {
    /* Implement a backtracking for solving the sudoku */
    for (int i = 1; i <= 9; i++) {
        if ((checkValueInField(i, row, col)) == 1) {
            setValueInField(i, row, col);
        }
        solve(row, col + 1);
        solve(row + 1, col);
    }
    return 0;
}

ma​​in.c

#include <stdio.h>
#include "sudoku.h"

int main(int argc, char * const argv[]) {
    int initial[SIZE][SIZE] = {
        {0, 1, 0, 0, 0, 9, 0, 5, 0},
        {0, 9, 0, 0, 0, 0, 4, 8, 0},
        {0, 6, 0, 1, 0, 4, 0, 0, 0},
        {0, 0, 5, 0, 0, 0, 9, 3, 0},
        {0, 0, 0, 7, 0, 2, 0, 0, 0},
        {0, 2, 1, 0, 0, 0, 8, 0, 0},
        {4, 0, 0, 0, 8, 0, 6, 0, 9},
        {0, 0, 0, 0, 6, 0, 5, 0, 3},
        {2, 0, 0, 0, 3, 0, 0, 0, 0},
    };

    init(initial);
    print();
    solve(0, 0);
    print();

    return 0;
}

Answer 1

您可能想查看what is a backtracking algorithm

在网格中不断移动

您的解决方案将一次解决一个位置(按 row 和 col 跟踪)，并递归检查解决下一个位置。

所以你的求解函数至少应该遍历网格

int solve(int row, int col) {
    // solve next column in the current row
    return solve(row, col + 1);
}

正如您所看到的，问题是，在不检查其他行的情况下，列将无限期地增长。 (顺便说一句，C 中数组的第一个元素的索引为 0 )

因此，一旦到达这一行的末尾，我们就需要移动到另一行(假设END_COLUMN_INDEX包含最后一列的索引)

   if(col == END_COLUMN_INDEX) { // we just reached the end of the current row
        return solve(row+1, 0); // solve the beginning of the next row
   }

现在您的求解将自动移至下一行，但是当我们到达最后一行时该怎么办 (假设END_ROW_INDEX包含行列的索引)

   if((col == END_COLUMN_INDEX) && (row == END_ROW_INDEX)) { // we reached the end of the grid meaning that we might have successfully solved the whole grid
       return 1; // return true
   }

现在逐步介绍此时应实现的内容。

solve(0,0) -> solve(0,1)
solve(0,1) -> solve(0,2)
solve(0,2) -> solve(0,3)
...
solve(0,END_COLUMN_INDEX - 1) -> solve(0, END_COLUMN_INDEX)
solve(0, END_COLUMN_INDEX) -> solve(1, 0)
...
...
solve(END_ROW_INDEX , END_COLUMN_INDEX - 1) -> solve(END_ROW_INDEX , END_COLUMN_INDEX) -> return true
(the true value is returned through each upper level of recursion)

我们现在正在网格中递归移动

解决数独

对于您需要检查的每个单元格

1. 如果单元格已填满(您可以求解下一个单元格)

2. 检查值(1 到 9，使用 checkValueInField ):

3. 如果找到的值没问题，您可以将该值存储在网格中 (setValueInField) 并尝试求解下一个单元格

4. 否则尝试下一个值

5. 如果我们尝试了所有值但没有合适的怎么办？

6. 这意味着上层递归是错误的，因此求解函数将返回false以表明前一个单元格中的值是错误的(上层将在步骤1 或 3)

7. 测试下一个单元格返回的内容解决(在步骤 1 或 3 中)

8. true，意味着我们解决了下一个单元格和所有后续单元格

9. false 表示我们有一个值导致下一个单元无法求解，我们可能想尝试其他值(回溯)。

当返回 false 到递归的上限值时，您一定不要忘记将当前单元格的值恢复为其原始值 (removeValueFromField)。

把它们放在一起

此时，您应该拥有解决问题并编写递归数独求解函数的所有指南。

此外，互联网上充满了数独求解代码的精彩示例。