带约束规划的方形拼图问题解决方案

Question

问题：用不接触或重叠的正方形（任何大小）填充网格，即使在角落处也不例外。下面和右侧的数字表示填充在相应列/行中的网格方块数。

为了解决这个问题，我应用了以下约束：放置的正方形应该是不相交的，为了确保网格正方形的数量是正确的，我将与给定行/列相交的正方形的长度总和限制为等于该行/列号。

但是，输出的解决方案是 [1, 0, 0, 1] ([NumSquares, X, Y, SquareSize]，一个在坐标 (0, 0) 中长度为 1 的正方形，它应该是右图（13 个不同大小和坐标的方块）。

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

Answer 1

由于问题在于方块的数量，我将它们固定为尽可能高的数量（单元格总数除以四，因为它们必须是不相交的），但允许其宽度/高度等于零，实际上不存在并且然后允许方格数限制在零和最大方格数之间。