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

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 theright indicate the number of grid squares that are filled in thecorresponding column / row.

为了解决这个问题，我应用了以下约束:放置的正方形应该是不相交的，为了确保网格正方形的数量是正确的，我将与给定行/列相交的正方形的长度总和限制为等于该行/列号。
但是，输出的解决方案是 [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

问题出在您的 line_constraint/4谓词。在其中，您在 findall/3 中发布了一些 clpfd 约束。 .这意味着这些约束仅在 findall/3 内有效。 .这是一种重写谓词的方法，以保持约束张贴(假设您使用的是 SICStus，我使用 do 循环样式，这只是递归谓词周围的语法糖):

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

(请注意，我将第二个不等式更改为严格的不等式:正方形的结尾正好在 Start + SquareSize 之前。)
您可能会体验到，这个公式在减少搜索空间方面非常薄弱。改进它的一种方法(但我自己没有尝试过)是替换 lines_constraints/4受一些累积约束。