3

"Squares"

Input:

Board size m × n (m, n ∈ {1,...,32}), list of triples (i, j, k), where i ∈ {1,...,m}, j ∈ {1,...,n}, k ∈ {0,...,(n-2)·(m-2)}) describing fields with numbers.

Output:

List of triples (i, j, d) showing solved riddle. Triple (i, j, d) describes square with opposite vertices at coordinates (i, j) and (i+d, j+d).

Example:

Input:

7. 7. [(3,3,0), (3,5,0), (4,4,1), (5,1,0), (6,6,3)].

Output:

[(1,1,2), (1,5,2), (2,2,4), (5,1,2), (4,4,3)]

Image:

Example

Explanation:

I have to find placement for x squares(x = fields with numbers). On the circuit of the each square, exactly at one of his corners should be only one digit equal to amount of digits inside the square. Sides of squares can't cover each other, same as corners. Square lines are "filling fields" so (0,0,1) square fills 4 fields and have 0 fields inside.

I need a little help coding solution to this riddle in Prolog. Could someone direct me in the right direction? What predicates, rules I should use.

4

1 回答 1

1

由于 Naimads 的生命值得拯救（！），这里有一些更具指导性的帮助。

程序员倾向于以自底向上（从“较低”级别的功能开始，构建完整的应用程序）或自顶向下（从提供输入/输出的高级“外壳”功能开始，但将解决方案处理存根以供以后细化）。

无论哪种方式，我都可以推荐一种受到 Ruby 编程社区支持的 Prolog 编程方法： 测试驱动开发。

让我们挑选几个功能要求，一个高一个低，并讨论一下这种理念如何提供帮助。

Prolog 中的高级谓词是一个接受所有输入和输出参数并在语义上定义问题的谓词。请注意，我们可以写下这样的谓词，而无需关心解决方案过程将如何实现：

/* squaresRiddle/4 takes inputs of Height and Width of a "board" with
   a list of (nonnegative) integers located at cells of the board, and
   produces a corresponding list of squares having one corner at each
   of those locations "boxing in" exactly the specified counts of them
   in their interiors.  No edges can overlap nor corners coincide.  */
squaresRiddle(Height,Width,BoxedCountList, OutputSquaresList).

到目前为止，我们刚刚提出了这个问题。注释给出了有用的进展（在高层次上清楚地定义了输入和输出），此时的代码只保证传递任何参数的“成功”。所以这个代码的“测试”：

?= squaresRiddle(7,7,ListIn,ListOut).

除了自由变量，不会产生任何东西。

接下来让我们考虑一下应该如何表示输入列表和输出列表。在问题中，建议使用整数的三元组作为这些列表的条目。我建议改用命名函子，因为这些输入三元组的语义（给出带有计数的单元格的 x,y 坐标）与输出三元组的语义（给出左上角的 x,y 坐标）略有不同和正方形的“范围”（高度和宽度））。特别注意，输出方块可以由与相应输入项中的角不同的角来描述，尽管输入项中的角需要是输出方块的四个角之一。

BoxedCountList = [box(3,3,0),box(3,5,0),box(4,4,1),box(5,1,0),box(6,6,3)]因此，如果这些构造通过简单的仿函数名称来区分，例如vs. ，它往往会使代码更具可读性OutputSquaresList = [sqr(1,1,2), sqr(1,5,2), sqr(2,2,4), sqr(5,1,2), sqr(4,4,3)]。

让我们稍微思考一下解决方案的搜索将如何进行。输出项与输入项是一一对应的，因此列表最终将具有相等的长度。然而，选择第 k 个输出项不仅取决于第 k 个输入项，还取决于所有输入项（因为我们计算了输出方格内部有多少）和前面的输出项（因为我们不允许满足和重叠的边缘）。

有几种方法可以管理符合此要求的决策流程，而选择一种方法并使其发挥作用似乎是本练习的关键。如果您熟悉差异列表或累加器，那么您就可以先行一步。

现在让我们切换到讨论一些较低级别的功能。给定一个输入box，可能有许多sqr与之对应的输出。给定输出的正“范围”，X,Y输入的坐标可以与输出正方形的四个角中的任何一个相交。虽然需要更多检查来验证解决方案，但这方面似乎是开始测试的好地方：

/* check that coordinates X,Y are indeed a corner of candidate square */
hasCorner(sqr(SX,SY,Extent),X,Y) :-
    (SX is X ; SX is X + Extent),
    (SY is Y ; SY is Y + Extent).

我们将如何利用这个测试？好吧，我们可以生成所有可能的正方形（可能将我们限制在适合我们“板”的高度和宽度的那些），然后检查是否有任何需要的角。这可能是相当低效的。更好的方法（就效率而言）将使用角来生成可能的正方形（通过从角延伸到Extent四个方向中的任何一个），这取决于电路板尺寸的参数。这种“优化”的实现留给读者作为练习。

于 2013-04-26T00:16:04.383 回答