/**************************************************************** LLP Example Pentomino Puzzle (posed by Henry E. Dudeny, 1907 and Solomon W. Golomb, 1953) by Naoyuki Tamura (tamura@kobe-u.ac.jp) Dept. CS, Kobe University ****************************************************************/ %%% %%% Tile twelve pentominoes into a rectangle of %%% 3 * 20 (2 solutions), %%% or 4 * 15 (402 solutions), %%% or 5 * 12 (? solutions), %%% or 6 * 10 (2339 solutions), %%% or 7 * 9 (with 3 blanks in the center) (? solutions), %%% or 8 * 8 (with 4 blanks in the center) (65 solutions) %%% %%% Twelve pentominoes (F, I, L, N, P, T, U, V, W, X, Y, Z) are: %%% %%% F-pentomino: %%% +--+--+ %%% | | | %%% +--+--+--+ %%% | | | %%% +--+--+ %%% | | %%% +--+ %%% %%% I-pentomino: +--+ %%% | | %%% +--+ %%% | | %%% +--+ %%% | | %%% +--+ %%% | | %%% +--+ %%% | | %%% +--+ %%% %%% L-pentomino: +--+ %%% | | %%% +--+ %%% | | %%% +--+ %%% | | %%% +--+--+ %%% | | | %%% +--+--+ %%% %%% N-pentomino: +--+--+--+ %%% | | | | %%% +--+--+--+--+ %%% | | | %%% +--+--+ %%% %%% P-pentomino: +--+--+ %%% | | | %%% +--+--+ %%% | | | %%% +--+--+ %%% | | %%% +--+ %%% %%% T-pentomino: +--+--+--+ %%% | | | | %%% +--+--+--+ %%% | | %%% +--+ %%% | | %%% +--+ %%% %%% U-pentomino: +--+ +--+ %%% | | | | %%% +--+--+--+ %%% | | | | %%% +--+--+--+ %%% %%% V-pentomino: +--+ %%% | | %%% +--+ %%% | | %%% +--+--+--+ %%% | | | | %%% +--+--+--+ %%% %%% W-pentomino: +--+ %%% | | %%% +--+--+ %%% | | | %%% +--+--+--+ %%% | | | %%% +--+--+ %%% %%% X-pentomino: %%% +--+ %%% | | %%% +--+--+--+ %%% | | | | %%% +--+--+--+ %%% | | %%% +--+ %%% %%% Y-pentomino: +--+ %%% | | %%% +--+--+--+--+ %%% | | | | | %%% +--+--+--+--+ %%% %%% Z-pentomino: %%% +--+--+ %%% | | | %%% +--+--+ %%% | | %%% +--+--+ %%% | | | %%% +--+--+ %%% %%% You can rotate or flip pentominoes. %%% :- resource p/2. main :- input_board(Board, M, N), read_yn('All solutions (y/n)? ', All), read_yn('Output (y/n)? ', Output), statistics(runtime, _), (rows(M) => columns(N) => all(All) => output(Output) => pentomino(Board)), statistics(runtime, [_,T]), write('CPU time = '), write(T), write(' msec'), nl. read_yn(Message, YN) :- write(Message), readline([Char|_]), ([Char] == "y" -> YN = yes; YN = no). input_board(Board, M, N) :- write('Board size'), nl, write(' 3 : 3 * 20'), nl, write(' 4 : 4 * 15'), nl, write(' 5 : 5 * 12'), nl, write(' 6 : 6 * 10'), nl, write(' 7 : 7 * 9 (with 3 blanks in the center)'), nl, write(' 8 : 8 * 8 (with 4 blanks in the center)'), nl, write('Which (3..8)? '), readint(M), board_size(M, N, Board). board_size(M, N, Board) :- 3 =< M, M =< 6, N is 60//M, make_board(M, N, Board). board_size(7, 9, Board) :- make_board(7, 9, Board), look_board(4, 4, Board, ' '), look_board(4, 5, Board, ' '), look_board(4, 6, Board, ' '). board_size(8, 8, Board) :- make_board(8, 8, Board), look_board(4, 4, Board, ' '), look_board(4, 5, Board, ' '), look_board(5, 4, Board, ' '), look_board(5, 5, Board, ' '). make_board(M, N, Board) :- functor(Board, b, M), make_board(1, M, N, Board). make_board(I, M, _, _) :- I > M, !. make_board(I, M, N, Board) :- I =< M, functor(B, b, N), arg(I, Board, B), I1 is I + 1, make_board(I1, M, N, Board). %% %% Solver %% pentomino(Board) :- pent(Board), (output(yes) -> write_board(Board); true), all(no), !. pentomino(_). pent(Board) :- make_pentominos(Resource), (Resource -<> pent_solve(Board)). %% To avoid symmetric solutions as much as possible, %% we firstly place X-pentomino. pent_solve(Board) :- rows(M), columns(N), M1 is (M+1)//2, N1 is (N+1)//2, for(J, 1, N1), for(I, 1, M1), (M =:= N -> I >= J; true), I1 is I, J1 is J-1, p('X', Shape), place(Shape, 'X', I1, J1, Board), % write_board(Board), readline(_), pent_solve(1, 1, Board). pent_solve(I, J, Board) :- columns(N), J > N, !. pent_solve(I, J, Board) :- rows(M), I > M, !, J1 is J + 1, pent_solve(1, J1, Board). pent_solve(I, J, Board) :- look_board(I, J, Board, X), var(X), !, p(P, Shape), % pick up a pentomino place(Shape, P, I, J, Board), % place it I1 is I + 1, pent_solve(I1, J, Board). pent_solve(I, J, Board) :- I1 is I + 1, pent_solve(I1, J, Board). place([], P, I, J, Board). place([(DI,DJ)|Shape], P, I, J, Board) :- I1 is I + DI, J1 is J + DJ, look_board(I1, J1, Board, P), place(Shape, P, I, J, Board). look_board(I, J, Board, X) :- arg(I, Board, Row), arg(J, Row, X). %% %% Create resources %% make_pentominos(Resource) :- Pentominos = ['F','I','L','N','P','T','U','V','W','X','Y','Z'], make_pentominos(Pentominos, Resource), !. make_pentominos([P], R) :- make_pent(P, R). make_pentominos([P,P1|Ps], (R, R1)) :- make_pent(P, R1), make_pentominos([P1|Ps], R). % Left-most upper-most position is (0,0) make_pent(P, R) :- P = 'F', !, Shape0 = [(0,0),(-1,1),(-1,2),(0,1),(1,1)], all_transformations(P, Shape0, R). make_pent(P, R) :- P = 'I', !, Shape0 = [(0,0),(1,0),(2,0),(3,0),(4,0)], rotate(Shape0, Shape1), R = (p(P,Shape0) & p(P,Shape1)). make_pent(P, R) :- P = 'L', !, Shape0 = [(0,0),(1,0),(2,0),(3,0),(3,1)], all_transformations(P, Shape0, R). make_pent(P, R) :- P = 'N', !, Shape0 = [(0,0),(0,1),(0,2),(1,2),(1,3)], all_transformations(P, Shape0, R). make_pent(P, R) :- P = 'P', !, Shape0 = [(0,0),(0,1),(1,0),(1,1),(2,0)], all_transformations(P, Shape0, R). make_pent(P, R) :- P = 'T', !, Shape0 = [(0,0),(0,1),(0,2),(1,1),(2,1)], all_rotations(P, Shape0, R). make_pent(P, R) :- P = 'U', !, Shape0 = [(0,0),(0,2),(1,0),(1,1),(1,2)], all_rotations(P, Shape0, R). make_pent(P, R) :- P = 'V', !, Shape0 = [(0,0),(1,0),(2,0),(2,1),(2,2)], all_rotations(P, Shape0, R). make_pent(P, R) :- P = 'W', !, Shape0 = [(0,0),(1,0),(1,1),(2,1),(2,2)], all_rotations(P, Shape0, R). make_pent(P, R) :- P = 'X', !, Shape0 = [(0,0),(-1,1),(0,1),(0,2),(1,1)], R = p(P,Shape0). make_pent(P, R) :- P = 'Y', !, Shape0 = [(0,0),(-1,2),(0,1),(0,2),(0,3)], all_transformations(P, Shape0, R). make_pent(P, R) :- P = 'Z', !, Shape0 = [(0,0),(0,1),(1,1),(2,1),(2,2)], rotate(Shape0, Shape1), flip(Shape0, Shape2), rotate(Shape2, Shape3), R = (p(P,Shape0) & p(P,Shape1) & p(P,Shape2) & p(P,Shape3)). all_transformations(P, Shape0, R) :- all_rotations(P, Shape0, R1), flip(Shape0, Shape1), all_rotations(P, Shape1, R2), R = (R1 & R2). all_rotations(P, Shape0, R) :- rotate(Shape0, Shape1), rotate(Shape1, Shape2), rotate(Shape2, Shape3), R = (p(P,Shape0) & p(P,Shape1) & p(P,Shape2) & p(P,Shape3)). rotate(Shape0, Shape) :- rotate_shape(Shape0, Shape1), normalize(Shape1, Shape). rotate_shape([], []). rotate_shape([(I0,J0)|Shape0], [(I,J)|Shape]) :- I is -J0, J is I0, rotate_shape(Shape0, Shape). flip(Shape0, Shape) :- flip_shape(Shape0, Shape1), normalize(Shape1, Shape). flip_shape([], []). flip_shape([(I0,J0)|Shape0], [(I,J)|Shape]) :- I is -I0, J is J0, flip_shape(Shape0, Shape). normalize(Shape0, Shape) :- sort_shape(Shape0, Shape1), Shape1 = [(I0,J0)|_], DI is -I0, DJ is -J0, move_shape(Shape1, DI, DJ, Shape). move_shape([], DI, DJ, []). move_shape([(I0,J0)|Shape0], DI, DJ, [(I,J)|Shape]) :- I is I0 + DI, J is J0 + DJ, move_shape(Shape0, DI, DJ, Shape). sort_shape(Shape0, Shape) :- sort_shape(Shape0, [], Shape). sort_shape([], Shape, Shape). sort_shape([Pos|Shape0], ShapeRest, Shape) :- partition_shape(Shape0, Pos, ShapeL, ShapeR), sort_shape(ShapeL, [Pos|Shape1], Shape), sort_shape(ShapeR, ShapeRest, Shape1). partition_shape([], Pos0, [], []). partition_shape([Pos|Shape], Pos0, [Pos|ShapeL], ShapeR) :- less_pos(Pos, Pos0), !, partition_shape(Shape, Pos0, ShapeL, ShapeR). partition_shape([Pos|Shape], Pos0, ShapeL, [Pos|ShapeR]) :- partition_shape(Shape, Pos0, ShapeL, ShapeR). less_pos((I,J), (I0,J0)) :- (J < J0; J =:= J0, I < I0), !. %% %% Output %% write_board(Board) :- rows(M), columns(N), for(I, 1, M), nl, arg(I, Board, Row), for(J, 1, N), arg(J, Row, P), write_pent(P), fail. write_board(_) :- nl. write_pent(P) :- var(P), !, write('_ '). write_pent(P) :- write(P), write(' '). %% %% Utilities %% for(M, M, N) :- M =< N. for(I, M, N) :- M =< N, M1 is M + 1, for(I, M1, N).