c - 如何从回溯算法中删除垃圾值？

Question

在我提问之前，我的英语不好，所以很难理解我的话。

我一直在尝试找出如何使用位运算符解决数独问题。 第一个想法是声明一个三维数组，添加9个适合9-9的数字，并排除任何坐标对应的行、列和框的数量。 但是，我认为使用位运算符会进一步降低执行速度。

例如，如果数独的一列数字是1，我认为它是2的双平方。这相当于0000 0000 0010。 接下来，4 将被声明为 16，即 2 的第四个平方。 这相当于 0000 0001 0000

假设所有最初以这种方式提供的数独都已转换为二进制系统。 例如，如果第一行是 1,2,5/0,8,4/9,3,7，如果您使用“or”(|) 运算符，则可能会出现以下内容。 0011 1011 1110。 对这个数字使用“not”(~) 运算符将保存后面的数字。 1100 0100 0001。 这表明空格中的零个数是六个。

问题是有多个空白区域，在这种情况下，我选择输入较低的值，然后移至下一个空白区域。 如果放不下了，可以使用回溯回到前面。

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


int solve(int(*map)[9])
{
    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];
        }
}

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
            {
                num = (~(line[i] | row[j] | box[(j / 3) + 3 * (i / 3)]));   //Use 'not' operator to find that number
                for (num1 = 1; num1 <= 9; num1++)
                {
                    num2 = 1<<num1;
                    if (num2&num)   //If and operator were used and not 0, it would be one of the numbers that could fit into the space.
                    {           printf("%d %d %d    ", i, j, num2);
                        map[i][j] = num2;
                        line[i] |= num2;
                        row[j] |= num2;
                        box[(j / 3) + 3 * (i / 3)] |= num2;
                        solve1(map);
                    }
                }
                return;     //backtracking
            }
        }
    }
    write(map);
}

int read(int(*map)[9])
{
    int i, j, k, num1;
    FILE*FP1 = fopen("data.txt", "r");  //Read the Sudoku saved in data.txt using the pointer.
    for (i = 0; i < 9; i++)
        for (j = 0; j < 9; j++)
        {
            fscanf(FP1, "%d", &map[i][j]);
            num1 = map[i][j];
            if (map[i][j] != 0)     
            {
                map[i][j] = 1;
                map[i][j] = map[i][j] << num1;  //Converts decimal to binary
            }
        }
    fclose(FP1);
}

int write(int(*map)[9])
{
    int i, j, idx;
    FILE*FP2 = fopen("result.txt", "a");
    for (i = 0; i < 9; i++)
    {
        for (j = 0; j < 9; j++)
        {
            idx = 0;
            while (map[i][j] != 1)    //Converts binary to decimal
            {
                map[i][j] = map[i][j] >> 1;
                idx++;
            }
            fprintf(FP2, "%d ", idx);
        }
        fprintf(FP2, "\n");
    }
    fclose(FP2);
}

int main(void)
{
    read(map);
    solve(map);
    solve1(map);
    return 0;
}

但是debug的时候没有结果。 我已经知道这是一个问题。

line[i] |= num2;
row[j] |= num2;
box[(j / 3) + 3 * (i / 3)] |= num2;

回溯时，返回二维数组中的数字，但行/列/框中使用“或”运算符则不返回，留下垃圾箱的值。

如果我执行回溯时上述三个数组一起工作，我就可以解决问题。

有什么办法可以解决这个问题吗？

正如我之前所说，由于我不熟悉英语，您可能不太容易看到，但感谢您阅读它。

Answer 1

如果我理解得很好，您想要撤消 |=递归调用 solve1 后的操作？

您可以将 int 中的特定位设置为 0使用按位与 & :

int value; // value to modify
int bitIndex = 3; // Index of the bit to set to 0 (index starts from 0)

int mask = ~(1 << bitIndex); // All bits set to 1, except the one at bitIndex
value &= mask;

注意:如果 value属于 T 类型大于 int，mask应定义为T mask = ~((T)1 << bitIndex); .

就您而言，您几乎拥有面具:

line[i] |= num2; // set some bits to 1
line[i] &= ~num2; // set the same bits to 0