问题标签 [constraint-satisfaction]

我想知道一个简单的蛮力回溯数独求解算法的 Big-O 是什么。

数独有 4 个约束：

1. 单元格 - 一个单元格最多可以包含一个数字
2. region - 区域中的数字必须完全不同
3. row - 同一行上的数字必须完全不同
4. column - 同一列上的数字必须完全不同

给定 9x9 网格：

我认为行、列和区域约束都是 O(n!) 因为 (n)(n-1)(n-2)(n-3)(n-4)(n-5)(n-6) (n-7)(n-8) 为每行、列和区域填满。

但是鉴于必须至少有 17 个给定的解决方案才能存在唯一的 9x9 数独解决方案，所以我现在不确定。排列的数量是 O(n^(n^2 - k)) 其中 k = 17 对于纯蛮力但这不包括约束满足，我确定它是指数 O(c^n) 或阶乘 O （n！）至少。

所以问题又是什么是数独的 Big-O 使用蛮力回溯和约束满足，为什么？O(log n!)?

在维基百科中它是这样写的（最小冲突算法）：

但是，这是什么意思？

例如，如果我对 N 皇后问题有以下矩阵：

这里我们有3个冲突，对吧？

如果我们将位置 1,1 的皇后移动到位置 2,3，CONFLICTS 函数的值是多少：

CONFLICTS 应该返回 2 还是应该返回 4？换句话说，我们应该只计算这个特定皇后的冲突，还是应该计算棋盘上全局的所有冲突。

维基百科也说

CONFLICTS 函数计算特定对象违反的约束的数量，假设其余分配的状态是已知的

但这感觉不对。

我正在使用 AMPL 来优化一系列值，并且我想指定一个规则，该序列不能连续包含两个以上的负值。我通过在序列为负时声明一个二进制来标记来实现这一点：

意图是对于给定的年份，如果 InventoriesDecrease 标志为零，则库存变化必须 >= 0，如果 InventoriesDecrease 标志为 1，则必须 >=（大负数）。

然后，我使用另一个约束强制执行“不超过 2 个连续否定”规则：

当我将 BigNumber 设置为 1111111 时，我得到了预期的结果——输出在库存变化中不超过两个连续的负数。（对于我正在研究的经济问题，这实际上不是一个好的解决方案，但没关系。）检查 InventoriesDecrease 的值会给我一个类似 1 1 0 1 0 1 1 ...

但是当我将 BigNumber 设置为 1111112 时，它每年都会对库存变化产生负面影响。查看 InventoriesDecrease，这些值要么是 1，要么是非常小的非整数正数，大约为 1E-5 左右。这使得库存的变化每年都是负数（因为现在的下限是 BigNumber * 1E-5 ~ 100 而不是 BigNumber * 0 = 0）。

如果我将 BigNumber 设置为 1111111 这不会发生；看起来好像然后精确地强制执行二元约束（或至少比〜 1E-5 更小的容差），因此“不超过 2 个连续否定”规则按预期工作。据推测，BigNumber 的大小会影响在 InventoriesDecrease 上设置的容差。（求解器 = Gurobi，但我在使用 CPLEX 时遇到了类似的问题。）

我希望使用一些相当大的数字，所以我想更好地了解触发这种行为的原因。我找到了http://www.ampl.com/NEW/tolerate.html但有几个“即将到来”，最后一次更新是在 1996 年，所以我没有屏住呼吸 :-)

（我也有点惊讶，十进制 1111111 是这种行为的阈值；我本来期望大约是 2 的幂！）

我想知道在序言中是否有可能让它暴力破解所有可能的计算，如下所示：

我的问题是：在学习 Prolog 时，我想制作一个 NxN 数独求解器。这个求解器会得到像这样的输入

其中一些可能是变量。求解器必须求解该数独。问题要小得多：

这应该是检查的开始，如果每一列都有不同的数字。Yfrom应该只包含给定行的firstElementsOf第一个元素。在示例中：

可悲的是，由于 append，它总是在Y列表中添加另一个空白空间。它给：

问题1：有没有办法摆脱它_1320？

问题2：这对吗？有没有办法用它来获取 Input 的第二个和第三个元素？

我正在编写一个约束满足求解器，它将读取具有多种功能的输入文件，例如

X1, X2, X3, X4, X5求解器将尝试上述函数的 100 到 100,000,000 次组合。

目前求解器：

1. 从 a 中读取函数的下一条指令Vec。
2. 模式将该指令与操作相匹配。
3. 执行指令并保存结果以供以后在函数中使用。

相反，我想对函数进行预处理并将它们转换为静态 Rust 代码。所以上面的函数会变成：

我计划有一个预处理程序：

1. 读取输入文件。
2. 自动生成一个将所有函数转换为 Rust 的模块。
3. 编辑求解器的一个模块，使其使用新生成的函数。
4. 调用编译器。
5. 运行新编译的求解器。

有一个更好的方法吗？

我可以编写一个程序来编辑自己、调用自己的编译器并安排自己在编译完成后运行，而不是编写两个程序吗？

我正在使用 Choco 来解决 CSP。一开始，我创建了一个变量数组，v如下所示：

添加几个约束后，我将搜索解决方案并找到其中的多个。但是，我只想要独特的解决方案，例如v[4]。因此，所有解决方案都应该在变量中具有不同的值v[4]。

我怎样才能做到这一点？

我有伪布尔问题，我需要用 sat4j 解决它。

有人能帮我吗？

这是我的问题：

• 我有一个名为：a,b,c,d,e,f 的变量列表

• 我有一个由以下表示的值列表：#1、#2、#3 .....

• h(a,#1) 表示将 #1 分配给 a

我有一些示例约束：

如此多的约束，例如上面的示例。最后，我想要一个将哪个值分配给哪个值的结果。

我怎样才能用 sat4J 解决它？我应该如何表示约束？

背景：我想知道是否有人成功地将自然语言转换为代表约束满足问题的知识库。我希望对一个人的陈述进行约束满足，以便在对陈述进行解决证明时查看是否存在任何不一致之处。这可以在法庭或选举辩论中使用。

因此，布置我的理想主义故事一致性算法：

如何将语句转换为可用子句？

例如：

三名嫌疑人参与抢劫，爱丽丝、鲍勃、卡尔。其中至少有一个是有罪的。

以下是条件：

如果 A 有罪，他正好有 1 个同谋。

如果 B 有罪，他正好有 2 个同谋。

谁有罪？

我怎样才能写一个Prolog脚本来解决这个guilty(X)给帮派带来的问题？