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.

Orcinol

Answer 1

Since the problem was in the number of squares, I fixed them to be the highest possible (total number of cells divided by four, since they must be disjoint), but allowed its width/height to be equal to zero, effectively not existing and then allowing for the number of squares to be bounded between zero and the maximum number of squares.

Orcinol

Answer 2

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.

Anoxia

I've replaced the line_constraints predicate, but the program runs on an endless loop. Did I do anything wrong? I've tried to run it with the following input [2,2,2,2,3,2,2,5,3,4] (Rows) and [4,5,4,4,0,0,0,4,3,3](Columns), which corresponds to the puzzle image I've submitted – Orcinol

I tried with both [1,0,1],[1,0,1] and [2,2,0],[2,2,0] and it gives the correct answer(s). As I said, with larger input, it gets very inefficient... – Anoxia

Looks like adding symmetry breaking constraints does allow one to solve the larger input. Add this somewhere in your solve/3 predicate (after declaring the variables and before labeling): (foreach(X,StartsX), foreach(Y,StartsY), foreach([X,Y],StartsXY) do true),lex_chain(StartsXY), – Anoxia

Yes, but it seems that I have to explicitily specify the number of squares – Orcinol

Weird, I don't have the same issue. I added the extra lines right after the three domain/3 calls. At that point in the code, the number of squares is already fixed anyway (by the length(StartsX, NumSquares) call). – Anoxia

I had to add a NumSquares #= 13 statement, otherwise it wouldn't work – Orcinol