用约束规划解决方形拼图问题

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.

为了解决这个问题，我应用了以下约束：放置的方块应该是不相交的，并且为了确保网格方块的数量是正确的，我限制了与给定相交的方块的长度总和 row/column 等于那个 row/column 数字。

然而，输出的解决方案是 [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 之前。）

您可能会体验到，此公式在减少搜索方面非常薄弱 space。改进它的一种方法（但我自己还没有尝试过）是用一些累积约束替换 lines_constraints/4。

Answer 2

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

用约束规划解决方形拼图问题

Square Puzzle Problem Solution with Constraint Programming

prolog

clpfd

sicstus-prolog