如何消除回溯算法求解数独时的垃圾值？

Hey there! The core issue you're facing is exactly what you suspected—your backtracking logic isn't undoing the bitwise changes to the line, row, and box arrays after recursive calls. Let's break down the fixes step by step, plus address a few other small issues that are causing your program to fail.

Key Problem: Undoing Bitwise Operations During Backtracking #

When you set a number in an empty cell, you update line[i], row[j], and box[] with |= num2. But when backtracking (i.e., when that number doesn't lead to a valid solution), you need to reverse those changes to restore the state for the next possible number. To undo a bitwise OR, you use &= ~num2—this clears exactly the bit that was set by num2.

Additional Issues to Fix #

1. Unused Return Values: Your solve function is declared as int but has no return statement, which causes undefined behavior. Change it to void.
2. Backtracking Flow: Your solve1 function returns immediately after the first recursive call, without checking if the recursion found a solution. You need to:
   • Check if the recursive call succeeds (return 1 if solved, 0 otherwise)
   • Restore map[i][j] to 0 and undo the bitwise changes if the current number doesn't work
3. Bitwise Mask for Valid Numbers: The ~ operator in C flips all bits (including sign bits for signed integers). Use 0x1ff (a mask for the first 9 bits, since we're dealing with numbers 1-9) to avoid issues with negative numbers.
4. Avoid Modifying Original Map in write: Your write function modifies the map array while converting binary to decimal, which corrupts the state for further backtracking. Calculate the decimal value without altering the original map.

Fixed Code #

#include<stdio.h>
int map[9][9]; //2-Dimensional array to store Sudoku
int line[9];
int row[9];
int box[9];

void solve(int(*map)[9]) { // Changed to void since no return value
    int i, j;
    for (i = 0; i<9; i++)
        for (j = 0; j < 9; j++) {
            line[i] |= map[i][j];
            row[j] |= map[i][j];
            box[(j / 3) + 3 * (i / 3)] |= map[i][j];
        }
}

// Returns 1 if solved, 0 otherwise
int solve1(int(*map)[9]) {
    short i = 0, j = 0;
    int num, num1, num2;
    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            if (map[i][j] == 0) // If the cell is empty
            {
                // Use 0x1ff mask to only keep the first 9 bits (numbers 1-9)
                num = 0x1ff & (~(line[i] | row[j] | box[(j / 3) + 3 * (i / 3)]));
                for (num1 = 1; num1 <= 9; num1++) {
                    num2 = 1 << num1;
                    if (num2 & num) // Check if this number is allowed
                    {
                        // Set the cell and update bitwise arrays
                        map[i][j] = num2;
                        line[i] |= num2;
                        row[j] |= num2;
                        box[(j / 3) + 3 * (i / 3)] |= num2;
                        
                        // Recursively solve; if successful, return 1 (done)
                        if (solve1(map)) {
                            return 1;
                        }
                        
                        // Backtrack: undo the changes
                        map[i][j] = 0;
                        line[i] &= ~num2;
                        row[j] &= ~num2;
                        box[(j / 3) + 3 * (i / 3)] &= ~num2;
                    }
                }
                // Tried all numbers, no solution from this path
                return 0;
            }
        }
    }
    // All cells filled, write the solution
    write(map);
    return 1; // Indicate solution found
}

void read(int(*map)[9]) { // Changed to void for consistency
    int i, j, num1;
    FILE*FP1 = fopen("data.txt", "r");
    if (!FP1) { // Add error checking for file open
        printf("Failed to open data.txt\n");
        return;
    }
    for (i = 0; i < 9; i++)
        for (j = 0; j < 9; j++) {
            fscanf(FP1, "%d", &num1);
            if (num1 != 0) {
                map[i][j] = 1 << num1; // Convert to bit representation
            } else {
                map[i][j] = 0;
            }
        }
    fclose(FP1);
}

void write(int(*map)[9]) { // Changed to void
    int i, j, idx, temp;
    FILE*FP2 = fopen("result.txt", "a");
    if (!FP2) { // Add error checking
        printf("Failed to open result.txt\n");
        return;
    }
    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            idx = 0;
            temp = map[i][j]; // Use a temp variable to avoid modifying original map
            while (temp != 1) {
                temp = temp >> 1;
                idx++;
            }
            fprintf(FP2, "%d ", idx);
        }
        fprintf(FP2, "\n");
    }
    fclose(FP2);
}

int main(void) {
    // Initialize line, row, box to 0 before use
    for (int k = 0; k < 9; k++) {
        line[k] = 0;
        row[k] = 0;
        box[k] = 0;
    }
    read(map);
    solve(map);
    solve1(map);
    return 0;
}

Explanation of Key Fixes #

• Backtracking Undo: After a recursive call to solve1 fails (returns 0), we set map[i][j] back to 0 and use &= ~num2 to clear the bit we set in line, row, and box. This restores the state to before we tried that number, allowing other possibilities to be tested.
• Recursion Success Check: The solve1 function returns 1 when a solution is found, so as soon as a valid path is found, we propagate that success up the recursion stack instead of continuing to try other numbers.
• Bit Mask: Using 0x1ff & ~(...) ensures we only work with the first 9 bits, avoiding issues with sign extension from the ~ operator.
• File Error Checking: Added checks for failed file opens to avoid crashes if data.txt or result.txt can't be accessed.
• Initialization: Explicitly initialized line, row, and box to 0 in main to avoid garbage initial values.

内容的提问来源于stack exchange，提问作者Kremlin