拉丁方生成器？ （类似数独的约束问题）
目的
我们正在为实验设计设计一个拉丁方（类似数独的序列），需要遵循以下约束：
- 行中的值不能重复 列
- 中的值不能重复
- 值不能重复任意两行中成对
出现 前 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 个值配对：
- 第二组值不能连续重复
- 第二组值不能在列中重复
- 与第一组数值配对时，第二组数值不能重复。
也就是说，我们需要另外六个值（同样是任意的——它们可以是“a、b、c、d、e、f”）与前六个值配对。最后一个约束意味着，如果您在任何地方使用 (2, a)，则无法再次使用它。
最后第二组约束就是问题所在。对于 nxn 网格（其中 n = 6）没有解决方案。这就是工作中的活动扳手。我们希望最大限度地减少重复次数，以形成“有点”正交的拉丁方阵对。
问题
您以前遇到过这个问题吗？ （如果有一种工具可以生成解决方案，那就太好了。）出于我们的目的，我们只需要一个这样的示例。我们已经尝试了几种不同的构建策略。
我们正在考虑为其编写一个求解器，但如果某些东西已经存在，我们希望避免这样做。
Purpose
We're designing a Latin square (sudoku-like sequence) for an experimental design that needs to follow these constraints:
- Values cannot be repeated in a row
- Values cannot be repeated in a column
- Values cannot be repeated pairwise in any two rows
Example for the first 3 constraints:
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
Here, we chose primes, but the values are arbitrary (as long as there are 6 distinct values). Notice that it's the same as sudoku in a 6 x 6 grid, with the additional constraint that there are no repeated pairs (a.k.a. bigrams) across rows. That is, 2 3 only appears on the first row, but in no others, and so on for every other pair.
- Values should be pair with another 6 values that fit these constraints:
- The 2nd-set values cannot be repeated in a row
- The 2nd-set values cannot be repeated in a column
- When paired with the 1st-set values, the 2nd-set values cannot be repeated.
That is, we need to have another six values (again, arbitrary -- they could be "a, b, c, d, e, f") that pair with the first six. The last constraint means that if you use (2, a) anywhere, you cannot use it again.
The last 2nd-set constraint is the problem. There is no solution for n x n grids where n = 6. That's the monkey wrench in the works. We want to minimize the number of repeats, to make a "sorta-kinda" orthogonal pair of Latin squares.
Question
Have you encountered this problem before? (It'd be great if there were a tool that will generate solutions.) We only need one such example for our purposes. We've tried several different construction strategies already.
We're flirting with the idea of writing a solver for it, but we'd like to avoid doing so if something already exists.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
看一下：跳舞链接
Take a look: Dancing Links
我们编写了一个求解器，可以随机排列解决方案，并在运行过夜后采用可用的最佳平衡解决方案。它可能不是最好的方法，但由于对于约束条件不存在完美的解决方案，我们认为它应该比其他找到“不太糟糕”的解决方案的方法更好。
We wrote a solver that randomly permuted solutions and took the best balanced solution available after running it overnight. It might not be the best approach, but since a perfect solution doesn't exist for the constraints, we thought it should be better than other methods of finding a "not-so-bad" solution.