前序约束处理：包装正方形 [英] Prolog Constraint Processing : Packing Squares

问题描述

我试图在prolog中解决约束处理问题。

I'm trying to solve a constraint processing problem in prolog.

我需要在10x10的网格中打包5x5,4x4,3x3和2x2的4个正方形。
它们不能重叠。

I need to pack 4 squares of 5x5,4x4,3x3 and 2x2 in a grid of 10x10. They may not overlap.

我的变量如下所示：

Name: SqX(i), i=1..10, domain: 1..10

其中X是5,4,3或2.索引i表示行，网格中的列。

Where X is either 5,4,3 or 2. The index i represents the row, the domain the column in the grid.

我的第一个约束尝试定义正方形的宽度和高度。我如此规定：

My first constraints try to define the width and height of the squares. I formulate it as such:

Constraint: SqX(i) > SqX(j)-X /\ i>j-X, range: i>0 /\ j>0

因此，可能的点被限制在彼此的X行和列之内。
Prolog然而，停止这些约束并给出以下结果：

So that the possible points are constrained to be within X rows and columns from each other. Prolog however, stops on these constraints and gives the following result:

Adding constraint "(Sq5_I > Sq5_J-5) /\ (I>J-5)" for values:
        I=1, J=1, 
        I=1, J=2, 
        I=1, J=3, 
        I=1, J=4, 
        I=1, J=5, 
        I=1, J=6, 
=======================[ End Solutions ]=======================

所以它停在那里，甚至不检查其他方格。我的约束很可能太紧，但我不明白为什么或如何。任何建议？

So it stops there, not even checking the other squares. My constraints are most likely too tight, but I can't see why or how. Any suggestions?

推荐答案

对于每个方块，定义 X c $ c> Y 表示左上角的变量。
这些变量将有域 1..10-L ，其中 L 是方形的长度。如果您将域设置为 1..10 ，则正方形可能会部分位于10x10矩形之外。

For each square, define X and Y variables that denote the upper left corner. These variable will have domains 1..10-L, where L is the length of the square. If you set the domain to 1..10, the squares may be placed partly outside your 10x10 rectangle.

然后你可以为每对矩形（X，Y）和（X1，Y1）如果它们在x轴上重叠，则它们不必在y轴上重叠，反之亦然：

Then you can post constraints for each pair of rectangles (X,Y) and (X1,Y1) that state that if they overlap on the x axis, they must not overlap on the y axis, and vice versa:

(((X  #=< X1) and (X+L   #> X1)) => ((Y+L #=< Y1) or (Y1+L1 #=< Y))),
(((X1 #=< X)  and (X1+L1 #> X))  => ((Y+L #=< Y1) or (Y1+L1 #=< Y))),
(((Y  #=< Y1) and (Y+L   #> Y1)) => ((X+L #=< X1) or (X1+L1 #=< X))),
(((Y1 #=< Y)  and (Y1+L1 #> Y))  => ((X+L #=< X1) or (X1+L1 #=< X)))

（您的特定约束语法可能不同）

(your particular constraint syntax may vary)

这篇关于前序约束处理：包装正方形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！