Question: Fill in the grid with squares (of any size) that do not touch or overlap, even at the corners. The numbers below and at the right indicate the number of grid squares that are filled in the corresponding column / row.
To solve this problem, I applied the following constraints: the placed squares should be disjoint and to make sure the number of grid squares is correct, I constrained the sum of the length of the squares that intersect a given row/column to be equal to that row/column number.
However, the outputed solution is [1, 0, 0, 1]
([NumSquares, X, Y, SquareSize]
), a single square with length of value one in coordinates (0, 0) and it should be the one depicted in the right image (13 squares with different sizes and coordinates).
:- use_module(library(clpfd)).
:- include('utils.pl').
solve(Rows, Columns, Vars) :-
% Domain and variables definition
length(Rows, Size),
MaxNumSquares is Size * Size,
NumSquares #>= 0,
NumSquares #< MaxNumSquares,
length(StartsX, NumSquares),
length(StartsY, NumSquares),
length(SquareSizes, NumSquares),
S is Size - 1,
domain(StartsX, 0, S),
domain(StartsY, 0, S),
domain(SquareSizes, 1, Size),
construct_squares(Size, StartsX, StartsY, SquareSizes, Squares),
% Constraints
disjoint2(Squares, [margin(0, 0, 1, 1)]),
lines_constraints(0, Rows, StartsX, SquareSizes),
lines_constraints(0, Columns, StartsY, SquareSizes),
% Solution search
VarsList = [NumSquares, StartsX, StartsY, SquareSizes],
flatten(VarsList, Vars),
labeling([], Vars).
construct_squares(_, [], [], [], []).
construct_squares(Size, [StartX|T1], [StartY|T2], [SquareSize|T3], [square(StartX, SquareSize, StartY, SquareSize)|T4]) :-
StartX + SquareSize #=< Size,
StartY + SquareSize #=< Size,
construct_squares(Size, T1, T2, T3, T4).
% Rows and columns NumFilledCells cells constraints
lines_constraints(_, [], _, _).
lines_constraints(Index, [NumFilledCells|T], Starts, SquareSizes) :-
line_constraints(Index, NumFilledCells, Starts, SquareSizes),
I is Index + 1,
lines_constraints(I, T, Starts, SquareSizes).
line_constraints(Index, NumFilledCells, Starts, SquareSizes) :-
findall(
SquareSize,
(
element(N, Starts, Start),
element(N, SquareSizes, SquareSize),
intersect(Index, Start, SquareSize)
),
Lines),
sum(Lines, #=, NumFilledCells).
% Check if a square intersects a row or column
intersect(Index, Start, SquareSize) :-
Start #=< Index,
Index #=< Start + SquareSize.
The issue is in your line_constraint/4
predicate. In it, you are posting some clpfd constraints inside a findall/3
. This means that those constraints are only valid inside the findall/3
. Here is a way to rewrite your predicate that keeps the constraints posted (given that you are using SICStus, I use the do
loop style, which is just syntactic sugar around a recursive predicate):
line_constraints(Index, NumFilledCells, Starts, SquareSizes) :-
(
foreach(Start,Starts),
foreach(SquareSize,SquareSizes),
foreach(Usage,Usages),
param(Index)
do
Intersect #<=> ( Start #=< Index #/\ Index #< Start + SquareSize),
Usage #= Intersect * SquareSize
),
sum(Usages, #=, NumFilledCells).
(Note that I changed the second inequality to be a strict one: The end of the square is right before Start + SquareSize
.)
As you will probably experience, this formulation is pretty weak in terms of reducing the search space. One way to improve it (but I haven't tried it myself) would be to replace the lines_constraints/4
by some cumulative constraints.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With