努力制定算法来生成益智游戏的棋盘

Question

我想做一个数字益智游戏。为了解决这个问题，我们假设棋盘是一个由 4 x 4 方格组成的网格。 （在实际的益智游戏中，这个数字将为 1..15）

一个数字只能在每列和每行中出现一次，有点像数独，但没有“方块”。

有效：

[1, 2, 3, 4
2, 3, 4, 1
3, 4, 1, 2
4, 1, 2, 3]

我似乎无法想出一种能够持续生成有效的随机 nxn 板的算法。

我用 C# 写这个。

Answer 1

首先阅读我的图形着色算法系列：

http://blogs。 msdn.com/b/ericlippert/archive/tags/graph+colouring/

这看起来与您的问题无关，但当您完成时，您会发现它与你的问题有一切关系。

---

好的，现在您已经阅读了本文，您知道可以使用图形着色算法来描述类似数独的谜题，然后解决该谜题的特定实例。但显然您可以使用相同的算法来生成谜题。

首先定义完全连接的图形区域。

然后修改算法，使其尝试找到两个解决方案。

现在创建一个空白图表并将其中一个区域随机设置为随机颜色。尝试解决该图。有两种解决方案吗？然后添加另一种随机颜色。再试一次。难道就没有解决办法吗？然后后退一步并添加不同的随机颜色。

继续这样做——添加随机颜色，当你没有解决方案时回溯，直到你得到一个有唯一解决方案的谜题。你就完成了；你有一个随机拼图生成器。

Answer 2

看来您可以使用这个有效的示例作为算法的输入，该算法随机交换两行随机次数，然后随机交换两个随机列随机次数。

Answer 3

您不需要尝试太多的组合。您始终可以重新排列有效的棋盘，使顶行为 1,2,3,4（通过重新映射符号），左列为 1,2,3,4（通过重新排列第 2 行到第 4 行）。每行上只有剩余 3 个符号的 6 种排列，因此您可以循环这些符号以找出 216 个可能的棋盘中哪些是有效的。您也可以存储有效的。

然后随机选择一个有效的棋盘，随机重新排列行，并随机重新分配符号。

Answer 4

我不会说 C#，但下面的算法应该很容易翻译。

将由数字 1..N 组成的集合与每一行和每一列相关联：

for i = 1 to N
  row_set[i] = column_set[i] = Set(1 .. N)

然后单次遍历矩阵，从该行和该列有效的集合元素中随机为每个位置选择一个条目。删除从相应的行和列集中选择的数字。

for r = 1 to N
  for c = 1 to N
    k = RandomChoice( Intersection( column_set[c], row_set[r] ))
    puzzle_board[r, c] = k
    column_set[c] = column_set[c] - k
    row_set[r] = row_set[r] - k
  next c
next r

Answer 5

看起来您想生成均匀分布的拉丁方。

这个 pdf 描述了 Jacobson 和 Matthews 的方法（已在其他地方发布） ，可以在这里找到其参考：http://designtheory.org/library/encyc/ latinsq/z/）

或者您可以预先生成“很多”它们（在发货之前:-)），将其存储在文件中并随机选择一个。

希望有帮助。

Answer 6

我能想到的最简单的方法是创建一个部分游戏并解决它。如果它无法解决，或者如果它是错误的，请再做一个。 ;-)

Answer 7

没有方块的数独听起来有点像数独。 :)

http://www.codeproject.com/KB/game/sudoku.aspx

他们在那里使用了板生成器代码的解释。

Answer 8

查看 http://www.chiark.greenend.org.uk/~sgtatham/ puzzles/ - 他有几个谜题恰好具有此约束（以及其他）。

Answer 9

进一步的解决方案是这样的。假设您有多种解决方案。对于它们中的每一个，您都可以通过简单地排列标识符 (1..15) 来生成新的解决方案。这些新的解决方案在逻辑上当然是相同的，但对于玩家来说它们会显得不同。

可以通过将初始解决方案中的每个标识符视为数组的索引，然后对该数组进行混洗来完成排列。

Answer 10

使用您的第一个有效示例：

1 2 3 4 
2 3 4 1
3 4 1 2
4 1 2 3

然后，随机创建 {1, 2, 3, 4} 的 2 个排列。

使用第一个来排列行，然后使用第二个来排列列。

您可以在 Knuth 的 计算机编程艺术 中找到多种创建排列的方法(TAOCP)，第 4 卷分册 2，生成所有元组和排列 (2005)，v+128 页。 ISBN 0-201-85393-0。

如果您在图书馆中找不到副本，可以在他的网站上找到预印本（讨论排列的部分）：fasc2b.ps.gz

---

编辑 - 更正

上述解决方案与 500-内部服务器错误的解决方案类似。但我认为两者都无法找到所有有效的安排。

例如，他们会发现：

1 3 2 4 
3 1 4 2
2 4 1 3
4 2 3 1

但不是这个：

1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

还需要一个步骤：重新排列行和列（使用 my 或 500 的方式）后，再创建一个排列（我们称之为 s3）并用它来排列数组中的所有数字。

s3 = randomPermutation(1 ... n)
for i=1 to n
  for j=1 to n
    array[i,j] = s3( array[i,j] )