Search code examples
prologclpfdsicstus-prolog

Square Puzzle Problem Solution with Constraint Programming

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.

Unsolved Solved

Solution

  • 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.