c# - 努力制作算法来为益智游戏生成棋盘

Question

我想制作一款数字益智游戏。为了这个问题，假设棋盘是由 4 x 4 正方形组成的网格。 (在实际的益智游戏中，这个数字会是1..15)

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

有效:

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

我似乎无法想出一个算法来持续生成有效的、随机的 n x n 板。

我正在用 C# 编写。

Answer 1

首先阅读我关于图形着色算法的系列文章:

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

看起来这与您的问题无关，但当您完成后，您会发现它与您的问题息息相关。

---

好的，既然你已经读过，你知道你可以使用图形着色算法来描述一个类似数独的谜题，然后解决这个谜题的特定实例。但很明显，您可以使用相同的算法生成谜题。

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

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

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

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