0

目的

我们正在为需要遵循以下约束的实验设计设计一个拉丁方格（类似数独的序列）：

  • 值不能连续重复
  • 值不能在列中重复
  • 任何两行中的值不能成对重复

前 3 个约束的示例：

2     3    5    7    11   13
7     2    11   3    13   5
11    5    2    13   7    3
3     7    13   2    5    11
5     13   3    11   2    7
13    11   7    5    3    2

在这里，我们选择了素数，但值是任意的（只要有 6 个不同的值）。请注意，它与 6 x 6 网格中的数独相同，但额外的约束是行间没有重复的对（又名二元组）。也就是说，2 3只出现在第一行，而没有出现在其他行中，以此类推。

  • 值应与符合这些约束的另外 6 个值配对：
    • 第二组值不能连续重复
    • 第二组值不能在列中重复
    • 与第 1 组数值配对时，第 2 组数值不能重复。

也就是说，我们需要另外六个与前六个配对的值（同样是任意的——它们可以是“a、b、c、d、e、f”）。最后一个约束意味着如果你在任何地方2使用 ( , a) ，你就不能再次使用它。

最后的第二组约束是问题所在。对于 n = 6 的 nxn 网格没有解决方案。这就是工作中的活动扳手。我们希望尽量减少重复次数，以制作一对“有点像”的正交拉丁方格。

问题

你以前遇到过这个问题吗？（如果有一种工具可以生成解决方案，那就太好了。）我们只需要一个这样的例子就可以了。我们已经尝试了几种不同的构建策略。

我们正在考虑为其编写求解器的想法，但如果某些东西已经存在，我们希望避免这样做。

4

2 回答 2

2

看一看：舞蹈链接

在计算机科学中，Dancing Links，也称为 DLX，是 Donald Knuth 提出的有效实现算法 X 的技术。算法 X 是一种递归、非确定性、深度优先的回溯算法，可以找到精确覆盖问题的所有解决方案。一些更为人所知的精确覆盖问题包括平铺、N 皇后问题和数独。

于 2009-11-18T17:06:24.893 回答
0

我们编写了一个求解器，它随机排列解决方案，并在运行一夜后获得最佳平衡解决方案。这可能不是最好的方法，但由于不存在约束的完美解决方案，我们认为它应该比其他找到“不太糟糕”解决方案的方法更好。

于 2010-02-16T14:18:11.327 回答