Prolog 约束处理 : Packing Squares [英] Prolog Constraint Processing : Packing Squares

问题描述

我正在尝试解决 prolog 中的约束处理问题.

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

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

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 和 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)

这篇关于Prolog 约束处理 : Packing Squares的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！