Блог

Вопрос: Заполните сетку квадратами (любого размера), которые не соприкасаются и не перекрываются даже по углам. Цифры внизу и справа указывают количество квадратов сетки, заполненных в соответствующем столбце / строке.

Чтобы решить эту проблему, я применил следующие ограничения: размещенные квадраты должны быть непересекающимися, и чтобы убедиться, что количество квадратов сетки правильное, я ограничил сумму длин квадратов, пересекающих данную строку / столбец, равной этому номеру строки / столбца.

Однако выводимым решением является [1, 0, 0, 1] ( [NumSquares, X, Y, SquareSize] ), один квадрат с длиной значения один в координатах (0, 0), и он должен быть тем, который изображен на правом изображении (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.
 

Проблема в вашем line_constraint/4 предикате. В нем вы размещаете некоторые ограничения clpfd внутри a findall/3 . Это означает, что эти ограничения действительны только внутри 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 на некоторые кумулятивные ограничения.

Поскольку проблема заключалась в количестве квадратов, я установил их максимально возможными (общее количество ячеек, разделенных на четыре, поскольку они должны быть непересекающимися), но допустил, чтобы его ширина / высота были равны нулю, фактически не существовали, а затем допускали ограничение количества квадратовмежду нулем и максимальным количеством квадратов.