算法设计:如何用C++表示带有边界数字的二维网格?

4
我喜欢利用业余时间研究算法,以提高我的算法设计技能。我将Jane Street的月度难题作为我的“每月挑战”。我曾经开发过算法来解决他们十月的谜题,并通过手动解决了他们的11月难题。
我通过手动解决了他们11月的难题(Hooks #6),但这只是因为我不确定如何计算地解决涉及带有编号边框的网格问题(以及未来的难题)。我不确定如何为这种类型的问题打好基础。
例如,他们的许多问题都涉及到一个带有边框数字的二维网格。此外,一个经常出现的主题是,无论在网格中放置什么,都必须满足涉及从网格的不同侧面观察该数字的多个条件。例如,如果我有以下2乘2网格,其边界外有4个数字:
  _ _
5|   | 45
5|_ _| 15

Place four numbers in the grid such that, when you
 look at the grid from the left, at least one number
 in that row is the border number.

In the case of the top left of the 2 by 2 grid, 
looking at it from the left means the number 5 must be in either (0,0) or (0,1).

In addition, when looking at that row from the right, the product 
of the numbers in the row must equal the boundary number on the right.

In the case of the top right of the 2 by 2 grid, 
looking at it from the right means the number 9 must be in either (0,0)
 or (0,1), as 9 * 5 = 45.

Hence, the first row in the 2 by 2 grid can either be 5 and 9, or 9 and 5.

解决这个问题的其中一种方法是手动操作:

(0,0) = 5, (0,1) = 9, (1,0) = 5, (1,1) = 3

但是我该如何进行计算?

我该如何将这些基于网格位置的具有不同条件的问题转换为代码?

谢谢!

2个回答

0
如果你正在寻找一种用于表示一个填充网格的数据结构,我推荐使用一个包含数字左边(left)、右边(right)和数字向量(std::vector)的结构体"row"。一个网格将会是一个"row"的向量。你可以编写方法来传递函数,以检查行上的条件。
但是以一种通用的方式解决这些问题对我来说似乎很复杂。不同的规则可能意味着完全不同的解决方法。当然,如果实例总是这么小,那么可以尝试所有(合理的)可能的填充网格的方式。但是这会很快变得不可行。
如果有一些规则彼此相似,你或许可以实现一些稍微通用的算法。例如,所有数字之和为固定值的问题与所有数字的乘积为固定值的问题非常相似。
但是如果不限制可能的规则并找到其中的一些相似之处,你将不得不为每个规则编写特定的求解器代码。

0

我并不认为这些谜题是用代码来解决的。它们似乎很古怪和复杂,编写代码会耗费很多时间。

话虽如此,11月的谜题似乎对于“修复”数字放置而言选项相当有限。我会考虑使用回溯算法,保持完整的棋盘状态,并具备评估特定行或列是否违反规则以及“自由方块”规则的就绪方法。

然后尝试给出黑色指示器给出的每个可能的数字放置,按顺序排列--考虑到它们连接的正方形并不多--并在受影响的行和列上调用评估。鉴于约束条件,我认为错误的分支可能会很快终止。

在我看来,这似乎是我们能做的最好的事情,因为似乎没有明显的启发式方法表明一个分支更有可能成功。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接