斑马拼图 - C 中的约束满足

Question

我正在尝试阅读约束满足问题并尝试编写代码来解决一些示例问题。我遇到了 http://rosettacode.org/wiki/Zebra_puzzle#C.2B.2B to solve the classic zebra puzzle. 在罗塞塔代码网站给出的 C 代码中，有以下功能。我只给出了其中的几行。我不知道这两个 if 语句的目的是什么以及它们是如何工作的。有人可以解释一下吗？

int checkHouses(int ha[5][5])
{
...
    int c_add = 0, c_or = 0;
    int m_add = 0, m_or = 0;
    int d_add = 0, d_or = 0;
    int a_add = 0, a_or = 0;
    int s_add = 0, s_or = 0;

    for (int i = 0; i < 5; i++) {
        // Uniqueness tests.
        if (ha[i][C] >= 0) {
            c_add += (1 << ha[i][C]);
            c_or |= (1 << ha[i][C]);
        }
        if (ha[i][M] >= 0) {
            m_add += (1 << ha[i][M]);
            m_or |= (1 << ha[i][M]);
        }
        if (ha[i][D] >= 0) {
            d_add += (1 << ha[i][D]);
            d_or |= (1 << ha[i][D]);
        }
        if (ha[i][A] >= 0) {
            a_add += (1 << ha[i][A]);
            a_or |= (1 << ha[i][A]);
        }
        if (ha[i][S] >= 0) {
            s_add += (1 << ha[i][S]);
            s_or |= (1 << ha[i][S]);
        }
    }

    if ((c_add != c_or) || (m_add != m_or) || (d_add != d_or)
        || (a_add != a_or) || (s_add != s_or)) {
        return Invalid;
    }

    if ((c_add != 0b11111) || (m_add != 0b11111) || (d_add != 0b11111)
        || (a_add != 0b11111) || (s_add != 0b11111)) {

        return Underfull;
}

Answer 1

评论实际上解释了它：他们正在验证每个 x 值的 ha[0..4][x] 之间没有重复值。

至于如何它是这样做的：每个值都分配了一个位位置，这样 1<<ha[i][x] 将产生一个只有该位置的位设置。 x_or 将是这些值的或，而 x_add 是它们的总和。如果存在重复值，则不会对 x_or 产生影响（该位已设置），但将对 x_add 产生影响；因此，它们会有所不同。

斑马拼图 - C 中的约束满足

Zebra puzzle - Constraint Satisfaction in C

c

artificial-intelligence

constraint-satisfaction