Здесь уже опубликовано несколько отличных решений (+1 за всех!), Использующих ограничения CLP (FD).
Кроме того, я хотел бы показать один концептуально отличный способ решения таких задач размещения и покрытия с использованием ограничений CLP (B).
Идея состоит в том, чтобы рассматривать каждое возможное размещение плитки как набор значений ИСТИНА в определенных элементах сетки, где каждый элемент сетки соответствует одному столбцу матрицы, и каждое возможное размещение плитки соответствует одной строке. Затем задача состоит в том, чтобы выбрать набор строк указанной матрицы таким образом, чтобы каждый элемент сетки был покрыт не более одного раза, или, другими словами, в каждом столбце таблицы было не более одного значения ИСТИНА. подматрица, состоящая из выбранных строк.
В этой формулировке выбор строк и, следовательно, размещение плиток в определенных положениях указывается логическими переменными, по одной для каждой строки матрицы.
Вот код, которым я хотел бы поделиться, он работает в 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) в all_cardinalities//3.
Вместе с другой модификацией это покрытие для сетки 4х4 из четырех прямоугольников 2х2:
[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.
Эти 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.
То же самое в сетке 10х10, вычисленное примерно за 6 минут (~ 2 миллиарда выводов):
?- placement(10, 10, Vs, Sat), sat_count(Sat, Count).
Count = 140547294509.
И на сетке 11x11, рассчитанной примерно за полчаса (~ 9 миллиардов выводов):
?- 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)
).
Разрешив использовать каждую из этих форм от 0 до 7 раз на доске 9x7, я получаю через минуту или около того Count = 58665048314 решений.
Вот один из них, выбранный наугад:
Выбор решений таким образом, чтобы каждое из них было одинаково вероятным, также довольно просто с CLP (B), даже если количество решений слишком велико, чтобы перечислить их явно.
person
mat
schedule
17.05.2015
