0

我正在尝试编写一个函数，该函数接受三个位向量，表示从位置 1-9 开始数独谜题的行、列和块中使用的数字。一个单元格只能使用未使用的数字，并且该函数应该返回所有向量中的数字是否强制一种可能性或是否存在多种可能性。我认为这意味着我必须合并所有三个向量，然后确定结果模式中“未设置”位的位置。

然而，我的函数在 gdb 中似乎并没有返回正确的掩码，即使它是受到这个推导的启发：http: //graphics.stanford.edu/~seander/bithacks.html#MaskedMerge

我正在尝试将一组合并到两组中，然后将第三组合并到前一个合并中，得出最终合并中 1 的数量，然后减去它以得出有多少个 0。

然后，我编写了以下函数：

   bool possibilities(unsigned short row, unsigned short col, unsigned short bloc)
   {

    unsigned int mask = (1 << col) - 1;
    unsigned int inbw = (row & ~mask) | (col & mask);

    unsigned int mask2 = (1 << bloc) - 1;
    unsigned int final = (inbw & ~mask2) | (bloc & mask2);

    int num_1s;
    while (result != 0) {
            result &= (result - 1);
            num_1s++;
    }

    int zeroes = 32 - num_1s; // 32 being the presumed number of bits in a short.

    if (zeroes == 1) return true;
    return false;
   }
4

2 回答 2

2

根据这份文件：

http://www.cplusplus.com/doc/tutorial/variables/

short 不小于 char。至少 16 位。因此，将零计算为 32 - num_1s 可能是错误的。

而不是这样做，您可以得到一个无符号短并用 1 填充它，在前 9 位设置 0。

var = 0xFFFFFE00

通过这种方式，您可以避免解决方案在很大程度上取决于您使用的变量的大小。

该问题的解决方案可能是这样的（假设 row、col 和 bloc 像上面一样）：

possibilities = row | col | bloc;
while (possibilities != 0) {
     num_0s += ((~possibilities)&1);
     possibilities = (possibilities >> 1);
}
于 2014-07-21T12:25:07.717 回答
0

如果我正确理解 , 和 (sic) 中的每一个row都是col位bloc掩码，其中的各个位（可能是位 0-8）代表数字 1-9 的存在，那么您的掩码是错误的（而且确实毫无意义）。例如，如果col设置了第 8 位，则将mask = (1 << col) - 11 向左移动 256 - 因为极不可能unsigned short超过 256 位宽，这会导致移位后为 0，然后在减去1.在这之后(row & ~mask) | (col & mask)将只是col因为~mask是0。

我想到了几个简单的选择：

1）根本不合并，只需分别对三个变量中的每一个进行popcount。一些现代处理器有一个 popcount 指令，所以如果你管理使用它，例如，通过编译器的内置函数（例如，__builtin_popcount），它甚至会更快。

2）单独屏蔽每个变量上的位并将它们移动到位置，例如：

const unsigned int mask = 0x1FF;
unsigned int final = (col & mask) | ((row & mask) << 9) | ((bloc & mask) << 18);

此外，不要从 32 中减去 1 的数量，而是从 27（= 3×9）中减去 1 的数量——如果三个变量中的每一个都最多可以设置 9 位，那么这就是 1 的最大数量。

编辑：可能是我误解了您通过合并尝试做的事情。如果您的意思是三个变量中所有 1 位的简单联合，那么它就unsigned int final = col | row | bloc不需要屏蔽了。然后你会从 9 中减去 popcount（1 位的数量）。

于 2014-07-21T12:27:32.000 回答