编辑:这个谜题也被称为"爱因斯坦的谜语"

该谁拥有斑马(你可以试试这里的网络版)是一款经典的一套谜题的一个例子,我敢打赌,大多数人对堆栈溢出可以用纸笔解决它.但程序化解决方案会是什么样子？

基于下面列出的线索......

• 有五个房子.
• 每栋房屋都有自己独特的颜色.
• 所有房主都是不同国籍的.
• 他们都有不同的宠物.
• 他们都喝不同的饮料.
• 他们都抽不同的香烟.
• 英国人住在红房子里.
• 瑞典人有一只狗.
• 丹麦人喝茶.
• 温室位于白宫的左侧.
• 他们在温室里喝咖啡.
• 抽烟Pall Mall的男人有鸟.
• 他们在黄屋里吸烟登喜路.
• 在中间的房子里,他们喝牛奶.
• 挪威人居住在第一所房子里.
• 吸烟的男人住在房子旁边的房子里和猫咪住在一起.
• 在房子旁边的房子里,他们有一匹马,他们吸烟登喜路.
• 抽烟师傅的男人喝啤酒.
• 德国人抽烟王子.
• 挪威人住在蓝屋旁边.
• 他们在房子旁边的房子里喝水,他们吸烟混合.

谁拥有斑马？

我正在开发一个Java应用程序,它需要做一些复杂的逻辑规则推导作为其功能的一部分.我想在Prolog或其他逻辑/约束编程语言而不是Java中编写我的逻辑演绎编码,因为我相信生成的代码将更加简单和易于维护.

我在Prolog上搜索了嵌入式Java实现,并发现了它们的数量,每个都只有很少的文档.我的(适度)选择标准是:

• 应该可以嵌入Java(例如,可以与我的java包捆绑在一起,而不需要在外部程序上进行任何本机安装)
• 从Java使用的简单接口(用于启动扣减,检查结果和添加规则)
• 至少有一些关于如何使用它的例子
• 不一定必须是Prolog,但具有上述标准的其他逻辑/约束编程语言也适合我的需要.

我有什么选择,它们的优点和缺点是什么？

考虑到https://speakerdeck.com/folone/theres-a-prolog-in-your-scala,我想"滥用"Scala类型系统来查找CanBuildFrom符合给定条件的所有实例.Prolog风格,我会评估以下伪代码的行:

can_build_from(Src, int, list[int])
Src = somecollectiontype1[int]
Src = somecollectiontype2[int]
... etc

即运行时将查找Src满足该语句的所有值can_build_from(Src, int, list[int]).

现在,我知道,原始的约束/逻辑编程环境,斯卡拉隐含查询系统,并不意味着使用这种技巧,并且不能用于"重返"不止一个发现价值Src出来的箱,所以我的问题是:是否有一个"魔术",使其工作,所以无论如何我会得到所有可能的值X的CanBuildFrom[X, Int, List[Int]]？

附加示例:

trait CanFoo[T, U]

implicit val canFooIntString  = new CanFoo[Int,     String] {}
implicit val canFooDblString  = new CanFoo[Double,  String] {}
implicit val canFooBoolString = new CanFoo[Boolean, String] {}
implicit val canFooIntSym     = new CanFoo[Int,     Symbol] {}
implicit val canFooDblSym     = new CanFoo[Double,  Symbol] {}
implicit val canFooBoolSym    = …

寻找有关Constraint Programming入门的技巧,教程,书籍和其他资源.

问题陈述

我们有一个雇主想要采访N人,因此会有N个面试时段.每个人都有自由忙碌的时间表.给出一个算法,如果可能的话,将N个人调度到N个插槽中,如果不可能,则返回标志/错误/等.什么是最快的运行时复杂性？

到目前为止我的方法

天真:有N!安排N人的方法.浏览所有这些,对于每个排列,检查它是否可行.上! )

回溯:

1. 寻找任何只能有1个人的面试时间段.安排此人,将其从候选人列表中删除并删除该插槽.
2. 寻找任何只能进入1个位置的候选人.安排此人,将其从候选人列表中删除并删除该插槽.
3. 重复1和2,直到没有更多这样的组合.
4. 选择一个人,将他们随机安排到他们的一个可用插槽中.记住这个操作.
5. 重复1,2,3,直到我们有一个时间表或存在无法解决的冲突.如果我们有时间表,请将其退回.如果存在无法解决的冲突,请回溯.

这是O(n!)最糟糕的情况,我认为 - 这不是更好.

可能还有DP解决方案 - 但我还没有看到它.

其他想法

问题可以用NxN矩阵表示,其中行是"槽",列是"人",值是"1"表示空闲,"0"表示忙.然后,我们在这个矩阵中寻找一个行列交换的Identity Matrix.步骤1和2正在寻找只有一个"1"的行或列.(如果矩阵的秩是= N,那意味着有一个解决方案.但相反的情况并不成立)另一种看待它的方法是将矩阵视为未加权的有向图边缘矩阵.然后,每个节点代表1个候选和1个时隙.然后我们寻找一组边,以便图中的每个节点都有一个输出边和一个输入边.或者,对于2x节点,它将是一个二分图.

矩阵示例:

1 1 1 1
0 1 1 0
1 0 0 1
1 0 0 1

背景和问题描述:

我有一些代码可以解决图形着色问题(广泛定义为将"颜色"分配给无向图的问题,确保没有两个由边连接的顶点具有相同的颜色).我正在尝试使用约束传播来实现解决方案,以提高标准递归回溯算法的效率,但遇到以下错误:

  File "C:\Users\danisg\Desktop\coloring\Solver.py", 
  line 99, in solve
  for color in self.domains[var]:
  RuntimeError: Set changed size during iteration

在这里,对于每个顶点,我set为该特定顶点保留一些可能的特定值:

  self.domains = { var: set(self.colors) for var in self.vars }

在我进行赋值后,我将此约束传播到相邻域,以限制搜索空间:

  for key in node.neighbors:          # list of keys corresponding to adjacent vertices
      if color in self.domains[key]:  # remove now to prune possible choices
          self.domains[key].remove(color)

这不是抛出实际错误的地方(在我的代码中,我指出了try-except块中问题的位置),但可能是问题的根源.

我的问题:

我是否有正确的想法,如果不是正确的实施？更重要的是,我该如何解决这个问题？另外,是否有必要保留一个单独的domains字典？或者我们可以domain在图中创建每个节点的属性吗？

我的代码:

这solve是调用此代码的函数:

def solve(self):

    uncolored = [var for var in self.vars if self.map[var].color …

我是 SAT 求解器的新手，需要一些有关以下问题的指导。

考虑到：

? 我在 4*4 网格中选择了 14 个相邻的单元格

? 我有 5 个多联骨牌（A、B、C、D、E），大小分别为 4、2、5、2 和 1

? 这些多联骨是自由的，即它们的形状不是固定的，可以形成不同的图案。

如何使用 SAT 求解器计算所选区域（灰色单元格）内这 5 个自由多联骨牌的所有可能组合？

借用@spinkus 有见地的答案和 OR-tools 文档，我可以制作以下示例代码（在 Jupyter Notebook 中运行）：

from ortools.sat.python import cp_model

import numpy as np
import more_itertools as mit
import matplotlib.pyplot as plt
%matplotlib inline


W, H = 4, 4 #Dimensions of grid
sizes = (4, 2, 5, 2, 1) #Size of each polyomino
labels = np.arange(len(sizes))  #Label of each …

由于Erlang基于Prolog,这是否意味着Erlang是一种约束逻辑语言？
Erlang是否有Prolog的构建块:事实,规则和查询

一个奇怪的问题是:
我在学校解决竞争问题,他们允许我们使用电脑.由于我是竞赛中唯一知道如何编码的人,我使用C和Pascal程序来更快地解决问题.我已经完成了伪代码到代码练习,算法,Collat​​z猜想验证等.
现在,昨天我正在接受下一次挑战训练(4月18日),我看到了一场关于Young tableaux的练习.它的措辞是这样的(我将尽力从意大利语翻译):
"Ferrers图表是N个盒子的配置,分布在一个或多个水平行中,左对齐并配置为每行包含相等或更低的数量这些配置也可以用方框的编号列表来描述,如下图所示:
ferrers diagram http://olimpiadiproblemsolving.it/immagini_test/mate/finale_2011_m_07a_400.jpg
一个年轻的画面是一个Ferrers N个框的图表填充了从1到N的整数.示例:
young tableaux http://olimpiadiproblemsolving.it/immagini_test/mate/finale_2011_s_03b_400.jpg
如果框中的数字被排序,以便它们按行和逐列递增,表格是"标准"(例如:第一,第三和第五画面).在标准表格中,第一行的第一个框始终包含1.N始终位于图表的其中一行的最左侧框中.


问题

考虑一个[6,3,2,1,1,1] Ferrers图:
1)如果第一行的第6个框中固定了6,第一列的最后一个框中固定了11,那么有多少种方法可以您是否以标准方式完成图表？

2)如果在第1行的第6个框中固定了7,在第1列的最后一个框中固定了11,那么您可以用多少种方式以标准方式完成图表？

3)如果在第1行的第6个框中固定了8,在第1列的最后一个框中固定了11,那么您可以用多少种方式以标准方式完成图表？"

我试图编写解决方案用矩阵填充这些数字并用"-1"作为"行尾字符",但我卡住了.我怎么能编码"以各种可能的方式填写它以使画面成为标准？".

我已经开始学习Constraint编程了,我觉得它适用于Haskell(我喜欢使用Haskell).

Haskell有任何成熟的约束框架吗？