carcassone in prolog

% task definition: generate a complete rectangular map using all 84 carcassone tiles where all borders are pastures :- use_module(library(clpfd)). % a tile has 4 sides, where: % * 0 is a town % * 1 is a road % * 2 is a pasture % * 3 is a river % A tile sides order is [Top, Right, Bottom, Left] tile(0 , [0 , 1 , 2 , 1]). tile(1 , [1 , 1 , 1 , 1]). tile(2 , [0 , 1 , 2 , 1]). tile(3 , [2 , 0 , 2 , 2]). tile(4 , [1 , 0 , 0 , 0]). tile(5 , [2 , 2 , 2 , 0]). tile(6 , [2 , 0 , 0 , 0]). tile(7 , [0 , 0 , 0 , 0]). tile(8 , [2 , 0 , 2 , 0]). tile(9 , [0 , 0 , 1 , 1]). tile(10 , [0 , 1 , 1 , 0]). tile(11 , [2 , 1 , 2 , 1]). tile(12 , [1 , 1 , 1 , 0]). tile(13 , [1 , 1 , 0 , 2]). tile(14 , [2 , 1 , 2 , 1]). tile(15 , [0 , 2 , 0 , 2]). tile(16 , [2 , 0 , 2 , 2]). tile(17 , [0 , 2 , 0 , 0]). tile(18 , [0 , 2 , 1 , 1]). tile(19 , [2 , 0 , 0 , 2]). tile(20 , [0 , 1 , 1 , 0]). tile(21 , [1 , 2 , 1 , 2]). tile(22 , [0 , 1 , 1 , 2]). tile(23 , [1 , 0 , 1 , 1]). tile(24 , [1 , 2 , 2 , 1]). tile(25 , [1 , 1 , 2 , 2]). tile(26 , [1 , 2 , 2 , 1]). tile(27 , [0 , 2 , 0 , 2]). tile(28 , [2 , 0 , 2 , 2]). tile(29 , [2 , 0 , 0 , 0]). tile(30 , [0 , 1 , 1 , 2]). tile(31 , [0 , 0 , 2 , 2]). tile(32 , [0 , 1 , 1 , 0]). tile(33 , [1 , 2 , 1 , 2]). tile(34 , [2 , 2 , 2 , 2]). tile(35 , [1 , 2 , 1 , 2]). tile(36 , [1 , 1 , 1 , 2]). tile(37 , [2 , 1 , 0 , 1]). tile(38 , [1 , 2 , 1 , 1]). tile(39 , [1 , 2 , 2 , 2]). tile(40 , [0 , 0 , 2 , 2]). tile(41 , [1 , 0 , 0 , 0]). tile(42 , [2 , 2 , 0 , 0]). tile(43 , [2 , 2 , 2 , 2]). tile(44 , [0 , 2 , 0 , 2]). tile(45 , [0 , 2 , 0 , 2]). tile(46 , [2 , 0 , 2 , 2]). tile(47 , [0 , 2 , 0 , 0]). tile(48 , [0 , 2 , 1 , 1]). tile(49 , [2 , 0 , 0 , 2]). tile(50 , [0 , 1 , 1 , 0]). tile(51 , [1 , 2 , 1 , 2]). tile(52 , [0 , 1 , 1 , 2]). tile(53 , [1 , 0 , 1 , 1]). tile(54 , [1 , 2 , 2 , 1]). tile(55 , [1 , 1 , 2 , 2]). tile(56 , [1 , 2 , 2 , 1]). tile(57 , [2 , 2 , 1 , 1]). tile(58 , [2 , 1 , 1 , 2]). tile(59 , [2 , 2 , 1 , 1]). tile(60 , [1 , 2 , 1 , 2]). tile(61 , [2 , 2 , 2 , 2]). tile(62 , [1 , 2 , 1 , 2]). tile(63 , [1 , 1 , 1 , 2]). tile(64 , [2 , 1 , 0 , 1]). tile(65 , [1 , 2 , 1 , 1]). tile(66 , [1 , 2 , 2 , 2]). tile(67 , [0 , 0 , 2 , 2]). tile(68 , [1 , 0 , 0 , 0]). tile(69 , [2 , 2 , 0 , 0]). tile(70 , [2 , 2 , 2 , 2]). tile(71 , [0 , 2 , 0 , 2]). tile(72 , [0 , 3 , 3 , 0]). tile(73 , [2 , 2 , 3 , 3]). tile(74 , [1 , 1 , 3 , 2]). tile(75 , [3 , 1 , 3 , 2]). tile(76 , [3 , 1 , 3 , 1]). tile(77 , [3 , 0 , 3 , 1]). tile(78 , [3 , 2 , 3 , 2]). tile(79 , [3 , 2 , 2 , 2]). tile(80 , [3 , 0 , 3 , 0]). tile(81 , [3 , 3 , 1 , 1]). tile(82 , [3 , 2 , 3 , 2]). tile(83 , [3 , 2 , 2 , 3]). sides(AllSides) :- findall(Sides, tile(_, Sides), AllSides). % compute a rotation independent id of a tile sides side_id(S, [C1, C2, C3, C4]) :- S = [S1, S2, S3, S4], C1 #= S1 + S2 * 4 + S3 * 16 + S4 * 64, C2 #= S2 + S3 * 4 + S4 * 16 + S1 * 64, C3 #= S3 + S4 * 4 + S1 * 16 + S2 * 64, C4 #= S4 + S1 * 4 + S2 * 16 + S3 * 64. cell(Sides) :- length(Sides, 4), Sides ins 0..3. top([Top, _Right, _Bottom, _Left], Top). right([_Top, Right, _Bottom, _Left], Right). bottom([_Top, _Right, Bottom, _Left], Bottom). left([_Top, _Right, _Bottom, Left], Left). row([Cell | Row]) :- row(Row, Cell). row([], _). row([RightCell | Row], LeftCell) :- right(LeftCell, Side), left(RightCell, Side), row(Row, RightCell). column([Cell | Col]) :- column(Col, Cell). column([], _). column([BottomCell | Col], TopCell) :- top(BottomCell, Side), bottom(TopCell, Side), column(Col, BottomCell). border(Type, Pred, Row) :- maplist(Pred, Row, Tops), maplist(=(Type), Tops). len(X, L) :- length(L, X). rows_cols_cells(W, H, Rows, Cols, Cells) :- length(Rows, H), maplist(len(W), Rows), append(Rows, Cells), transpose(Rows, Cols). cardinality(L1, L2) :- sort(L1, Set), pairs_keys_values(P, Set, _), global_cardinality(L1, P), global_cardinality(L2, P). grid(W, H, Rows, Vars) :- % create a grid of WxH Variables rows_cols_cells(W, H, Rows, Cols, Cells), maplist(cell, Cells), maplist(row, Rows), maplist(column, Cols), sides(SidesByTile), append(SidesByTile, Sides), append(Cells, CellSides), % all sides of the grid should have the same cardinality than the sides of available tiles cardinality(Sides, CellSides), % all border sides should be pastures maplist(call, [nth0(0), last, nth0(0), last], [Rows, Rows, Cols, Cols], Borders), maplist(border(2), [top, bottom, left, right], Borders), maplist(side_id, SidesByTile, Ids), maplist(side_id, Cells, CellIds), append(Ids, FlatIds), append(CellIds, FlatCellIds), % all cells ids should have the same cardinality than the ids of available tiles cardinality(FlatIds, FlatCellIds), maplist(last, CellIds, Vars). ?- grid(7, 12, Rows, Vars), time(labeling([ff], Vars)), print_term(Rows, []). % 19,232,168,326 inferences, 1079.055 CPU in 1082.840 seconds (100% CPU, 17823156 Lips) [ [[2,1,1,2],[2,1,2,1],[2,1,2,1],[2,1,2,1],[2,2,1,1],[2,0,0,2],[2,2,0,0]], [[1,2,1,2],[2,2,2,2],[2,2,2,2],[2,2,0,2],[1,1,1,2],[0,2,1,1],[0,2,0,2]], [[1,2,1,2],[2,2,2,2],[2,2,3,2],[0,2,2,2],[1,1,1,2],[1,2,0,1],[0,2,0,2]], [[1,2,1,2],[2,3,3,2],[3,2,2,3],[2,2,0,2],[1,1,1,2],[0,2,1,1],[0,2,0,2]], [[1,1,2,2],[3,1,3,1],[2,2,1,1],[0,2,2,2],[1,1,1,2],[1,2,0,1],[0,2,0,2]], [[2,1,2,2],[3,0,3,1],[1,2,1,0],[2,1,1,2],[1,1,1,1],[0,2,1,1],[0,2,0,2]], [[2,1,1,2],[3,2,3,1],[1,1,2,2],[1,1,0,1],[1,1,0,1],[1,2,0,1],[0,2,0,2]], [[1,2,1,2],[3,2,3,2],[2,1,1,2],[0,1,2,1],[0,1,1,1],[0,0,0,1],[0,2,0,0]], [[1,0,1,2],[3,0,3,0],[1,2,1,0],[2,0,0,2],[1,1,0,0],[0,0,0,1],[0,2,0,0]], [[1,2,1,2],[3,2,3,2],[1,1,3,2],[0,0,1,1],[0,1,1,0],[0,0,0,1],[0,2,0,0]], [[1,1,2,2],[3,3,1,1],[3,0,0,3],[1,1,0,0],[1,0,0,1],[0,0,0,0],[0,2,0,0]], [[2,2,2,2],[1,2,2,2],[0,2,2,2],[0,0,2,2],[0,2,2,0],[0,0,2,2],[0,2,2,0]] ] Rows = [[[2, 1, 1, 2], [2, 1, 2, 1], [2, 1, 2, 1], [2, 1, 2, 1], [2, 2, 1|...], [2, 0|...], [2|...]], [[1, 2, 1, 2], [2, 2, 2, 2], [2, ]], [[1, 2, 1, 2], [2, 2, 2, 2], [2, 2, 3|...], [0, 2|...], [1|...], [...|...]|...], [[1, 2, 1, 2], [2, 3, 3|...], [3, 2|...], [2|...], [...|...]|...], [[2, 1|...], [3|...], [...|...]|...], [[2|...], [...|...]|...], [[...|...]|...], [...|...]|...], Vars = [90, 153, 153, 153, 105, 10, 40, 102, 170|...]