CLP(FD) 制約を使用して、ここに投稿されたいくつかの優れたソリューションが既にあります (すべて +1!)。
さらに、CLP( B ) 制約を使用して、このような配置とカバーのタスクを解決するための概念的に異なる方法を 1 つ示したいと思います。
アイデアは、タイルの各可能な配置をグリッド上の特定の要素での一連のTRUE値と見なすことです。ここで、各グリッド要素はマトリックスの 1 つの列に対応し、タイルの各可能な配置は 1 つの行に対応します。次に、各グリッド要素が最大 1 回カバーされるように、つまり、選択された行で構成されるサブマトリックスの各列に最大で 1 つのTRUE値が存在するように、マトリックスの行のセットを選択します。 .
この定式化では、行の選択、つまり特定の位置でのタイルの配置は、行列の行ごとに 1 つのブール変数によって示されます。
これが私が共有したいコードです。これは、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) を示しています。ここで、各行は長方形の 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) バージョンよりもスケーラブルではありません。これは、より多くの変数が含まれるためです。ただし、いくつかの利点もあります。
重要な利点の 1 つは、形状の一部またはすべてを複数回使用できるタスクのバージョンに容易に一般化できることです。たとえば、上記のバージョンでは、単純に次のように変更できますcard1/2。
custom_cardinality(Vs, card([0,1,2,3,4,5,6,7], Vs)).
各タイルを最大 7 回使用できるバージョンを取得し、完全に省略することもできます (が含まれているため0)。
次に、これを正確なカバーの問題の解決策に簡単に変えることができます。つまり、各グリッド要素が形状の 1 つによって覆われていることを意味します。card([0,1], Cs)card([1], Cs)all_cardinalities//3
他の変更と合わせて、4 つの 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) 式の 3 つ目の利点は、解を明示的に列挙しなくても解の数を計算できることです。たとえば、元のタスクの場合:
?- placement(7, 9, Vs, Sat), sat_count(Sat, Count).
Count = 68.
これらの 68 のソリューションは、@repeat によってすでに美しく説明されています。
比較のために、各形状を 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 のグリッドでは、約 30 分 (~ 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 回使用できるようにすると、1 分ほどでCount = 58665048314解決策が得られます。
そのうちの 1 つをランダムに選んで以下に示します。
解の数が多すぎて明示的に列挙できない場合でも、CLP(B) を使用すると、それぞれの可能性が等しくなるように解を選択することも非常に簡単です。
