Square Puzzle Problem Solution with Constraint Programming

Question

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.

In some cases, grid squares can be marked with an X, indicating that it shouldn't be filled. However, I'm not taking that in consideration, since it's not necessary for this particular input. I removed it from the post — Educorreia
"even at the corners." That's not possible, obviously. 5+3 > 5. — bobcat
@MaxB "Even at the corners" means that squares' corners must not touch, that is, between every square that must exist a gap — Educorreia

jnmonette jnmonette · Accepted Answer · 2021-01-01T20:52:35

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.

Square Puzzle Problem Solution with Constraint Programming

3 Answers