% http://www.cs.kuleuven.be/~dtai/events/ASP-competition/Benchmarks/EdgeMatching1.shtml % B-Prolog version 7.3 (uses table constraints and the global constraint assignment/2) % by Neng-Fa Zhou, April 6, 2009 :-include(base). solve(As):- get_largest_atom(As,row(N)), % defined in base.pl get_largest_atom(As,col(M)), NTiles is N*M, functor(TilesVect,v,NTiles), functor(CellsVect,v,NTiles), findall(C,member(colour(C),As),Cs), map(Cs,0,ICs,MapC), % ICs: encoded colours as integers create_tiles(TilesVect,1,NTiles,MapC,CNos,As), create_cells(CellsVect,1,NTiles,ICs,TNos), assignment(CNos,TNos), % CNos and TNos are duals TilesVect=..[_|Tiles], CellsVect=..[_|Cells], constrain_cell_edges(Cells,N,M,CellsVect), constrain_tiles_cells(Tiles,Cells), label_center_cell(NTiles,CellsVect,TilesVect), label(TNos,TilesVect),!, output(Tiles,M). solve(_):- format("UNSATISFIABLE~n"). % assign a tile to a center cell and determine its rotation label_center_cell(NTiles,CellsVect,TilesVect):- Index is NTiles//2, arg(Index,CellsVect,Cell), Cell=cell(_,TNo,_,_,_,_), indomain(TNo), arg(TNo,TilesVect,Tile), Tile=tile(_,_,Rotation,_,_,_,_), indomain(Rotation). % assign a tile to a cell and determine its rotation label([],_). label([TNo|TNos],TilesVect):-integer(TNo),!, arg(TNo,TilesVect,Tile), Tile=tile(_,_,Rotation,_,_,_,_), indomain(Rotation), label(TNos,TilesVect). label(TNos,TilesVect):- deleteff(TNo,TNos,Rest), indomain(TNo), arg(TNo,TilesVect,Tile), Tile=tile(_,_,Rotation,_,_,_,_), indomain(Rotation), label(Rest,TilesVect). create_tiles(_,TNo,NTiles,_,[],_):-TNo>NTiles,!. create_tiles(TilesVect,TNo,NTiles,MapC,[CNo|CNos],As):- Tile=tile(TNo,CNo,Rotation,Top,Right,Bottom,Left), Rotation :: 0..3, CNo :: 1..NTiles, member(tileSide(TNo,top,Ct),As), member(tileSide(TNo,right,Cr),As), member(tileSide(TNo,bottom,Cb),As), member(tileSide(TNo,left,Cl),As),!, arg(TNo,TilesVect,Tile), map([Ct,Cr,Cb,Cl],[ICt,ICr,ICb,ICl],MapC), (Rotation,Top,Right,Bottom,Left) in [(0,ICt,ICr,ICb,ICl), (1,ICl,ICt,ICr,ICb), (2,ICb,ICl,ICt,ICr), (3,ICr,ICb,ICl,ICt)], /* Rotation#=0 #=> Top#=ICt #/\ Right#=ICr #/\ Bottom#=ICb #/\ Left#=ICl, Rotation#=1 #=> Top#=ICl #/\ Right#=ICt #/\ Bottom#=ICr #/\ Left#=ICb, Rotation#=2 #=> Top#=ICb #/\ Right#=ICl #/\ Bottom#=ICt #/\ Left#=ICr, Rotation#=3 #=> Top#=ICr #/\ Right#=ICb #/\ Bottom#=ICl #/\ Left#=ICt, */ TNo1 is TNo+1, create_tiles(TilesVect,TNo1,NTiles,MapC,CNos,As). create_cells(_,CNo,NTiles,_,[]):-CNo>NTiles,!. create_cells(CellsVect,CNo,NTiles,ICs,[TNo|TNos]):- Cell=cell(CNo,TNo,Top,Right,Bottom,Left), TNo :: 1..NTiles, arg(CNo,CellsVect,Cell), [Top,Right,Bottom,Left] :: ICs, CNo1 is CNo+1, create_cells(CellsVect,CNo1,NTiles,ICs,TNos). %% make sure the colors of the edges of each cell match those of its neighbors constrain_cell_edges([],_,_,_). constrain_cell_edges([Cell|Cells],N,M,CellsVect):- constrain_top_edge(Cell,N,M,CellsVect), constrain_right_edge(Cell,N,M,CellsVect), constrain_bottom_edge(Cell,N,M,CellsVect), constrain_left_edge(Cell,N,M,CellsVect), constrain_cell_edges(Cells,N,M,CellsVect). constrain_top_edge(Cell,_,M,CellsVect):- Cell=cell(CNo,_,Top,_,_,_), Row is (CNo-1)//M+1, Col is (CNo-1) mod M+1, Row1 is Row-1, Row1>=1,!, CNo1 is (Row1-1)*M+Col, arg(CNo1,CellsVect,Cell1),Cell1=cell(CNo1,_,_,_,Bottom1,_), Top=Bottom1. constrain_top_edge(_,_,_,_). constrain_right_edge(Cell,_,M,CellsVect):- Cell=cell(CNo,_,_,Right,_,_), Row is (CNo-1)//M+1, Col is (CNo-1) mod M+1, Col1 is Col+1, Col1==1,!,CNo1 is (Row-1)*M+Col1, arg(CNo1,CellsVect,Cell1),Cell1=cell(CNo1,_,_,Right1,_,_),!, Left=Right1. constrain_left_edge(_,_,_,_). % ensure the edges of each tile match those of the occupied cell constrain_tiles_cells([],_). constrain_tiles_cells([Title|Tiles],Cells):- constrain_tile_cells_aux(Title,Cells), constrain_tiles_cells(Tiles,Cells). constrain_tile_cells_aux(_,[]). constrain_tile_cells_aux(Tile,[Cell|Cells]):- Tile=tile(TNo1,_,_,TTop,TRight,TBottom,TLeft), Cell=cell(_,TNo,CTop,CRight,CBottom,CLeft), TTop#\=CTop #\/ TRight#\=CRight #\/ TBottom#\=CBottom #\/ TLeft#\=CLeft #=> TNo#\=TNo1, constrain_tile_cells_aux(Tile,Cells). output([],_):-nl. output([Tile|Tiles],M):- Tile=tile(TNo,CNo,Rotation,_,_,_,_), Row is (CNo-1)//M+1, Col is (CNo-1) mod M+1, (Rotation==0->Rotation1=0;Rotation==1->Rotation1=90;Rotation==2->Rotation1=180;Rotation1=270), format("chosenTile(~w,~w,~w). chosenRotation(~w,~w,~w). ",[Col,Row,TNo,Col,Row,Rotation1]), output(Tiles,M). /* test:- solve([tile(1),tile(2),tile(3),tile(4),colour(red),colour(green),colour(blue),colour(black),row(1),row(2),col(1),col(2),rotation(0),rotation(90),rotation(180),rotation(270),side(top),side(right),side(bottom),side(left),tileSide(1,top,red),tileSide(1,right,green),tileSide(1,bottom,black),tileSide(1,left,black),tileSide(2,top,blue),tileSide(2,right,red),tileSide(2,bottom,black),tileSide(2,left,black),tileSide(3,top,green),tileSide(3,right,red),tileSide(3,bottom,black),tileSide(3,left,black),tileSide(4,top,red),tileSide(4,right,blue),tileSide(4,bottom,black),tileSide(4,left,black)]). */ test:- solve([tile(1), tile(2), tile(3), tile(4), tile(5), tile(6), tile(7), tile(8), tile(9), col(5), tile(10), tile(11), tile(12), tile(13), tile(14), tile(15), tile(16), tile(17), tile(34), tile(18), tile(19), tile(20), tile(21), tile(22), tile(23), tile(24), tile(25), tile(26), tile(27), tile(28), tile(29), tile(30), tile(31), tile(32), tile(33), col(6), col(7), rotation(0), tile(35), tile(36), tile(37), tile(38), tile(39), tile(40), tile(41), tile(42), tile(43), tile(44), tile(45), tile(46), tile(47), tile(48), tile(49), colour(red), colour(green), colour(blue), colour(yellow), colour(cyan), row(1), row(2), row(3), row(4), row(5), row(6), row(7), col(1), col(2), col(3), col(4), tileSide(15,right,cyan), tileSide(46,left,green), tileSide(32,right,green), tileSide(15,left,yellow), tileSide(5,top,yellow), rotation(90), rotation(180), rotation(270), side(top), side(right), side(bottom), side(left), tileSide(2,top,yellow), tileSide(2,bottom,cyan), tileSide(3,top,cyan), tileSide(2,right,blue), tileSide(2,left,blue), tileSide(43,bottom,blue), tileSide(3,bottom,blue), tileSide(25,left,blue), tileSide(3,right,blue), tileSide(3,left,red), tileSide(22,right,red), tileSide(25,right,green), tileSide(47,left,green), tileSide(25,top,yellow), tileSide(25,bottom,green), tileSide(39,bottom,green), tileSide(47,right,blue), tileSide(45,right,blue), tileSide(47,top,yellow), tileSide(47,bottom,cyan), tileSide(34,top,cyan), tileSide(45,left,cyan), tileSide(29,left,cyan), tileSide(45,bottom,yellow), tileSide(45,top,red), tileSide(46,right,red), tileSide(29,right,yellow), tileSide(21,top,yellow), tileSide(29,top,cyan), tileSide(29,bottom,green), tileSide(15,bottom,green), tileSide(21,bottom,red), tileSide(21,right,green), tileSide(21,left,green), tileSide(5,right,green), tileSide(43,right,blue), tileSide(43,left,cyan), tileSide(22,top,cyan), tileSide(43,top,red), tileSide(1,right,red), tileSide(22,bottom,yellow), tileSide(39,right,yellow), tileSide(22,left,green), tileSide(27,right,green), tileSide(39,left,red), tileSide(34,left,red), tileSide(39,top,red), tileSide(12,bottom,red), tileSide(34,right,yellow), tileSide(46,top,yellow), tileSide(34,bottom,cyan), tileSide(19,bottom,cyan), tileSide(46,bottom,cyan), tileSide(26,top,blue), tileSide(4,right,green), tileSide(8,top,green), tileSide(4,bottom,blue), tileSide(8,bottom,red), tileSide(7,right,red), tileSide(8,left,blue), tileSide(7,left,green), tileSide(38,top,green), tileSide(7,top,blue), tileSide(38,bottom,cyan), tileSide(15,top,cyan), tileSide(18,bottom,cyan), tileSide(5,bottom,green), tileSide(5,left,green), tileSide(14,right,green), tileSide(1,top,green), tileSide(1,bottom,green), tileSide(27,top,green), tileSide(1,left,yellow), tileSide(11,right,yellow), tileSide(27,bottom,blue), tileSide(12,right,blue), tileSide(27,left,cyan), tileSide(28,top,cyan), tileSide(12,left,blue), tileSide(19,right,blue), tileSide(12,top,yellow), tileSide(37,right,yellow), tileSide(19,left,yellow), tileSide(32,top,yellow), tileSide(19,top,red), tileSide(41,bottom,red), tileSide(32,bottom,blue), tileSide(18,right,blue), tileSide(32,left,blue), tileSide(16,right,blue), tileSide(18,left,blue), tileSide(14,top,blue), tileSide(18,top,yellow), tileSide(44,top,yellow), tileSide(14,bottom,yellow), tileSide(14,left,yellow), tileSide(23,bottom,yellow), tileSide(11,top,cyan), tileSide(11,bottom,cyan), tileSide(28,left,cyan), tileSide(11,left,cyan), tileSide(49,top,cyan), tileSide(28,right,blue), tileSide(37,top,blue), tileSide(28,bottom,red), tileSide(35,bottom,red), tileSide(37,bottom,blue), tileSide(41,right,blue), tileSide(37,left,red), tileSide(6,bottom,red), tileSide(41,left,red), tileSide(16,top,red), tileSide(41,top,cyan), tileSide(40,bottom,cyan), tileSide(16,bottom,blue), tileSide(44,left,blue), tileSide(16,left,cyan), tileSide(48,bottom,cyan), tileSide(44,right,yellow), tileSide(23,right,yellow), tileSide(44,bottom,red), tileSide(9,top,red), tileSide(23,left,cyan), tileSide(23,top,red), tileSide(36,bottom,red), tileSide(49,left,cyan), tileSide(49,right,green), tileSide(35,right,green), tileSide(49,bottom,yellow), tileSide(31,bottom,yellow), tileSide(35,left,yellow), tileSide(6,right,yellow), tileSide(35,top,green), tileSide(17,bottom,green), tileSide(6,left,red), tileSide(40,right,red), tileSide(6,top,blue), tileSide(33,bottom,blue), tileSide(40,left,cyan), tileSide(48,right,cyan), tileSide(40,top,red), tileSide(42,right,red), tileSide(48,left,cyan), tileSide(9,left,cyan), tileSide(48,top,cyan), tileSide(30,bottom,cyan), tileSide(9,right,green), tileSide(36,right,green), tileSide(9,bottom,red), tileSide(24,bottom,red), tileSide(36,left,green), tileSide(36,top,cyan), tileSide(20,top,cyan), tileSide(31,right,red), tileSide(31,left,blue), tileSide(17,right,blue), tileSide(31,top,yellow), tileSide(13,top,yellow), tileSide(17,left,green), tileSide(33,right,green), tileSide(17,top,yellow), tileSide(26,bottom,yellow), tileSide(33,left,cyan), tileSide(42,top,cyan), tileSide(33,top,red), tileSide(4,top,red), tileSide(42,bottom,cyan), tileSide(30,right,cyan), tileSide(42,left,blue), tileSide(8,right,blue), tileSide(30,left,yellow), tileSide(24,right,yellow), tileSide(30,top,red), tileSide(7,bottom,red), tileSide(24,left,green), tileSide(20,left,green), tileSide(24,top,green), tileSide(38,right,green), tileSide(20,right,blue), tileSide(20,bottom,blue), tileSide(10,top,blue), tileSide(13,left,yellow), tileSide(13,right,blue), tileSide(26,right,blue), tileSide(13,bottom,green), tileSide(26,left,yellow), tileSide(4,left,yellow), tileSide(10,left,cyan), tileSide(38,left,cyan), tileSide(10,right,cyan), tileSide(10,bottom,blue)]).