算法设计：用 C++ 表示具有边界数字的 2D 网格的最佳方法？
Algorithm Design: Best Way to Represent a 2D Grid, with Boundary Digits, in C++?
我喜欢在业余时间研究算法，以提高我的算法设计技能。我 'monthly challenge' 解决 Jane Street 每月的难题。我以前开发过 algorithms to solve their October 拼图，并手工解决了他们的 11 月拼图。
我手动解决了他们的 November 谜题（Hooks #6），但这只是因为我不确定如何解决涉及网格 的问题（以及未来的谜题）编号边界，计算。我不确定我将如何为这类问题奠定基础。
例如，他们的许多问题都涉及二维网格，网格的边界上有数字。此外，一个反复出现的主题是网格中的任何内容都必须满足多个条件，这些条件涉及从网格的不同侧面查看该数字。例如，如果我有以下 2 x 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
但是我该如何进行计算呢？
我怎样才能将这些基于网格位置 "looks" 的不同条件的类似网格的问题转化为代码？
谢谢！
如果您正在寻找一种数据结构来表示一个填充的网格，我会推荐一个 struct row 包含数字 left 和 right 以及一个 std::vector 的数字.网格将是 rows 的矢量。您可以编写允许您将检查行条件的函数传递给它的方法。
但以通用方式解决这些问题对我来说似乎很复杂。不同的规则可能意味着非常不同的解决方法。当然，如果实例总是这么小，那么可以尝试所有（合理的）可能的网格填充。但这很快就会变得不可行。
如果存在彼此相似的规则，您也许可以实现一些通用算法。例如，一行中所有数字的总和的固定值与产品的固定值非常相似。
但是如果不限制可能的规则并在其中找到一些相似之处，您将不得不为每个规则编写特定的求解器代码。
我不相信这些谜题是要通过代码来解决的。它们看起来非常特殊和复杂，以至于对它们进行编码非常耗时。
也就是说，特别是 11 月的拼图似乎在 "fixing" 数字放置方面的选择相当有限。我会考虑一个回溯算法，它保持完整的棋盘状态，并有现成的方法来评估特定的行或列是否没有违反规则，以及 "free square" 规则。
然后尝试按顺序排列黑色指示器给出的数字的每个可能位置——没有那么多，考虑到它们连接正方形——并对受影响的行和列调用评估。鉴于限制，我认为错误的分支可能会很快终止。
在我看来，这或多或少是我们能做的最好的事情，因为似乎没有明确的启发式方法表明分支更有可能成功。
我喜欢在业余时间研究算法，以提高我的算法设计技能。我 'monthly challenge' 解决 Jane Street 每月的难题。我以前开发过 algorithms to solve their October 拼图，并手工解决了他们的 11 月拼图。
我手动解决了他们的 November 谜题（Hooks #6），但这只是因为我不确定如何解决涉及网格 的问题（以及未来的谜题）编号边界，计算。我不确定我将如何为这类问题奠定基础。
例如，他们的许多问题都涉及二维网格，网格的边界上有数字。此外，一个反复出现的主题是网格中的任何内容都必须满足多个条件，这些条件涉及从网格的不同侧面查看该数字。例如，如果我有以下 2 x 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
但是我该如何进行计算呢？
我怎样才能将这些基于网格位置 "looks" 的不同条件的类似网格的问题转化为代码？
谢谢！
如果您正在寻找一种数据结构来表示一个填充的网格，我会推荐一个 struct row 包含数字 left 和 right 以及一个 std::vector 的数字.网格将是 rows 的矢量。您可以编写允许您将检查行条件的函数传递给它的方法。
但以通用方式解决这些问题对我来说似乎很复杂。不同的规则可能意味着非常不同的解决方法。当然，如果实例总是这么小，那么可以尝试所有（合理的）可能的网格填充。但这很快就会变得不可行。
如果存在彼此相似的规则，您也许可以实现一些通用算法。例如，一行中所有数字的总和的固定值与产品的固定值非常相似。
但是如果不限制可能的规则并在其中找到一些相似之处，您将不得不为每个规则编写特定的求解器代码。
我不相信这些谜题是要通过代码来解决的。它们看起来非常特殊和复杂，以至于对它们进行编码非常耗时。
也就是说，特别是 11 月的拼图似乎在 "fixing" 数字放置方面的选择相当有限。我会考虑一个回溯算法，它保持完整的棋盘状态，并有现成的方法来评估特定的行或列是否没有违反规则，以及 "free square" 规则。
然后尝试按顺序排列黑色指示器给出的数字的每个可能位置——没有那么多，考虑到它们连接正方形——并对受影响的行和列调用评估。鉴于限制，我认为错误的分支可能会很快终止。
在我看来，这或多或少是我们能做的最好的事情，因为似乎没有明确的启发式方法表明分支更有可能成功。