这里已经发布了几个很棒的解决方案（全部 +1！），使用 CLP(FD) 约束。
此外，我想展示一种概念上不同的方法来解决此类放置和覆盖任务，使用 CLP( B ) 约束。
这个想法是将瓦片的每个可能放置视为网格上特定元素处的一组TRUE值，其中每个网格元素对应于矩阵的一列，并且每个可能的瓦片放置对应于一行。然后任务是选择所述矩阵的一组行，使得每个网格元素最多被覆盖一次，或者换句话说，在由所选行组成的子矩阵的每一列中最多有一个TRUE值.
在这个公式中，行的选择——以及因此瓷砖在特定位置的放置——由布尔变量表示，一个用于矩阵的每一行。
这是我想分享的代码，它可以在 SICStus Prolog 和 SWI 中工作，最多只做一些小的改动：
:- use_module(library(clpb)).
:- use_module(library(clpfd)).
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
The tiles we have available for placement.
For example, a 2x2 tile is represented in matrix form as:
[[1,1],
[1,1]]
1 indicates which grid elements are covered when placing the tile.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
tile(5*5).
tile(4*4).
tile(3*3).
tile(2*2).
tile_matrix(Rows) :-
tile(M*N),
length(Rows, M),
maplist(length_list(N), Rows),
append(Rows, Ls),
maplist(=(1), Ls).
length_list(L, Ls) :- length(Ls, L).
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Describe placement of tiles as SAT constraints.
Notice the use of Cards1 to make sure that each tile is used
exactly once. Remove or change this constraint if a shape can be
used multiple times, or can even be omitted.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
placement(M, N, Vs, *(Cs) * *(Cards1)) :-
matrix(M, N, TilesRows),
pairs_keys_values(TilesRows, Tiles, Rows),
same_length(Rows, Vs),
pairs_keys_values(TilesVs0, Tiles, Vs),
keysort(TilesVs0, TilesVs),
group_pairs_by_key(TilesVs, Groups),
pairs_values(Groups, SameTiles),
maplist(card1, SameTiles, Cards1),
Rows = [First|_],
phrase(all_cardinalities(First, Vs, Rows), Cs).
card1(Vs, card([1], Vs)).
all_cardinalities([], _, _) --> [].
all_cardinalities([_|Rest], Vs, Rows0) -->
{ maplist(list_first_rest, Rows0, Fs, Rows),
pairs_keys_values(Pairs0, Fs, Vs),
include(key_one, Pairs0, Pairs),
pairs_values(Pairs, Cs) },
[card([0,1], Cs)],
all_cardinalities(Rest, Vs, Rows).
key_one(1-_).
list_first_rest([L|Ls], L, Ls).
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
We build a matrix M_ij, where each row i describes what placing a
tile at a specific position looks like: Each cell of the grid
corresponds to a unique column of the matrix, and the matrix
entries that are 1 indicate the grid positions that are covered by
placing one of the tiles at the described position. Therefore,
placing all tiles corresponds to selecting specific rows of the
matrix such that, for the selected rows, at most one "1" occurs in
each column.
We represent each row of the matrix as Ts-Ls, where Ts is the tile
that is used in each case.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
matrix(M, N, Ms) :-
Squares #= M*N,
length(Ls, Squares),
findall(Ts-Ls, line(N, Ts, Ls), Ms).
line(N, Ts, Ls) :-
tile_matrix(Ts),
length(Ls, Max),
phrase((zeros(0,P0),tile_(Ts,N,Max,P0,P1),zeros(P1,_)), Ls).
tile_([], _, _, P, P) --> [].
tile_([T|Ts], N, Max, P0, P) -->
tile_part(T, N, P0, P1),
{ (P1 - 1) mod N >= P0 mod N,
P2 #= min(P0 + N, Max) },
zeros(P1, P2),
tile_(Ts, N, Max, P2, P).
tile_part([], _, P, P) --> [].
tile_part([L|Ls], N, P0, P) --> [L],
{ P1 #= P0 + 1 },
tile_part(Ls, N, P1, P).
zeros(P, P) --> [].
zeros(P0, P) --> [0], { P1 #= P0 + 1 }, zeros(P1, P).
以下查询说明了哪些网格元素被覆盖 ( 1)，其中每一行对应于其中一个矩形的位置：
?- M = 7, N = 9, placement(M, N, Vs, Sat), sat(Sat),
labeling(Vs), matrix(M, N, Ms), pairs_values(Ms, Rows),
pairs_keys_values(Pairs0, Vs, Rows),
include(key_one, Pairs0, Pairs1), pairs_values(Pairs1, Covers),
maplist(writeln, Covers).
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,1,1,1]
[0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
M = 7,
N = 9,
etc.
对应的解决方案：
这样的 CLP(B) 公式通常比 CLP(FD) 版本的可扩展性更小，这也是因为涉及的变量更多。但是，它也有一些优点：
一个重要的优点是它很容易推广到可以多次使用部分或全部形状的任务版本。例如，在上面的版本中，我们可以简单地更改card1/2为：
custom_cardinality(Vs, card([0,1,2,3,4,5,6,7], Vs)).
并获得一个版本，每个图块最多可以使用 7 次，甚至可以完全省略（由于包含0）。
其次，我们可以轻松地将其转换为精确覆盖问题的解决方案，这意味着每个网格元素都被其中一个形状覆盖，只需将其更改card([0,1], Cs)为card([1], Cs)in即可all_cardinalities//3。
连同其他修改，这里是一个使用四个 2x2 矩形的 4x4 网格的覆盖：
[1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0]
[0,0,1,1,0,0,1,1,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0]
[0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,1]
CLP(B) 公式的第三个优点是无需显式枚举解即可计算解的数量。例如，对于原始任务：
?- placement(7, 9, Vs, Sat), sat_count(Sat, Count).
Count = 68.
@repeat 已经对这 68 个解决方案进行了精美的说明。
为了比较，这里是每个形状可以使用 0 到 7 次的解决方案的数量：
?- placement(7, 9, Vs, Sat), time(sat_count(Sat, Count)).
% 157,970,727 inferences, 19.165 CPU in 19.571 seconds
...
Count = 17548478.
在 10x10 网格上也是如此，在大约 6 分钟内计算（约 20 亿次推理）：
?- placement(10, 10, Vs, Sat), sat_count(Sat, Count).
Count = 140547294509.
在 11x11 网格上，大约半小时计算（约 90 亿次推理）：
?- placement(11, 11, Vs, Sat), sat_count(Sat, Count).
Count = 15339263199580.
最后，也许最重要的是，这种方法适用于任何形状的瓷砖，并且不限于正方形或矩形。例如，要处理 1x1 正方形和三角形以及其垂直和水平反射，请使用以下定义tile_matrix/1：
tile_matrix([[1]]).
tile_matrix(T) :-
T0 = [[1,1,1,1],
[1,1,1,0],
[1,1,0,0],
[1,0,0,0]],
( T = T0
; maplist(reverse, T0, T)
; reverse(T0, T)
).
允许这些形状中的每一个在 9x7 板上使用 0 到 7 次，大约一分钟后，我得到了Count = 58665048314解决方案。
这是其中之一，随机挑选：
使用 CLP(B) 以使每个解决方案都具有同等可能性的方式选择解决方案也很容易，即使解决方案的数量太大而无法明确列举它们。
