| % File : pentomino.pl |
| % Authors: Mutsunori Banbara (banbara@kobe-u.ac.jp) |
| % Naoyuki Tamura (tamura@kobe-u.ac.jp) |
| % Updated: 14 February 2008 |
| % Purpose: Pentomino Puzzle |
| % (posed by Henry E. Dudeny, 1907 and Solomon W. Golomb, 1953) |
| |
| /**************************************************************** |
| Count All Solutions |
| ****************************************************************/ |
| count_all(N) :- |
| findall(B, solve_pentomino(N, B), L), |
| length(L, C), |
| write(C), write(' solutions'), nl. |
| |
| /**************************************************************** |
| Main |
| ****************************************************************/ |
| main :- |
| write('Pentomino Puzzle '), nl, |
| write(' Please select a board size.'), nl, |
| write(' 3 : 3 * 20'), nl, |
| write(' 4 : 4 * 15'), nl, |
| write(' 5 : 5 * 12'), nl, |
| write(' 6 : 6 * 10'), nl, |
| write(' 8 : 8 * 8 (with 4 blanks in the center)'), nl, |
| write('Please select a board size in (3..8).'), nl, |
| write('Number = '), |
| current_output(Out), |
| flush_output(Out), |
| read(X), |
| read_yn('All solutions (y/n)? ', All), |
| read_yn('Output (y/n)? ', Output), |
| statistics(runtime, _), |
| solve_pent(X, all(All), output(Output)), |
| statistics(runtime, [_,T]), |
| write('CPU time = '), write(T), write(' msec'), nl. |
| |
| read_yn(Message, YN) :- |
| write(Message), |
| flush_output, |
| read(X), |
| (X == 'y' -> YN = yes; YN = no). |
| |
| solve_pent(X, all(All), output(Output)) :- |
| solve_pentomino(X, Board), |
| (Output == yes -> show_result(Board),nl; true), |
| All == no, |
| !. |
| solve_pent(_, _, _). |
| /**************************************************************** |
| Ê£¿ô¤Î¥Ú¥ó¥È¥ß¥Î¤òÇÛÃÖ¤¹¤ë |
| solve_pentomino(X, B) |
| X : ¥Ü¡¼¥É¤Î½ÄÉý(¹Ô¤Î¿ô) |
| B : ¥Ü¡¼¥É¤Î¹½Â¤ÂÎ |
| ****************************************************************/ |
| solve_pentomino(X, Board) :- |
| pent_board(X, Y, Board), |
| Col is Y+2, |
| set_x_pentomino(X, Y, Col, Board, Z0, Z), |
| solve_pent(X, Y, Col, Board), |
| remove_symmetry(Z0, Z). |
| |
| remove_symmetry(Z0, Z) :- |
| nonvar(Z0), nonvar(Z), |
| !, |
| Z0 @=< Z. |
| remove_symmetry(_, _). |
| |
| solve_pent(X, Y, Col, Board) :- |
| get_search_list(List, 1, 1, X, Y, Col, Board), |
| Pts = ['F','I','L','N','P','T','U','V','W','Y','Z'], |
| solve_pent0(Pts, List, Col, Board). |
| |
| solve_pent0([], _, _, _) :- !. |
| solve_pent0(Pts, [(N, E)|Ls], Col, Board) :- |
| var(E), |
| !, |
| not_one_space(N, Col, Board), |
| pent_select(P, Pts, Pts1), |
| place_pent(P, N, Col, Board), |
| solve_pent0(Pts1, Ls, Col, Board). |
| solve_pent0(Pts, [_|Ls], Col, Board) :- |
| solve_pent0(Pts, Ls, Col, Board). |
| |
| not_one_space(N, Col, B) :- |
| ( |
| N1 is N+1, arg(N1, B, X1), var(X1) |
| ; |
| N2 is N+Col, arg(N2, B, X2), var(X2) |
| ), |
| !. |
| |
| get_search_list([], I, J, X, Y, _, _) :- |
| J =:= Y+1, I =:= X-1, |
| !. |
| get_search_list(L, I, J, X, Y, Col, B) :- |
| I =:= 0, J =< X, |
| !, |
| get_search_list(L, J, 1, X, Y, Col, B). |
| get_search_list(L, I, J, X, Y, Col, B) :- |
| I =:= 0, J > X, |
| !, |
| J1 is J-X+1, |
| get_search_list(L, X, J1, X, Y, Col, B). |
| get_search_list(L, I, J, X, Y, Col, B) :- |
| J =:= Y+1, |
| !, |
| J1 is I+2+Y-X, |
| get_search_list(L, X, J1, X, Y, Col, B). |
| get_search_list([(N,Z)|Ls], I, J, X, Y, Col, B) :- |
| N is Col*I+J+1, |
| arg(N, B, Z), |
| var(Z), |
| !, |
| I1 is I-1, |
| J1 is J+1, |
| get_search_list(Ls, I1, J1, X, Y, Col, B). |
| get_search_list(L, I, J, X, Y, Col, B) :- |
| I1 is I-1, |
| J1 is J+1, |
| get_search_list(L, I1, J1, X, Y, Col, B). |
| /**************************************************************** |
| Remove Symmetry by using X-pentomino |
| ****************************************************************/ |
| set_x_pentomino(X, _, _, Board, Z0, Z) :- |
| X =:= 3, !, |
| ( |
| place_pent('X', 2, 1, 22, Board), |
| look_up_board(1, 3, 22, Board, Z0), |
| look_up_board(3, 3, 22, Board, Z) |
| ; |
| place_pent('X', 2, 2, 22, Board), |
| look_up_board(1, 4, 22, Board, Z0), |
| look_up_board(3, 4, 22, Board, Z) |
| ; |
| place_pent('X', 2, 3, 22, Board), |
| look_up_board(1, 5, 22, Board, Z0), |
| look_up_board(3, 5, 22, Board, Z) |
| ; |
| place_pent('X', 2, 4, 22, Board), |
| look_up_board(1, 6, 22, Board, Z0), |
| look_up_board(3, 6, 22, Board, Z) |
| ; |
| place_pent('X', 2, 5, 22, Board), |
| look_up_board(1, 7, 22, Board, Z0), |
| look_up_board(3, 7, 22, Board, Z) |
| ; |
| place_pent('X', 2, 6, 22, Board), |
| look_up_board(1, 8, 22, Board, Z0), |
| look_up_board(3, 8, 22, Board, Z) |
| ; |
| place_pent('X', 2, 7, 22, Board), |
| look_up_board(1, 9, 22, Board, Z0), |
| look_up_board(3, 9, 22, Board, Z) |
| ; |
| place_pent('X', 2, 8, 22, Board), |
| look_up_board(1, 10, 22, Board, Z0), |
| look_up_board(3, 10, 22, Board, Z) |
| ; |
| place_pent('X', 2, 9, 22, Board), |
| look_up_board(1, 11, 22, Board, Z0), |
| look_up_board(3, 11, 22, Board, Z) |
| ). |
| |
| set_x_pentomino(X, _, _, Board, Z0, Z) :- |
| X =:= 8, !, |
| ( |
| place_pent('X', 3, 1, 10, Board) |
| ; |
| place_pent('X', 4, 1, 10, Board) |
| ; |
| place_pent('X', 3, 2, 10, Board), |
| look_up_board(2, 4, 10, Board, Z0), |
| look_up_board(4, 2, 10, Board, Z) |
| ). |
| set_x_pentomino(X, Y, Col, Board, Z0, Z) :- |
| 4 =< X, X =< 6, !, |
| M is (X-1)//2, |
| N is (Y-1)//2, |
| for(J0, 1, N), |
| for(I0, 1, M), |
| I is I0+1, |
| J is J0, |
| place_pent('X', I, J, Col, Board), |
| ( |
| X =:= 5, I =:= 3 -> |
| look_up_board(1, J, Col, Board, Z0), |
| look_up_board(5, J, Col, Board, Z) |
| ; |
| true |
| ), |
| ( |
| X =:= 4, I =:= 2, J =:= 7 -> |
| look_up_board(1, 7, Col, Board, Z0), |
| look_up_board(1, 9, Col, Board, Z) |
| ; |
| true |
| ). |
| /**************************************************************** |
| ¥Ü¡¼¥É¤Î(I¡¢J)À®Ê¬¤òÊÖ¤¹ |
| look_up_board(I, J, Col, B, X) |
| I : ¹ÔÈÖ¹æ |
| J : ÎóÈÖ¹æ |
| Col: Îó¤Î¿ô+2(+2¤ÏÊɤΤ¿¤áɬÍ×) |
| B : ¥Ü¡¼¥É¤Î¹½Â¤ÂÎ |
| X : ¥Þ¥¹ |
| ****************************************************************/ |
| look_up_board(I, J, Col, B, X) :- |
| P is Col*I+J+1, |
| arg(P, B, X). |
| /**************************************************************** |
| ¥Ü¡¼¥É¤ÎºîÀ® |
| pent_board(I, J, B) |
| I : ¥Ü¡¼¥É¤Î½ÄÉý(¹Ô¤Î¿ô) |
| J : ¥Ü¡¼¥É¤Î²£Éý(Îó¤Î¿ô) |
| B : ¥Ü¡¼¥É¤Î¹½Â¤ÂÎ |
| ****************************************************************/ |
| pent_board(I, J, Board) :- 3 =< I, I =< 6, !, |
| J is 60//I, |
| make_board(I, J, Board). |
| |
| pent_board(I, I, Board) :- I == 8, !, |
| make_board(8, 8, Board), |
| look_up_board(4, 4, 10, Board, ' '), |
| look_up_board(4, 5, 10, Board, ' '), |
| look_up_board(5, 4, 10, Board, ' '), |
| look_up_board(5, 5, 10, Board, ' '). |
| |
| make_board(I, J, Board) :- |
| M is I+2, N is J+2, |
| Total is M*N, |
| functor(Board, b, Total), |
| frame(1, 1, M, N, Board). |
| |
| frame(_, J, _, N, _) :- J > N, !. |
| frame(I, J, M, N, Board) :- I > M, !, |
| J1 is J+1, |
| frame(1, J1, M, N, Board). |
| frame(I, J, M, N, Board) :- |
| (I =:= 1 ; I =:= M ; J =:= 1 ; J =:= N), |
| !, |
| L is (I-1)*N+J, |
| arg(L, Board, '*'), |
| I1 is I+1, |
| J1 is J, |
| frame(I1, J1, M, N, Board). |
| frame(I, J, M, N, Board) :- |
| I1 is I+1, |
| J1 is J, |
| frame(I1, J1, M, N, Board). |
| /**************************************************************** |
| ¥Ü¡¼¥É¤Îɽ¼¨ |
| show_result(B) |
| B : ¥Ü¡¼¥É¤Î¹½Â¤ÂÎ |
| ****************************************************************/ |
| show_result(B) :- |
| board_size(B, H, W), |
| Col is W+2, |
| for(I, 1, H), |
| nl, |
| for(J, 1, W), |
| look_up_board(I, J, Col, B, P), |
| write_pent(P), |
| fail. |
| show_result(_) :- nl. |
| |
| write_pent(P) :- var(P), !, write('_ '). |
| write_pent(P) :- write(P), write(' '). |
| /**************************************************************** |
| ¥Ü¡¼¥É¤Î¥µ¥¤¥º |
| board_size(B, H, W) |
| B : ¥Ü¡¼¥É¤Î¹½Â¤ÂÎ |
| H : ¥Ü¡¼¥É¤Î½ÄÉý |
| W : ¥Ü¡¼¥É¤Î²£Éý |
| ****************************************************************/ |
| board_size(B, H, W) :- |
| board_width(B, W), |
| board_height(W, H). |
| |
| board_width(B, W) :- |
| count_flame(B, 1, W). |
| |
| count_flame(B, N, W) :- |
| arg(N, B, P), P == '*', |
| !, |
| N1 is N+1, |
| count_flame(B, N1, W). |
| count_flame(_, N, W) :- |
| W is N-4. |
| |
| board_height(W, H) :- |
| 10 =< W, W =< 20, |
| !, |
| H is 60//W. |
| board_height(8, 8). |
| /**************************************************************** |
| ¥Ú¥ó¥È¥ß¥Î¤ò£±¤ÄÇÛÃÖ¤¹¤ë |
| place_pent(P, I, J, Col, B) |
| P : ¥Ú¥ó¥È¥ß¥Î¤Î¼ïÎà̾ |
| I : ¹ÔÈÖ¹æ |
| J : ÎóÈÖ¹æ |
| Col: Îó¤Î¿ô+2(+2¤ÏÊɤΤ¿¤áɬÍ×) |
| B : ¥Ü¡¼¥É¤Î¹½Â¤ÂÎ |
| ****************************************************************/ |
| place_pent(P, I, J, Col, B) :- |
| C is Col*I+J+1, |
| !, |
| place_pent(P, C, Col, B). |
| |
| % Pentmino = 'X' |
| % Number = 1 |
| % D |
| % C E G |
| % F |
| place_pent('X', C, Col, Board) :- |
| arg(C, Board, 'X'), |
| D is C-Col+1, |
| arg(D, Board, 'X'), |
| E is C+1, |
| arg(E, Board, 'X'), |
| F is E+Col, |
| arg(F, Board, 'X'), |
| G is E+1, |
| arg(G, Board, 'X'). |
| % Pentmino = 'F' |
| % Number = 1 |
| % D F |
| % C E |
| % G |
| place_pent('F', C, Col, Board) :- |
| arg(C, Board, 'F'), |
| D is C-Col+1, |
| arg(D, Board, 'F'), |
| E is C+1, |
| arg(E, Board, 'F'), |
| F is D+1, |
| arg(F, Board, 'F'), |
| G is E+Col, |
| arg(G, Board, 'F'). |
| % Pentmino = 'F' |
| % Number = 2 |
| % D |
| % C E F |
| % G |
| place_pent('F', C, Col, Board) :- |
| arg(C, Board, 'F'), |
| D is C-Col+1, |
| arg(D, Board, 'F'), |
| E is C+1, |
| arg(E, Board, 'F'), |
| F is E+1, |
| arg(F, Board, 'F'), |
| G is F+Col, |
| arg(G, Board, 'F'). |
| % Pentmino = 'F' |
| % Number = 3 |
| % C |
| % E G |
| % D F |
| place_pent('F', C, Col, Board) :- |
| arg(C, Board, 'F'), |
| D is C+(2*Col)-1, |
| arg(D, Board, 'F'), |
| E is C+Col, |
| arg(E, Board, 'F'), |
| F is D+1, |
| arg(F, Board, 'F'), |
| G is E+1, |
| arg(G, Board, 'F'). |
| % Pentmino = 'F' |
| % Number = 4 |
| % C |
| % D E G |
| % F |
| place_pent('F', C, Col, Board) :- |
| arg(C, Board, 'F'), |
| D is C+Col, |
| arg(D, Board, 'F'), |
| E is D+1, |
| arg(E, Board, 'F'), |
| F is E+Col, |
| arg(F, Board, 'F'), |
| G is E+1, |
| arg(G, Board, 'F'). |
| % Pentmino = 'F' |
| % Number = 5 |
| % C D |
| % E G |
| % F |
| place_pent('F', C, Col, Board) :- |
| arg(C, Board, 'F'), |
| D is C+1, |
| arg(D, Board, 'F'), |
| E is D+Col, |
| arg(E, Board, 'F'), |
| F is E+Col, |
| arg(F, Board, 'F'), |
| G is E+1, |
| arg(G, Board, 'F'). |
| % Pentmino = 'F' |
| % Number = 6 |
| % E |
| % C D G |
| % F |
| place_pent('F', C, Col, Board) :- |
| arg(C, Board, 'F'), |
| D is C+1, |
| arg(D, Board, 'F'), |
| E is C-Col+2, |
| arg(E, Board, 'F'), |
| F is D+Col, |
| arg(F, Board, 'F'), |
| G is D+1, |
| arg(G, Board, 'F'). |
| % Pentmino = 'F' |
| % Number = 7 |
| % D |
| % C E |
| % F G |
| place_pent('F', C, Col, Board) :- |
| arg(C, Board, 'F'), |
| D is C-Col+1, |
| arg(D, Board, 'F'), |
| E is C+1, |
| arg(E, Board, 'F'), |
| F is E+Col, |
| arg(F, Board, 'F'), |
| G is F+1, |
| arg(G, Board, 'F'). |
| % Pentmino = 'F' |
| % Number = 8 |
| % D |
| % C F G |
| % E |
| place_pent('F', C, Col, Board) :- |
| arg(C, Board, 'F'), |
| D is C-Col+1, |
| arg(D, Board, 'F'), |
| E is C+Col, |
| arg(E, Board, 'F'), |
| F is C+1, |
| arg(F, Board, 'F'), |
| G is F+1, |
| arg(G, Board, 'F'). |
| % Pentmino = 'I' |
| % Number = 1 |
| % C |
| % D |
| % E |
| % F |
| % G |
| place_pent('I', C, Col, Board) :- |
| arg(C, Board, 'I'), |
| D is C+Col, |
| arg(D, Board, 'I'), |
| E is D+Col, |
| arg(E, Board, 'I'), |
| F is E+Col, |
| arg(F, Board, 'I'), |
| G is F+Col, |
| arg(G, Board, 'I'). |
| % Pentmino = 'I' |
| % Number = 2 |
| % C D E F G |
| place_pent('I', C, _, Board) :- |
| arg(C, Board, 'I'), |
| D is C+1, |
| arg(D, Board, 'I'), |
| E is D+1, |
| arg(E, Board, 'I'), |
| F is E+1, |
| arg(F, Board, 'I'), |
| G is F+1, |
| arg(G, Board, 'I'). |
| % Pentmino = 'L' |
| % Number = 1 |
| % C |
| % D |
| % E |
| % F G |
| place_pent('L', C, Col, Board) :- |
| arg(C, Board, 'L'), |
| D is C+Col, |
| arg(D, Board, 'L'), |
| E is D+Col, |
| arg(E, Board, 'L'), |
| F is E+Col, |
| arg(F, Board, 'L'), |
| G is F+1, |
| arg(G, Board, 'L'). |
| % Pentmino = 'L' |
| % Number = 2 |
| % C E F G |
| % D |
| place_pent('L', C, Col, Board) :- |
| arg(C, Board, 'L'), |
| D is C+Col, |
| arg(D, Board, 'L'), |
| E is C+1, |
| arg(E, Board, 'L'), |
| F is E+1, |
| arg(F, Board, 'L'), |
| G is F+1, |
| arg(G, Board, 'L'). |
| % Pentmino = 'L' |
| % Number = 3 |
| % C D |
| % E |
| % F |
| % G |
| place_pent('L', C, Col, Board) :- |
| arg(C, Board, 'L'), |
| D is C+1, |
| arg(D, Board, 'L'), |
| E is D+Col, |
| arg(E, Board, 'L'), |
| F is E+Col, |
| arg(F, Board, 'L'), |
| G is F+Col, |
| arg(G, Board, 'L'). |
| % Pentmino = 'L' |
| % Number = 4 |
| % F |
| % C D E G |
| place_pent('L', C, Col, Board) :- |
| arg(C, Board, 'L'), |
| D is C+1, |
| arg(D, Board, 'L'), |
| E is D+1, |
| arg(E, Board, 'L'), |
| F is E-Col+1, |
| arg(F, Board, 'L'), |
| G is E+1, |
| arg(G, Board, 'L'). |
| % Pentmino = 'L' |
| % Number = 5 |
| % C |
| % D |
| % F |
| % E G |
| place_pent('L', C, Col, Board) :- |
| arg(C, Board, 'L'), |
| D is C+Col, |
| arg(D, Board, 'L'), |
| E is D+(2*Col)-1, |
| arg(E, Board, 'L'), |
| F is D+Col, |
| arg(F, Board, 'L'), |
| G is E+1, |
| arg(G, Board, 'L'). |
| % Pentmino = 'L' |
| % Number = 6 |
| % C |
| % D E F G |
| place_pent('L', C, Col, Board) :- |
| arg(C, Board, 'L'), |
| D is C+Col, |
| arg(D, Board, 'L'), |
| E is D+1, |
| arg(E, Board, 'L'), |
| F is E+1, |
| arg(F, Board, 'L'), |
| G is F+1, |
| arg(G, Board, 'L'). |
| % Pentmino = 'L' |
| % Number = 7 |
| % C E |
| % D |
| % F |
| % G |
| place_pent('L', C, Col, Board) :- |
| arg(C, Board, 'L'), |
| D is C+Col, |
| arg(D, Board, 'L'), |
| E is C+1, |
| arg(E, Board, 'L'), |
| F is D+Col, |
| arg(F, Board, 'L'), |
| G is F+Col, |
| arg(G, Board, 'L'). |
| % Pentmino = 'L' |
| % Number = 8 |
| % C D E F |
| % G |
| place_pent('L', C, Col, Board) :- |
| arg(C, Board, 'L'), |
| D is C+1, |
| arg(D, Board, 'L'), |
| E is D+1, |
| arg(E, Board, 'L'), |
| F is E+1, |
| arg(F, Board, 'L'), |
| G is F+Col, |
| arg(G, Board, 'L'). |
| % Pentmino = 'N' |
| % Number = 1 |
| % C |
| % D |
| % E F |
| % G |
| place_pent('N', C, Col, Board) :- |
| arg(C, Board, 'N'), |
| D is C+Col, |
| arg(D, Board, 'N'), |
| E is D+Col, |
| arg(E, Board, 'N'), |
| F is E+1, |
| arg(F, Board, 'N'), |
| G is F+Col, |
| arg(G, Board, 'N'). |
| % Pentmino = 'N' |
| % Number = 2 |
| % D F G |
| % C E |
| place_pent('N', C, Col, Board) :- |
| arg(C, Board, 'N'), |
| D is C-Col+1, |
| arg(D, Board, 'N'), |
| E is C+1, |
| arg(E, Board, 'N'), |
| F is D+1, |
| arg(F, Board, 'N'), |
| G is F+1, |
| arg(G, Board, 'N'). |
| % Pentmino = 'N' |
| % Number = 3 |
| % C |
| % D E |
| % F |
| % G |
| place_pent('N', C, Col, Board) :- |
| arg(C, Board, 'N'), |
| D is C+Col, |
| arg(D, Board, 'N'), |
| E is D+1, |
| arg(E, Board, 'N'), |
| F is E+Col, |
| arg(F, Board, 'N'), |
| G is F+Col, |
| arg(G, Board, 'N'). |
| % Pentmino = 'N' |
| % Number = 4 |
| % E G |
| % C D F |
| place_pent('N', C, Col, Board) :- |
| arg(C, Board, 'N'), |
| D is C+1, |
| arg(D, Board, 'N'), |
| E is C-Col+2, |
| arg(E, Board, 'N'), |
| F is D+1, |
| arg(F, Board, 'N'), |
| G is E+1, |
| arg(G, Board, 'N'). |
| % Pentmino = 'N' |
| % Number = 5 |
| % C |
| % E |
| % D G |
| % F |
| place_pent('N', C, Col, Board) :- |
| arg(C, Board, 'N'), |
| D is C+(2*Col)-1, |
| arg(D, Board, 'N'), |
| E is C+Col, |
| arg(E, Board, 'N'), |
| F is D+Col, |
| arg(F, Board, 'N'), |
| G is D+1, |
| arg(G, Board, 'N'). |
| % Pentmino = 'N' |
| % Number = 6 |
| % C D |
| % E F G |
| place_pent('N', C, Col, Board) :- |
| arg(C, Board, 'N'), |
| D is C+1, |
| arg(D, Board, 'N'), |
| E is D+Col, |
| arg(E, Board, 'N'), |
| F is E+1, |
| arg(F, Board, 'N'), |
| G is F+1, |
| arg(G, Board, 'N'). |
| % Pentmino = 'N' |
| % Number = 7 |
| % D |
| % C F |
| % E |
| % G |
| place_pent('N', C, Col, Board) :- |
| arg(C, Board, 'N'), |
| D is C-Col+1, |
| arg(D, Board, 'N'), |
| E is C+Col, |
| arg(E, Board, 'N'), |
| F is C+1, |
| arg(F, Board, 'N'), |
| G is E+Col, |
| arg(G, Board, 'N'). |
| % Pentmino = 'N' |
| % Number = 8 |
| % C D E |
| % F G |
| place_pent('N', C, Col, Board) :- |
| arg(C, Board, 'N'), |
| D is C+1, |
| arg(D, Board, 'N'), |
| E is D+1, |
| arg(E, Board, 'N'), |
| F is E+Col, |
| arg(F, Board, 'N'), |
| G is F+1, |
| arg(G, Board, 'N'). |
| % Pentmino = 'P' |
| % Number = 1 |
| % C E |
| % D G |
| % F |
| place_pent('P', C, Col, Board) :- |
| arg(C, Board, 'P'), |
| D is C+Col, |
| arg(D, Board, 'P'), |
| E is C+1, |
| arg(E, Board, 'P'), |
| F is D+Col, |
| arg(F, Board, 'P'), |
| G is D+1, |
| arg(G, Board, 'P'). |
| % Pentmino = 'P' |
| % Number = 2 |
| % C D F |
| % E G |
| place_pent('P', C, Col, Board) :- |
| arg(C, Board, 'P'), |
| D is C+1, |
| arg(D, Board, 'P'), |
| E is D+Col, |
| arg(E, Board, 'P'), |
| F is D+1, |
| arg(F, Board, 'P'), |
| G is E+1, |
| arg(G, Board, 'P'). |
| % Pentmino = 'P' |
| % Number = 3 |
| % D |
| % C F |
| % E G |
| place_pent('P', C, Col, Board) :- |
| arg(C, Board, 'P'), |
| D is C-(Col-1), |
| arg(D, Board, 'P'), |
| E is C+Col, |
| arg(E, Board, 'P'), |
| F is C+1, |
| arg(F, Board, 'P'), |
| G is E+1, |
| arg(G, Board, 'P'). |
| % Pentmino = 'P' |
| % Number = 4 |
| % C E |
| % D F G |
| place_pent('P', C, Col, Board) :- |
| arg(C, Board, 'P'), |
| D is C+Col, |
| arg(D, Board, 'P'), |
| E is C+1, |
| arg(E, Board, 'P'), |
| F is D+1, |
| arg(F, Board, 'P'), |
| G is F+1, |
| arg(G, Board, 'P'). |
| % Pentmino = 'P' |
| % Number = 5 |
| % C E |
| % D F |
| % G |
| place_pent('P', C, Col, Board) :- |
| arg(C, Board, 'P'), |
| D is C+Col, |
| arg(D, Board, 'P'), |
| E is C+1, |
| arg(E, Board, 'P'), |
| F is D+1, |
| arg(F, Board, 'P'), |
| G is F+Col, |
| arg(G, Board, 'P'). |
| % Pentmino = 'P' |
| % Number = 6 |
| % D F |
| % C E G |
| place_pent('P', C, Col, Board) :- |
| arg(C, Board, 'P'), |
| D is C-(Col-1), |
| arg(D, Board, 'P'), |
| E is C+1, |
| arg(E, Board, 'P'), |
| F is D+1, |
| arg(F, Board, 'P'), |
| G is E+1, |
| arg(G, Board, 'P'). |
| % Pentmino = 'P' |
| % Number = 7 |
| % C |
| % D F |
| % E G |
| place_pent('P', C, Col, Board) :- |
| arg(C, Board, 'P'), |
| D is C+Col, |
| arg(D, Board, 'P'), |
| E is D+Col, |
| arg(E, Board, 'P'), |
| F is D+1, |
| arg(F, Board, 'P'), |
| G is E+1, |
| arg(G, Board, 'P'). |
| % Pentmino = 'P' |
| % Number = 8 |
| % C E G |
| % D F |
| place_pent('P', C, Col, Board) :- |
| arg(C, Board, 'P'), |
| D is C+Col, |
| arg(D, Board, 'P'), |
| E is C+1, |
| arg(E, Board, 'P'), |
| F is D+1, |
| arg(F, Board, 'P'), |
| G is E+1, |
| arg(G, Board, 'P'). |
| % Pentmino = 'T' |
| % Number = 1 |
| % C D F |
| % E |
| % G |
| place_pent('T', C, Col, Board) :- |
| arg(C, Board, 'T'), |
| D is C+1, |
| arg(D, Board, 'T'), |
| E is D+Col, |
| arg(E, Board, 'T'), |
| F is D+1, |
| arg(F, Board, 'T'), |
| G is E+Col, |
| arg(G, Board, 'T'). |
| % Pentmino = 'T' |
| % Number = 2 |
| % E |
| % C D F |
| % G |
| place_pent('T', C, Col, Board) :- |
| arg(C, Board, 'T'), |
| D is C+1, |
| arg(D, Board, 'T'), |
| E is C-(Col-2), |
| arg(E, Board, 'T'), |
| F is D+1, |
| arg(F, Board, 'T'), |
| G is F+Col, |
| arg(G, Board, 'T'). |
| % Pentmino = 'T' |
| % Number = 3 |
| % C |
| % E |
| % D F G |
| place_pent('T', C, Col, Board) :- |
| arg(C, Board, 'T'), |
| D is C+(Col*2)-1, |
| arg(D, Board, 'T'), |
| E is C+Col, |
| arg(E, Board, 'T'), |
| F is D+1, |
| arg(F, Board, 'T'), |
| G is F+1, |
| arg(G, Board, 'T'). |
| % Pentmino = 'T' |
| % Number = 4 |
| % C |
| % D F G |
| % E |
| place_pent('T', C, Col, Board) :- |
| arg(C, Board, 'T'), |
| D is C+Col, |
| arg(D, Board, 'T'), |
| E is D+Col, |
| arg(E, Board, 'T'), |
| F is D+1, |
| arg(F, Board, 'T'), |
| G is F+1, |
| arg(G, Board, 'T'). |
| % Pentmino = 'U' |
| % Number = 1 |
| % C F |
| % D E G |
| place_pent('U', C, Col, Board) :- |
| arg(C, Board, 'U'), |
| D is C+Col, |
| arg(D, Board, 'U'), |
| E is D+1, |
| arg(E, Board, 'U'), |
| F is C+2, |
| arg(F, Board, 'U'), |
| G is E+1, |
| arg(G, Board, 'U'). |
| % Pentmino = 'U' |
| % Number = 2 |
| % C E |
| % D |
| % F G |
| place_pent('U', C, Col, Board) :- |
| arg(C, Board, 'U'), |
| D is C+Col, |
| arg(D, Board, 'U'), |
| E is C+1, |
| arg(E, Board, 'U'), |
| F is D+Col, |
| arg(F, Board, 'U'), |
| G is F+1, |
| arg(G, Board, 'U'). |
| % Pentmino = 'U' |
| % Number = 3 |
| % C E F |
| % D G |
| place_pent('U', C, Col, Board) :- |
| arg(C, Board, 'U'), |
| D is C+Col, |
| arg(D, Board, 'U'), |
| E is C+1, |
| arg(E, Board, 'U'), |
| F is E+1, |
| arg(F, Board, 'U'), |
| G is D+2, |
| arg(G, Board, 'U'). |
| % Pentmino = 'U' |
| % Number = 4 |
| % C D |
| % F |
| % E G |
| place_pent('U', C, Col, Board) :- |
| arg(C, Board, 'U'), |
| D is C+1, |
| arg(D, Board, 'U'), |
| E is C+(2*Col), |
| arg(E, Board, 'U'), |
| F is D+Col, |
| arg(F, Board, 'U'), |
| G is E+1, |
| arg(G, Board, 'U'). |
| % Pentmino = 'V' |
| % Number = 1 |
| % C |
| % D |
| % E F G |
| place_pent('V', C, Col, Board) :- |
| arg(C, Board, 'V'), |
| D is C+Col, |
| arg(D, Board, 'V'), |
| E is D+Col, |
| arg(E, Board, 'V'), |
| F is E+1, |
| arg(F, Board, 'V'), |
| G is F+1, |
| arg(G, Board, 'V'). |
| % Pentmino = 'V' |
| % Number = 2 |
| % C E G |
| % D |
| % F |
| place_pent('V', C, Col, Board) :- |
| arg(C, Board, 'V'), |
| D is C+Col, |
| arg(D, Board, 'V'), |
| E is C+1, |
| arg(E, Board, 'V'), |
| F is D+Col, |
| arg(F, Board, 'V'), |
| G is E+1, |
| arg(G, Board, 'V'). |
| % Pentmino = 'V' |
| % Number = 3 |
| % C D E |
| % F |
| % G |
| place_pent('V', C, Col, Board) :- |
| arg(C, Board, 'V'), |
| D is C+1, |
| arg(D, Board, 'V'), |
| E is D+1, |
| arg(E, Board, 'V'), |
| F is E+Col, |
| arg(F, Board, 'V'), |
| G is F+Col, |
| arg(G, Board, 'V'). |
| % Pentmino = 'V' |
| % Number = 4 |
| % D |
| % F |
| % C E G |
| place_pent('V', C, Col, Board) :- |
| arg(C, Board, 'V'), |
| D is C-(2*Col)+2, |
| D > 0, %%% arg/3 ¤ÎÂè°ì°ú¿ô¤¬Éé¤Î¿ô¤Ë¤Ê¤é¤Ê¤¤¤¿¤áɬÍ× |
| arg(D, Board, 'V'), |
| E is C+1, |
| arg(E, Board, 'V'), |
| F is D+Col, |
| arg(F, Board, 'V'), |
| G is E+1, |
| arg(G, Board, 'V'). |
| % Pentmino = 'W' |
| % Number = 1 |
| % C |
| % D E |
| % F G |
| place_pent('W', C, Col, Board) :- |
| arg(C, Board, 'W'), |
| D is C+Col, |
| arg(D, Board, 'W'), |
| E is D+1, |
| arg(E, Board, 'W'), |
| F is E+Col, |
| arg(F, Board, 'W'), |
| G is F+1, |
| arg(G, Board, 'W'). |
| % Pentmino = 'W' |
| % Number = 2 |
| % D G |
| % C F |
| % E |
| place_pent('W', C, Col, Board) :- |
| arg(C, Board, 'W'), |
| D is C-(Col-1), |
| arg(D, Board, 'W'), |
| E is C+Col, |
| arg(E, Board, 'W'), |
| F is C+1, |
| arg(F, Board, 'W'), |
| G is D+1, |
| arg(G, Board, 'W'). |
| % Pentmino = 'W' |
| % Number = 3 |
| % C D |
| % E F |
| % G |
| place_pent('W', C, Col, Board) :- |
| arg(C, Board, 'W'), |
| D is C+1, |
| arg(D, Board, 'W'), |
| E is D+Col, |
| arg(E, Board, 'W'), |
| F is E+1, |
| arg(F, Board, 'W'), |
| G is F+Col, |
| arg(G, Board, 'W'). |
| % Pentmino = 'W' |
| % Number = 4 |
| % E |
| % D G |
| % C F |
| place_pent('W', C, Col, Board) :- |
| arg(C, Board, 'W'), |
| D is C-(Col-1), |
| arg(D, Board, 'W'), |
| E is D-(Col-1), |
| arg(E, Board, 'W'), |
| F is C+1, |
| arg(F, Board, 'W'), |
| G is D+1, |
| arg(G, Board, 'W'). |
| % Pentmino = 'Y' |
| % Number = 1 |
| % E |
| % C D F G |
| place_pent('Y', C, Col, Board) :- |
| arg(C, Board, 'Y'), |
| D is C+1, |
| arg(D, Board, 'Y'), |
| E is C-(Col-2), |
| arg(E, Board, 'Y'), |
| F is D+1, |
| arg(F, Board, 'Y'), |
| G is F+1, |
| arg(G, Board, 'Y'). |
| % Pentmino = 'Y' |
| % Number = 2 |
| % C |
| % D |
| % E G |
| % F |
| place_pent('Y', C, Col, Board) :- |
| arg(C, Board, 'Y'), |
| D is C+Col, |
| arg(D, Board, 'Y'), |
| E is D+Col, |
| arg(E, Board, 'Y'), |
| F is E+Col, |
| arg(F, Board, 'Y'), |
| G is E+1, |
| arg(G, Board, 'Y'). |
| % Pentmino = 'Y' |
| % Number = 3 |
| % C D F G |
| % E |
| place_pent('Y', C, Col, Board) :- |
| arg(C, Board, 'Y'), |
| D is C+1, |
| arg(D, Board, 'Y'), |
| E is D+Col, |
| arg(E, Board, 'Y'), |
| F is D+1, |
| arg(F, Board, 'Y'), |
| G is F+1, |
| arg(G, Board, 'Y'). |
| % Pentmino = 'Y' |
| % Number = 4 |
| % D |
| % C E |
| % F |
| % G |
| place_pent('Y', C, Col, Board) :- |
| arg(C, Board, 'Y'), |
| D is C-(Col-1), |
| arg(D, Board, 'Y'), |
| E is C+1, |
| arg(E, Board, 'Y'), |
| F is E+Col, |
| arg(F, Board, 'Y'), |
| G is F+Col, |
| arg(G, Board, 'Y'). |
| % Pentmino = 'Y' |
| % Number = 5 |
| % C |
| % D F |
| % E |
| % G |
| place_pent('Y', C, Col, Board) :- |
| arg(C, Board, 'Y'), |
| D is C+Col, |
| arg(D, Board, 'Y'), |
| E is D+Col, |
| arg(E, Board, 'Y'), |
| F is D+1, |
| arg(F, Board, 'Y'), |
| G is E+Col, |
| arg(G, Board, 'Y'). |
| % Pentmino = 'Y' |
| % Number = 6 |
| % C D E G |
| % F |
| place_pent('Y', C, Col, Board) :- |
| arg(C, Board, 'Y'), |
| D is C+1, |
| arg(D, Board, 'Y'), |
| E is D+1, |
| arg(E, Board, 'Y'), |
| F is E+Col, |
| arg(F, Board, 'Y'), |
| G is E+1, |
| arg(G, Board, 'Y'). |
| % Pentmino = 'Y' |
| % Number = 7 |
| % C |
| % E |
| % D F |
| % G |
| place_pent('Y', C, Col, Board) :- |
| arg(C, Board, 'Y'), |
| D is C+(2*Col)-1, |
| arg(D, Board, 'Y'), |
| E is C+Col, |
| arg(E, Board, 'Y'), |
| F is D+1, |
| arg(F, Board, 'Y'), |
| G is F+Col, |
| arg(G, Board, 'Y'). |
| % Pentmino = 'Y' |
| % Number = 8 |
| % D |
| % C E F G |
| place_pent('Y', C, Col, Board) :- |
| arg(C, Board, 'Y'), |
| D is C-(Col-1), |
| arg(D, Board, 'Y'), |
| E is C+1, |
| arg(E, Board, 'Y'), |
| F is E+1, |
| arg(F, Board, 'Y'), |
| G is F+1, |
| arg(G, Board, 'Y'). |
| % Pentmino = 'Z' |
| % Number = 1 |
| % C D |
| % E |
| % F G |
| place_pent('Z', C, Col, Board) :- |
| arg(C, Board, 'Z'), |
| D is C+1, |
| arg(D, Board, 'Z'), |
| E is D+Col, |
| arg(E, Board, 'Z'), |
| F is E+Col, |
| arg(F, Board, 'Z'), |
| G is F+1, |
| arg(G, Board, 'Z'). |
| % Pentmino = 'Z' |
| % Number = 2 |
| % F |
| % C E G |
| % D |
| place_pent('Z', C, Col, Board) :- |
| arg(C, Board, 'Z'), |
| D is C+Col, |
| arg(D, Board, 'Z'), |
| E is C+1, |
| arg(E, Board, 'Z'), |
| F is C-(Col-2), |
| arg(F, Board, 'Z'), |
| G is E+1, |
| arg(G, Board, 'Z'). |
| % Pentmino = 'Z' |
| % Number = 3 |
| % C F |
| % E |
| % D G |
| place_pent('Z', C, Col, Board) :- |
| arg(C, Board, 'Z'), |
| D is C+(2*Col)-1, |
| arg(D, Board, 'Z'), |
| E is C+Col, |
| arg(E, Board, 'Z'), |
| F is C+1, |
| arg(F, Board, 'Z'), |
| G is D+1, |
| arg(G, Board, 'Z'). |
| % Pentmino = 'Z' |
| % Number = 4 |
| % C |
| % D E F |
| % G |
| place_pent('Z', C, Col, Board) :- |
| arg(C, Board, 'Z'), |
| D is C+Col, |
| arg(D, Board, 'Z'), |
| E is D+1, |
| arg(E, Board, 'Z'), |
| F is E+1, |
| arg(F, Board, 'Z'), |
| G is F+Col, |
| arg(G, Board, 'Z'). |
| |
| /**************************************************************** |
| Utilities |
| ****************************************************************/ |
| for(M, M, N) :- M =< N. |
| for(I, M, N) :- M =< N, M1 is M + 1, for(I, M1, N). |
| |
| pent_select(X, [X|Xs], Xs). |
| pent_select(X, [Y|Ys], [Y|Zs]) :- pent_select(X, Ys, Zs). |
| |
| /**************************************************************** |
| For applet |
| ****************************************************************/ |
| |
| pentomino_applet(X, B) :- |
| solve_pentomino(X, B0), |
| remove_asterisk(B0, B). |
| |
| remove_asterisk(B0, B) :- |
| B0 =.. [_|As], |
| rm_aster(As, B). |
| |
| rm_aster([], []) :- !. |
| rm_aster([A|As], Ps) :- A == '*', !, |
| rm_aster(As,Ps). |
| rm_aster([A|As], [A|Ps]) :- |
| rm_aster(As,Ps). |
| |
| |
