Constraint Logic Programming in Prolog: Hanjie Puzzle Solver
In:
Submitted By luiscleto Words 9959 Pages 40
Constraint Logic Programming in Prolog: Hanjie Puzzle Solver
Lu´ Cleto and Jo˜o Marinheiro ıs a
FEUP-PLOG, Turma 3MIEIC05, Group 23 {ei11077,ei11129}@fe.up.pt http://www.fe.up.pt
Abstract. The purpose of this project was to use constraint logic programming in Prolog to implement a solver for the 2D puzzle, Hanjie. For this purpose we used the clp(FD) library provided by SICStus Prolog 4.2.3, specifically the sum/3 and automaton/3 combinatorial constraints. The program we developed is able to solve puzzles with dimensions up to 88x88, with only one possible solution, in less than one second. When there are multiple solutions, the execution time for the obtaining the first solution varies with the number of possible solutions. These results show that the execution time of the program is primarily affected by the amount of possible results. While larger grid dimensions do increase the execution time, the increase is linear if the number of possible solutions is maintained. On the other hand, increasing the number of possible solutions will lead to an exponential growth in execution time.
1
Introduction
The goal of this project is to use constraint logic programming in Prolog to develop a logic program capable of solving a decision problem in the form of the 2D puzzle, Hanjie. This puzzle consists of a rectangular grid with ’clues’ on top of every column and to the left of every row that indicate the number and length of gray blocks in that column/row. To achieve this goal, first had to be chosen the data structures that would be used to represent the problem. It was decided to use lists of lists, containing the clues for each column/row in every sublist, and a similar structure for the puzzle grid where every sublist is a row of the grid. Every square of the grid can be either a 0 or a 1 where a 0 represents a blank square and 1 represents a gray square. Our implementation also allows the lists of clues to be partially or completely uninstantiated, providing possible values for the uninstantiated elements. Additionally, it allows the puzzle to be written to a file instead of to the terminal as some solutions may be too large to be displayed correctly on the terminal. The most complex aspect of creating constraints for this puzzle is creating a set of rules that will ensure that every gray block occurs in sequence on the proper row, with the proper dimensions, without bordering any other blocks in that row. To solve this particular problem of sequences, it was opted to use automaton/3
2
Hanjie Puzzle Solver
constraints to establish the main rules of the puzzle and ensure the integrity of the gray blocks in every row and column. In addition, a subgoal of the project was to allow for random generation of valid hanjie puzzles, which was achieved with an algorithm similar to how a human being would create the puzzle. The grid is created first by randomly filling it with painted squares and the clues for each row/column are obtained afterwards, this way the puzzle is guaranteed to have at least one possible solution. The remainder of this article will contain several sections dedicated to describing the problem, the data files containing examples of the problem to solve, the decision variables used, the constraints implemented, the adopted search strategy, the solution presentation, the results obtained and the conclusion we achieved. Additionally it will contain in the annex the source code developed for the project.
2
Problem Description
Hanjie is a two dimensional puzzle that starts with a grid of blank squares with clues on top of every column and to the left of every row. Every list of clues contains numbers that indicate the length of every painted block in that row. The length of the list will be the number of blocks that row must contain and every block must be separated from the others by at least one blank square. Additionally, the order of the clues is the order of the blocks in that row and each block must be separated from the next by at least one blank block. For example, a set of clues {3, 2} would indicate that there would have to be exactly two gray blocks, the first composed of three gray squares and the second composed of two gray squares, in that row. They would also have to be separated by at least one blank square. See Fig. 1 for an example of a solved Hanjie puzzle.
Fig. 1. An example of a Hanjie puzzle. This particular example has more than one possible solution.
3
Data Files
Along with the Prolog source code developed to solve the described problem, an additional file called ‘hanjie examples.pl’was created containing several examples of Hanjie puzzles in the form of example name(-ColumnHints, -RowHints)
Hanjie Puzzle Solver
3
where the arguments of the predicate will be initialized with the clues for the columns and the rows in the form of a list of lists for both of them. There are several examples of puzzles and a few with partially or completely uninstantiated hints for the columns/rows. Aditionally, there are predicates to randomly generate Hanjie puzzles of any dimension in the file ‘hanjie generation.pl’. The predicate generate hanjie(+Width, +Height, -ColumnHints, -RowHints), to randomly generate a puzzle that may have more than one solution by randomly painting some cells of the grid and generating the clues, generate hanjie full(+Width, +Height, -ColumnHints, RowHints) that generates a puzzle with only one solution by painting every square and generate hanjie empty(+Width, +Height, -ColumnHints, -RowHints) that generates a puzzle with only one solution by leaving every square blank.
4
Decision Variables
The first set of decision variables created to solve the described problem, are the elements of the puzzle grid which can either be instantiated to 0 or to 1, where 0 represents a blank square and 1 represents a painted square. Additionally, if the clues are also uninstantiated, they are given a domain ranging from 0 to the length of the row and the sum of the elements in the row and of the elements in the list of clues are also stored in a variable.
5
Constraints
For the implementation of a solution to the problem in Prolog with constraint logic programming, several constraints had to be created. To establish these constraints, the puzzle grid’s rows are searched at the same time as the list of clues for the rows. For each set of rows and their corresponding clues, the first constraint added is that the sum of all their elements must have the same value since the number of painted squares, which correspond to 1s must be equal to the total of the clues, and every other square must be blank. This is done through the use of the predicate sum/3, using the operator #= as the second argument for the predicate and a variable for the third which will be the same for the sum of the row elements and of the clues. In addition to these constraints, an automaton/3 constraint is created for each row to ensure the sequence of the colored blocks. This automaton will be an NFA and it starts by creating a loop between the initial state and itself by reading 0s. From the initial state it can move on to the next state by reading a 1. It must then receive a number of 1s equivalent to the remainder of the clue, which will be decremented until it reaches 0. When this happens, another loop with input 0 is created from the current state to itself along with an additional transition from this state to the next one, also by reading a 0. This ensures the painted blocks are separated by at least one blank square. This is repeated for every clue until the list is empty. However, this solution alone could fail if the last painted square was at the end of the row as there would be no blank squares after it and the automaton would
4
Hanjie Puzzle Solver
fail to advance to the next, and final, state. To solve this, a 0 is appended to every row before the automaton constraint is established on this new list.
Fig. 2. An example of the automaton created for a row with the set of clues [2,1]
After these constraints for the rows are established, a list of the columns is obtained by using the predicate transpose/2 of the SICStus Prolog 4.2.3 lists library on the puzzle grid and the process is repeated for this list and the list of corresponding clues.
6
Search Strategy
For the adopted search strategy, the predicate labeling/2 is called for a list of variables containing the elements of the puzzle grid, ordered as seen on the grid from left to right and top to bottom, with the option ff in the option list. It was chosen to use the first fail strategy to attempt to reduce the resulting search tree by failing as soon as possible and thus achieving a shorter execution time.
7
Solution Presentation
For printing the achieved solution in text mode, the predicate draw grid( +Grid, +ColumnHints, +RowHints) was created. This predicate begins by obtaining the size of the largest sublist in RowHints when every element is printed with an additional space in front. This is done with the predicate largest sublist( +List, -Size) and allows the printing predicates to know how much horizontal spacing they must apply when printing the solutions. Afterwards, the column hints are drawn by first determining size of the largest sublist, allowing the predicate to know how many lines it will take to print all the hints, and printing each hint in the correct position. Finally, the grid is printed on the screen, along with the row hints, with ’X’s representing painted squares and spaces representing blank squares. Between each column and each row, as well as on the borders of the grid, a separator is drawn to accentuate the grid structure. Additionally, we allow the results to be saved to a file as sometimes, for very large puzzles, the display will not fit properly in the terminal. To do this, use the predicate hanjie solve to file(ColHints, RowHints, FilePath) where FilePath must
Hanjie Puzzle Solver
5
lead to a file that the program has permission to write in, or create in case it doesn’t exist.
Fig. 3. A solution to a Hanjie puzzle as viewed in text mode by the developed program.
8
Results
When testing our application with several examples of hanjie puzzles, we noticed it solved any puzzle with only one possible solution in under a second for puzzles with dimensions up to 80x80. Most of this time however was for preprocessing, as the labeling phase by itself takes less than 10 milliseconds for puzzles with dimensions up to 250x250. Concluding that there are no alternate solutions is also done in under a millisecond. For puzzles with dimensions greater than the previously indicated, the increase in execution time is linear relatively to the area of the puzzle grid.
Fig. 4. Execution time for solving a grid where every square is painted. Automatons generated for each row/column will be large and therefore require a larger pre-processing duration.
Fig. 5. Constraint programming specific statistics for solving a full grid. The adopted search strategy will lead to a large number of backtracks in this case as it tries smaller values first.
6
Hanjie Puzzle Solver
Fig. 6. Execution time for solving a grid where every square is blank. The chosen search strategy is ideal for this kind of puzzle as no backtracking will be required.
Fig. 7. Constraint programming specific statistics for solving an empty grid. The adopted search strategy will lead to no backtracks.
When the number of possible solutions increases however, the labeling time increases exponentially for finding the first solution. The labeling phase for other solutions that do not require the total number of painted squares in the row to be altered is processed in under a millisecond. Finding that there are no solutions left, or other solutions that do require a change in the total number of painted squares of a row, takes approximately the same time as finding the previous set of solutions.
Fig. 8. Execution time for solving a randomly generated grid which can have multiple solutions.
These results were obtained using an Intel(R) Core(TM) i7-2630QM CPU @ 2.00GHz 2.00GHz with 6,00 GB RAM.
Hanjie Puzzle Solver
7
Fig. 9. Constraint programming specific statistics for solving a randomly generated grid which can have multiple solutions.
9
Conclusions and Future Work
This project allowed us to understand the mechanics behind constraint logic programming studied during Logic Programming classes, by applying them to a logic program capable of solving the 2D puzzle, Hanjie. While trying to find a solution for this problem, the most complex part was developing the restrictions that would ensure the integrity and sequence of the painted squares. We quickly realized using strictly arithmetic restriction would create an overly complex solution and so decided to implement combinatorial constraints instead. More specifically, we implemented the automaton restriction since Hanjie is a puzzle of sequences in two dimensions. As the results we obtained show, what makes these puzzles computationally heavy to solve, are the number of possible solutions, and not the dimensions of the puzzle alone. Although larger dimensions, do allow for more possible solutions, once restraints have been applied, if there is only one possible solution, the labeling phase is quickly processed. It is therefore possible to solve a puzzle with dimensions 100x100 a lot faster than a 30x30 puzzle if the restraints leave a smaller search base for that puzzle. The implementation developed for this project will quickly solve any puzzles whose clues strongly restrict the elements of the rows/columns but will suffer an exponential growth in execution time with more ambiguous clues or puzzles with more than one solution. For puzzles with dimensions up to 30x30 however, it can usually solve them within 1-5 seconds. Additionally, it will always find a solution for a puzzle, provided it has any. If we had more time to work on this project, we would spend it analyzing the logic behind Hanjie, to be able to deduce more restrictions from the sets of clues that could be applied to our decision variables and help shorten execution time by reducing the resulting search base for possible solutions.
8
Hanjie Puzzle Solver
10
Bibliography
References
1. Russel, Stuart; Norvig, Peter: Artificial Intelligence: A Modern Approach. Pearson, New Jersey (2009) 2. Sterling, Lehon; Shapiro, Ehud: The Art of Prolog: Advanced Programming Techniques. The MIT Press, Massachusetts (1994) 3. FEUP - Logic Programming class support documentation, http://moodle.up.pt/ course/view.php?id=511 4. Description of Hanjie puzzles http://www.puzzlemix.com/Hanjie 5. Ullman, Jeffrey; Motwani, Rajeev; Hopcroft, John: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (2001) 6. Description of automaton and other combinatorial constraints available in SICStus Prolog 4.2.3 http://www.fi.muni.cz/~hanka/sicstus/doc/html/sicstus/ Combinatorial-Constraints.html
Hanjie Puzzle Solver
9
11
Annex A - Output to File Example
Fig. 10. The visualization of a text file created with this program.
10
Hanjie Puzzle Solver
12
Annex B - Code
’hanjie.pl’: :− use module ( l i b r a r y ( c l p f d ) ) . :− use module ( l i b r a r y ( l i s t s ) ) . ?− e n s u r e l o a d e d ( ’ h a n j i e e x a m p l e s . pl ’ ) . ?− e n s u r e l o a d e d ( ’ h a n j i e g e n e r a t i o n . pl ’ ) . % FOR EXAMPLES OF HANJIE PUZZLES, LOAD FILE ” hanjie examples . pl ” %p r e d i c a t e f o s o l v i n g h a n j i e p u z z l e s %i n i t i a l i z e s a g r i d ( l i s t o f l i s t s ) o f u n i n s t a n c i a t e d v a r i a b l e s with t h e a p r o p r i a t e s i z e f o r t h e s p e c i f i e d column and row h i n t s . %a h i n t must be a l i s t o f l i s t s where e v e r y s u b l i s t c o n t a i n s t h e s i z e and s e q u e n c e o f gray b l o c k s i n t h a t line %e . g . : [ [ 1 , 1 ] , [ 1 ] ] means t h e f i r s t l i n e must have two b l o c k s o f gray s q u a r e s with l e n g t h one and t h e s e c o n d l i n e must o n l y have one %t h e g r i d i s then f l a t t e n e d t o r e s t r i c t t h e domain o f t h e v a r i a b l e s to [ 0 , 1 ] . %a d d i t i o n a l c o n s t r a i n s a r e added with t h e p r e d i c a t e h a n j i e c o n s t r a i n t s /3 %a f t e r w a r d s , t h e l a b e l i n g /2 p r e d i c a t e i s used and t h e r e s u l t i n g g r i d i s drawn on s c r e e n % IMPORTANT: EVERY ROW/COLUMN MUST HAVE A HINT , EVEN IF IT IS 0 , OTHERWISE THE SIZE OF THE GRID WOULD HAVE TO BE INDICATED MANUALLY h a n j i e ( ColHints , RowHints ) :− l e n g t h ( ColHints , GridWidth ) , l e n g t h ( RowHints , GridHeight ) , m a k e g r i d ( S o l u t i o n , GridWidth , GridHeight ) , f l a t t e n ( S o l u t i o n , Vars ) , domain ( Vars , 0 , 1 ) , !, h a n j i e c o n s t r a i n t s ( ColHints , RowHints , S o l u t i o n ) , f l a t t e n ( ColHints , T o t a l C o l H i n t s ) , f l a t t e n ( RowHints , TotalRowHints ) , sum ( T o t a l C o l H i n t s , #=, TotalValue ) , sum ( TotalRowHints , #=, TotalValue ) , sum ( Vars , #=, TotalValue ) , l a b e l i n g ( [ f f ] , Vars ) ,
Hanjie Puzzle Solver
11
d r a w g r i d ( S o l u t i o n , ColHints , RowHints ) . %t h i s p r e d i c a t e a l l o w s t h e p u z z l e s o l u t i o n t o be s t o r e d i n a f i l e g i v e n by t h e s p e c i f i e d path h a n j i e s o l v e t o f i l e ( ColHints , RowHints , F i l e p a t h ) :− open ( F i l e p a t h , append , S1 ) , l e n g t h ( ColHints , GridWidth ) , l e n g t h ( RowHints , GridHeight ) , m a k e g r i d ( S o l u t i o n , GridWidth , GridHeight ) , f l a t t e n ( S o l u t i o n , Vars ) , domain ( Vars , 0 , 1 ) , !, h a n j i e c o n s t r a i n t s ( ColHints , RowHints , S o l u t i o n ) , f l a t t e n ( ColHints , T o t a l C o l H i n t s ) , f l a t t e n ( RowHints , TotalRowHints ) , sum ( T o t a l C o l H i n t s , #=, TotalValue ) , sum ( TotalRowHints , #=, TotalValue ) , sum ( Vars , #=, TotalValue ) , l a b e l i n g ( [ f f ] , Vars ) , d r a w g r i d ( S1 , S o l u t i o n , ColHints , RowHints ) , c l o s e ( S1 ) . %t h i s p r e d i c a t e w i l l g e n e r a t e a random h a n j i e p u z z l e and s o l v e i t by c a l l i n g h a n j i e g e n e r a t e and h a n j i e h a n j i e g e n e r a t e a n d s o l v e ( NumCols , NumRows) :− g e n e r a t e h a n j i e ( NumCols , NumRows, ColHints , RowHints ), !, h a n j i e ( ColHints , RowHints ) . %d o e s t h e same a s h a n j i e /2 but measures s t a t i s t i c s f o r c a l c u l a t i n g t h e s o l u t i o n i n s t e a d o f drawing t h e g r i d h a n j i e s t a t s ( ColHints , RowHints ) :− l e n g t h ( ColHints , GridWidth ) , l e n g t h ( RowHints , GridHeight ) , m a k e g r i d ( S o l u t i o n , GridWidth , GridHeight ) , f l a t t e n ( S o l u t i o n , Vars ) , domain ( Vars , 0 , 1 ) , !, p r i n t ( ’ dumping p r e v i o u s f d s t a t s : ’ ) , nl , fd statistics , s t a t i s t i c s ( w a l l t i m e , [ W0| ] ) , s t a t i s t i c s ( runtime , [ T0 | ] ) , h a n j i e c o n s t r a i n t s ( ColHints , RowHints , S o l u t i o n ) ,
12
Hanjie Puzzle Solver
f l a t t e n ( ColHints , T o t a l C o l H i n t s ) , f l a t t e n ( RowHints , TotalRowHints ) , sum ( T o t a l C o l H i n t s , #=, TotalValue ) , sum ( TotalRowHints , #=, TotalValue ) , sum ( Vars , #=, TotalValue ) , s t a t i s t i c s ( w a l l t i m e , [ W1| ] ) , s t a t i s t i c s ( runtime , [ T1 | ] ) , l a b e l i n g ( [ f f ] , Vars ) , s t a t i s t i c s ( w a l l t i m e , [ W2| ] ) , s t a t i s t i c s ( runtime , [ T2 | ] ) , T i s T1−T0 , W i s W1 −W0, Tl i s T2−T1 , Wl i s W2 −W1, nl , nl , nl , nl , nl , nl , nl , nl , nl , nl , nl , nl , nl , nl , nl , nl , format ( ’ c r e a t i n g c o n s t r a i n t s took CPU ˜3d s e c . ˜ n ’ , [T] ) , format ( ’ c r e a t i n g c o n s t r a i n t s took a t o t a l o f ˜3d s e c . ˜ n ’ , [W] ) , format ( ’ l a b e l i n g took CPU ˜3d s e c . ˜ n ’ , [ Tl ] ) , format ( ’ l a b e l i n g took a t o t a l o f ˜3d s e c . ˜ n ’ , [ Wl ]) , nl , fd statistics . %c r e a t e s t h e c o n s t r a i n s f o r each row o f t h e g r i d u s i n g r e s t r i c t r o w s /2 and t h e row h i n t s . %u s e s t h e p r e d i c a t e t r a n s p o s e /2 ( l i s t s l i b r a r y ) t o o b t a i n a l i s t o f t h e columns and c r e a t e s t h e c o n s t r a i n t s f o r %them a s w e l l , u s i n g r e s t r i c t r o w s /2 and t h e column h i n t s h a n j i e c o n s t r a i n t s ( ColHints , RowHints , Grid ) :− r e s t r i c t r o w s ( Grid , RowHints ) , t r a n s p o s e ( Grid , Columns ) , r e s t r i c t r o w s ( Columns , C o l H i n t s ) . %r e s t r i c t s t h e domain o f each e l e m e n t o f t h e g r i d by e n s u r i n g t h e sum o f a l l e l e m e n t s i s e q u a l t o t h e sum of the h i n t s %(0 c o r r e s p o n d s t o blank s q u a r e s and 1 c o r r e s p o n d s t o gray s q u a r e s o f t h e h a n j i e p u z z l e ) %t o e n s u r e t h e s e q u e n c e s o f c o l o r e d s q u a r e s a r e maintained , t h i s p r e d i c a t e c r e a t e s an automaton f o r each row restrict rows ( [ ] , [ ] ) . r e s t r i c t r o w s ( [ R| Rs ] , [ H| Hs ] ) :−
Hanjie Puzzle Solver
13
l e n g t h (R, MaxSum) , (%This ’ or ’ a l l o w s l i s t s t o be c o m p l e t e l y uninstantiated var (H) , HintLength i s f l o o r ( ( MaxSum+1) / 2 ) , l e n g t h (H, HintLength ) , c h e c k H i n t s (H, MaxSum) ; nonvar (H) , c h e c k H i n t s (H, MaxSum) ), RowSum #= MaxSum, < sum (H,#=,RowSum) , sum (R,#=,RowSum) , c r e a t e t r a n s i t i o n s (H, Arcs , s t a r t , F i n a l S t a t e , 1 ) , append (R, [ 0 ] , RowWithExtraZero ) , %a z e r o i s added t o s i m p l i f y t h e automaton ( e v e r y gray b l o c k must be f o l l o w e d by a t l e a s t one blank square , even t h e l a s t one ) automaton ( RowWithExtraZero , [ s o u r c e ( s t a r t ) , s i n k ( F i n a l S t a t e ) ] , [ a r c ( s t a r t , 0 , s t a r t ) | Arcs ] ) , r e s t r i c t r o w s ( Rs , Hs ) . %c h e c k s i f t h e h i n t s a r e v a r i a b l e s . I f so , t h e domain i s assigned to the v a r i a b l e checkHints ( [ ] , ) : −!. c h e c k H i n t s ( [ H| Hs ] , MaxSum) :− ( var (H) , domain ( [ H] , 0 , MaxSum) ; i n t e g e r (H) ) , c h e c k H i n t s ( Hs , MaxSum) . %t h i s p r e d i c a t e i s used t o g e n e r a t e t h e t r a n s i t i o n s ( a r c s ) between each s t a t e o f t h e automaton %i t g o e s through e v e r y v a l u e o f t h e Hint l i s t , d e c r e m e n t i n g them u n t i l they r e a c h 0 and c r e a t i n g mandatory t r a n s i t i o n s %t o e n s u r e c o n t i n u o u s gray b l o c k s . When t h e Hint r e a c h e s 0 i t c r e a t e s t r a n s i t i o n s t o e n s u r e a t l e a s t one blank b l o c k a f t e r t h e gray one %(t o a l l o w f o r 1 o r more w h i t e s q u a r e s a f t e r each gray blo ck , t h e automaton w i l l be an NFA) %i f t h e f i r s t s q u a r e o f a b l o c k has a h i n t with v a l u e 0 ( F i r s t S q u a r e = 1 ) , t h e CurState i s s e t a s N e x t S t a t e ( hint i s ignored ) c r e a t e t r a n s i t i o n s ( [ ] , [ ] , FinalState , FinalState , ) .
14
Hanjie Puzzle Solver
c r e a t e t r a n s i t i o n s ( [ Hint | Hs ] , T r a n s i t i o n s , CurState , F i n a l S t a t e , F i r s t S q u a r e ) :− ( Hint #= 0 , %f i n i s h e d c u r r e n t ’ gray ’ b l o c k s segment %’ gray ’ b l o c k s must be f o l l o w e d by AT LEAST ONE ’ blank ’ s q u a r e ( l o o p t o c u r r e n t s t a t e with ’ blank ’ b l o c k s ) %(an e x t r a ’ blank ’ s q u a r e was added t o end o f t h e row f o r t h e c a s e when t h e ’ gray ’ b l o c k ends at the grid ’ s border ) ( F i r s t S q u a r e =:=0 , T r a n s i t i o n s = [ a r c ( CurState , 0 , CurState ) , a r c ( CurState , 0 , N e x t S t a t e ) | Ts ] , c r e a t e t r a n s i t i o n s ( Hs , Ts , NextState , FinalState , 1 ) ; F i r s t S q u a r e =:=1 , T r a n s i t i o n s = [ a r c ( CurState , 0 , CurState ) ] , c r e a t e t r a n s i t i o n s ( Hs , Ts , CurState , FinalState , 1 ) ) ; %i n t h i s c a s e , we aren ’ t f i n i s h e d with t h e gray b l o c k y e t and a s such need more ’ gray ’ s q u a r e s t o advance Hint # 0 , > T r a n s i t i o n s = [ a r c ( CurState , 1 , N e x t S t a t e ) | Ts ] , NewHint #= Hint −1, c r e a t e t r a n s i t i o n s ( [ NewHint | Hs ] , Ts , NextState , FinalState , 0 ) ) .
%−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− UTILITIES −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− %f l a t t e n s a l i s t o f l i s t s i n t o a s i n g l e l i s t flatten ( [ ] , [ ] ) : −!. f l a t t e n ( [ [ ] | Gs ] , Fg ) :− !, f l a t t e n ( Gs , Fg ) . f l a t t e n ( [ [ G1 | G1s ] | Gs ] , [ G1 | Fg ] ) :− f l a t t e n ( [ G1s | Gs ] , Fg ) .
Hanjie Puzzle Solver
15
%t h i s p r e d i c a t e i s used t o c r e a t e a g r i d ( l i s t o f l i s t s ) o f u n i n s t a n c i a t e d v a r i a b l e s with t h e s p e c i f i e d dimensions m a k e g r i d ( Grid , Width , Height ) :− l e n g t h ( Grid , Height ) , make rows ( Grid , Width ) . make rows ( [ ] , ) : − ! . make rows ( [G| Gs ] , Width ) :− l e n g t h (G, Width ) , make rows ( Gs , Width ) . %t h i s p r e d i c a t e i s used t o d e t e r m i n e t h e s i z e o f t h e l a r g e s t s u b l i s t in a l i s t of l i s t s l a r g e s t s u b l i s t ( [ ] , 0 ) : −!. l a r g e s t s u b l i s t ( [ L | Ls ] ,N) :− l a r g e s t s u b l i s t ( Ls ,M1) , l e n g t h (L ,M2) , (M1 > M2, N i s M1; N i s M2) , !. %−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−END UTILITIES −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
%−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−DISPLAY PREDICATES −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− %p r e d i c a t e s f o r drawing t h e h a n j i e ’ s p u z z l e g r i d sign (0 , ’ ’) . s i g n ( 1 , ’X’ ) . d r a w g r i d ( [ B | Bs ] , ColHints , RowHints ) :− l a r g e s t s u b l i s t ( RowHints , HChars ) , HSpacing i s HChars ∗ 2 , nl , nl , HSpacingForCols i s HSpacing +1, d r a w c o l u m n h i n t s ( ColHints , HSpacingForCols ) , l e n g t h (B,N) , putChars ( ’ ’ , HSpacing ) , p r i n t ( ’ | ’ ) , p r i n t s e p a r a t o r (N, ’ − ’ ) , pg ( [ B | Bs ] , RowHints , HSpacing ) , putChars ( ’ ’ , HSpacing ) , p r i n t ( ’ | ’ ) , p r i n t s e p a r a t o r (N, ’ − ’ ) , n l . pg ( [ B ] , [RH] , HLength ) :−
16
Hanjie Puzzle Solver
d r a w r o w h i n t s (RH, HLength ) , p r i n t l i n e (B) , ! . pg ( [ B | Bs ] , [RH| RHs ] , HLength ) :− d r a w r o w h i n t s (RH, HLength ) , p r i n t l i n e (B) , l e n g t h (B,N) , putChars ( ’ ’ , HLength ) , print ( ’| ’) , p r i n t s e p a r a t o r (N, ’ + ’ ) , pg ( Bs , RHs , HLength ) . p r i n t l i n e ( [ ] ) :− print ( ’ | ’ ) , nl . p r i n t l i n e ( [ L | Ls ] ) :− s i g n (L , Symbol ) , print ( ’| ’) , p r i n t ( Symbol ) , p r i n t l i n e ( Ls ) . p r i n t s e p a r a t o r ( 1 , ) :− p r i n t ( ’ − | ’ ) , n l . p r i n t s e p a r a t o r (N, MidChar ) :− N > 1, N1 i s N−1, p r i n t ( ’ − ’) , p r i n t ( MidChar ) , p r i n t s e p a r a t o r (N1 , MidChar ) . putChars ( , 0 ) : − ! . putChars ( Char ,N) :− N > 0, N1 i s N−1, p r i n t ( Char ) , putChars ( Char , N1) . d r a w c o l u m n h i n t s ( ColHints , HSpacing ) :− l a r g e s t s u b l i s t ( ColHints , VSpacing ) , dch ( ColHints , HSpacing , VSpacing ) . dch ( , , 0 ) : − ! . dch ( ColHints , HSpacing , VSpacing ) :− VSpacing > 0 , putChars ( ’ ’ , HSpacing ) , d r a w e l e m e n t s a t v p o s ( ColHints , VSpacing ) , nl , NewVSpacing i s VSpacing −1, dch ( ColHints , HSpacing , NewVSpacing ) . draw elements at vpos ( [ ] , ) : −!. d r a w e l e m e n t s a t v p o s ( [CH| CHs ] , VSpacing ) :− l e n g t h (CH, NumHints ) , ( NumHints < VSpacing , ! ,
Hanjie Puzzle Solver
17
print ( ’ ’) ; ElementPos i s NumHints−VSpacing , nth0 ( ElementPos ,CH, Value ) , ( Value < 1 0 , ! , p r i n t ( Value ) ; p r i n t ( ’# ’) ) , print ( ’ ’) ) , d r a w e l e m e n t s a t v p o s (CHs , VSpacing ) . draw row hints ( [ ] , ) : −!. d r a w r o w h i n t s ( [ R| Rs ] , HSize ) :− HSize >0, l e n g t h ( [ R| Rs ] , L) , ( HSize > L ∗ 2 , ! , NewHSize i s HSize −2, print ( ’ ’) , d r a w r o w h i n t s ( [ R| Rs ] , NewHSize ) ; NewHSize i s HSize −2, (R< 1 0 , ! , p r i n t (R) , p r i n t ( ’ ’ ) ; p r i n t ( ’# ’ ) ) , d r a w r o w h i n t s ( Rs , NewHSize ) ) . %−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−END DISPLAY PREDICATES −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− %−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−FILE I /O PREDICATES −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− %p r e d i c a t e s f o r drawing t h e h a n j i e ’ s p u z z l e g r i d i n a file d r a w g r i d ( Stream , [ B | Bs ] , ColHints , RowHints ) :− l a r g e s t s u b l i s t ( RowHints , HChars ) , HSpacing i s HChars ∗ 2 , w r i t e ( Stream , ’ \ n\n ’ ) , HSpacingForCols i s HSpacing +1, d r a w c o l u m n h i n t s ( Stream , ColHints , HSpacingForCols ) , l e n g t h (B,N) , putChars ( Stream , ’ ’ , HSpacing ) , w r i t e ( Stream , ’ | ’ ) , p r i n t s e p a r a t o r ( Stream , N, ’ − ’ ) , pg ( Stream , [ B | Bs ] , RowHints , HSpacing ) , putChars ( Stream , ’ ’ , HSpacing ) ,
18
Hanjie Puzzle Solver
w r i t e ( Stream , ’ | ’ ) , p r i n t s e p a r a t o r ( Stream , N, ’ − ’ ) , w r i t e ( Stream , ’ \ n ’ ) . pg ( Stream , [ B ] , [RH] , HLength ) :− d r a w r o w h i n t s ( Stream ,RH, HLength ) , p r i n t l i n e ( Stream , B) , ! . pg ( Stream , [ B | Bs ] , [RH| RHs ] , HLength ) :− d r a w r o w h i n t s ( Stream ,RH, HLength ) , p r i n t l i n e ( Stream , B) , l e n g t h (B,N) , putChars ( Stream , ’ ’ , HLength ) , w r i t e ( Stream , ’ | ’ ) , p r i n t s e p a r a t o r ( Stream , N, ’ + ’ ) , pg ( Stream , Bs , RHs , HLength ) . p r i n t l i n e ( Stream , [ ] ) :− w r i t e ( Stream , ’ | \ n ’ ) . p r i n t l i n e ( Stream , [ L | Ls ] ) :− s i g n (L , Symbol ) , w r i t e ( Stream , ’ | ’ ) , w r i t e ( Stream , Symbol ) , p r i n t l i n e ( Stream , Ls ) . p r i n t s e p a r a t o r ( Stream , 1 , ) :− w r i t e ( Stream , ’ − | ’ ) , w r i t e ( Stream , ’ \ n ’ ) . p r i n t s e p a r a t o r ( Stream , N, MidChar ) :− N > 1, N1 i s N−1, w r i t e ( Stream , ’ − ’ ) , w r i t e ( Stream , MidChar ) , p r i n t s e p a r a t o r ( Stream , N1 , MidChar ) . putChars ( , , 0 ) : − ! . putChars ( Stream , Char ,N) :− N > 0, N1 i s N−1, w r i t e ( Stream , Char ) , putChars ( Stream , Char , N1) . d r a w c o l u m n h i n t s ( Stream , ColHints , HSpacing ) :− l a r g e s t s u b l i s t ( ColHints , VSpacing ) , dch ( Stream , ColHints , HSpacing , VSpacing ) . dch ( , , , 0 ) : − ! . dch ( Stream , ColHints , HSpacing , VSpacing ) :− VSpacing > 0 , putChars ( Stream , ’ ’ , HSpacing ) , d r a w e l e m e n t s a t v p o s ( Stream , ColHints , VSpacing ) , w r i t e ( Stream , ’ \ n ’ ) , NewVSpacing i s VSpacing −1,
Hanjie Puzzle Solver
19
dch ( Stream , ColHints , HSpacing , NewVSpacing ) . draw elements at vpos ( , [ ] , ) : −!. d r a w e l e m e n t s a t v p o s ( Stream , [ CH| CHs ] , VSpacing ) :− l e n g t h (CH, NumHints ) , ( NumHints < VSpacing , ! , w r i t e ( Stream , ’ ’) ; ElementPos i s NumHints−VSpacing , nth0 ( ElementPos ,CH, Value ) , ( Value < 1 0 , ! , w r i t e ( Stream , Value ) ; w r i t e ( Stream , ’ # ’ ) ) , w r i t e ( Stream , ’ ’ ) ) , d r a w e l e m e n t s a t v p o s ( Stream , CHs , VSpacing ) . draw row hints ( , [ ] , ) : −!. d r a w r o w h i n t s ( Stream , [ R| Rs ] , HSize ) :− HSize >0, l e n g t h ( [ R| Rs ] , L) , ( HSize > L ∗ 2 , ! , NewHSize i s HSize −2, w r i t e ( Stream , ’ ’) , d r a w r o w h i n t s ( Stream , [ R| Rs ] , NewHSize ) ; NewHSize i s HSize −2, (R< 1 0 , ! , w r i t e ( Stream ,R) , w r i t e ( Stream , ’ ’ ) ; w r i t e ( Stream , ’# ’ ) ) , d r a w r o w h i n t s ( Stream , Rs , NewHSize ) ) . %−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−END DISPLAY PREDICATES −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
2] , [3 , 8 , 7 , 2] , [26] , [34] , [34] , [34] , [34] , [34] , [24] , [5 , 3 , 5] , [3 , 5 , 3 , 5] , [2 , 2 , 24] , [1 , 1 , 24] , [2 , 2 9 ] , [ 5 , 24 , 2 ] , [ 3 , 26 , 2 ] , [ 4 1 , 3 ] , [43 , 2] , [42 , 3] , [41 , 2] , [41 , 2] , [4 , 2 , 2 , 2 , 2 , 5] , [42] , [42] , [42] , [64] , [86] , [83] , [65] , [75] , [71] , [ 6 0 , 1 0 ] , [ 6 , 53 , 1 0 ] , [ 6 , 25 , 24 , 1 0 ] , [ 1 9 , 17 , 3 , 4 4 ] , [ 3 0 , 12 , 4 0 ] , [ 1 2 , 19 , 2 2 ] , [ 9 , 24 , 1 6 ] , [ 4 , 20 , 8 , 1 1 ] , [ 5 , 24 , 6 , 2 , 3 ] , [ 3 8 , 6 , 2 , 6 ] , [45 , 8 , 8] , [52 , 3] , [51 , 1] , [51 , 2] , [50 , 1] , [50 , 1] , [50 , 1] , [34 , 9 , 2 ] , [ 3 1 , 6 , 7 , 7 , 1 ] , [ 2 9 , 10 , 6 , 3 , 5 , 1] , [27 , 8 , 5 , 5 , 3 , 1] , [25 , 5 , 5 , 4 , 10 , 5 , 2 ] , [ 2 3 , 3 , 11 , 2 , 3 , 3 , 5 , 1 ] , [ 2 0 , 3 , 16 , 2 , 8 , 11 , 1 ] , [ 1 8 , 2 , 8 , 4 , 1 , 9 , 3 , 7 , 2] , [15 , 4 , 8 , 5 , 4 , 12 , 5 , 9 , 1 ] , [ 1 1 , 5 , 7 , 8 , 2 , 14 , 5 , 11 , 1 ] , [ 7 , 7 , 6 , 13 , 9 , 15 , 1 5 ] ] ) . %t h e f o l l o w i n g examples a l l o w f o r m u l t i p l e s o l u t i o n s ( c l u e s t o be d e t e r m i n e d ) ], example i 1 ( [ , [ , ]) . example i 2 ( [ , , ], [ , , ]) . example i 3 ( [ [ 1 , 1] , [ ] , [1 , 1 ] ] , [ [ 1 , 1] , [ ] , [1 , 1 ] ] ) . %l a r g e amounts o f c o m p l e t e l y u n i n s t a n t i a t e d l i s t s ( number o f h i n t s p e r row w i l l be maximum) w i l l p o s s i b l y t a k e l o n g t o compute example i 4 ( [ , , , , , , , , , , , , , , ], , , , , , , , , , [ , , , , , ]) . example i 5 ( [ [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , [ ]] , [[ ] , [ ] , [ ] , [ ] , [ ] , [ ] , [ ], [ ], [ ], [ ], [ ], [ ], [ ] , [ ] , [ ]]) .
Hanjie Puzzle Solver
23
’hanjie generation.pl’: :− use module ( l i b r a r y ( l i s t s ) ) . :− use module ( l i b r a r y ( random ) ) . ?− e n s u r e l o a d e d ( ’ h a n j i e . pl ’ ) .
%t h i s p r e d i c a t e w i l l c r e a t e a random h a n j i e g r i d and obtain the c l u e s f o r generated s o l u t i o n s g e n e r a t e h a n j i e ( Width , Height , ColHints , RowHints ) :− make atom grid ( PuzzleGrid , Width , Height ) , g e n e r a t e r o w s h i n t s ( PuzzleGrid ,RH) , t r a n s p o s e ( PuzzleGrid , C o l s ) , g e n e r a t e r o w s h i n t s ( Cols ,CH) , s t r i p z e r o s (RH, RowHints ) , s t r i p z e r o s (CH, C o l H i n t s ) , nl , nl , nl , p r i n t ( ’ This i s a p o s s i b l e s o l u t i o n ( t h e l a r g e r t h e g r i d t h e more l i k e l y i t w i l l have m u l t i p l e s o l u t i o n s ) : ’ ) , nl , d r a w g r i d ( PuzzleGrid , ColHints , RowHints ) . %t h i s p r e d i c a t e w i l l c r e a t e a h a n j i e g r i d with a l l squares painted g e n e r a t e h a n j i e f u l l ( Width , Height , ColHints , RowHints ) :− m a k e a t o m g r i d f u l l ( PuzzleGrid , Width , Height ) , g e n e r a t e r o w s h i n t s ( PuzzleGrid ,RH) , t r a n s p o s e ( PuzzleGrid , C o l s ) , g e n e r a t e r o w s h i n t s ( Cols ,CH) , s t r i p z e r o s (RH, RowHints ) , s t r i p z e r o s (CH, C o l H i n t s ) . %t h i s p r e d i c a t e w i l l c r e a t e a h a n j i e g r i d with a l l s q u a r e s blank g e n e r a t e h a n j i e e m p t y ( Width , Height , ColHints , RowHints ) :− make atom grid empty ( PuzzleGrid , Width , Height ) , g e n e r a t e r o w s h i n t s ( PuzzleGrid ,RH) , t r a n s p o s e ( PuzzleGrid , C o l s ) , g e n e r a t e r o w s h i n t s ( Cols ,CH) , s t r i p z e r o s (RH, RowHints ) , s t r i p z e r o s (CH, C o l H i n t s ) . s t r i p z e r o s ( [ ] , [ ] ) : −!. s t r i p z e r o s ( [ Row | Rest ] , [ R e s u l t | Rs ] ) :− d e l e t e (Row, 0 , Temp) ,
24
Hanjie Puzzle Solver
(Temp = [ ] , Result = [ 0 ] ; R e s u l t=Temp) , ! , s t r i p z e r o s ( Rest , Rs ) . generate rows hints ( [ ] , [ ] ) : −!. g e n e r a t e r o w s h i n t s ( [ Row | Rest ] , [RH| RHs ] ) :− g e n e r a t e h i n t s f o r r o w (Row,RH) , g e n e r a t e r o w s h i n t s ( Rest , RHs) . generate hints for row ( [ ] , [ 0 ] ) : −!. g e n e r a t e h i n t s f o r r o w ( [ 0 | Rest ] , [ 0 | RHs ] ) :− g e n e r a t e h i n t s f o r r o w ( Rest , RHs) . g e n e r a t e h i n t s f o r r o w ( [ 1 | Rest ] , [ Head | RHs ] ) :− g e n e r a t e h i n t s f o r r o w ( Rest , [ NextHead | RHs ] ) , Head i s NextHead +1.
make atom grid empty ( [ ] , , 0 ) : − ! . make atom grid empty ( [ Row | Rest ] , Width , Height ) :− Height > 0 , make atom row empty (Row, Width ) , RemainingHeight i s Height −1, make atom grid empty ( Rest , Width , RemainingHeight ) . make atom row empty ( [ ] , 0 ) : − ! . make atom row empty ( [ 0 | Rs ] , Width ) :− Width > 0 , RemainingWidth i s Width −1, make atom row empty ( Rs , RemainingWidth ) . make atom grid full ( [ ] , ,0) : −!. m a k e a t o m g r i d f u l l ( [ Row | Rest ] , Width , Height ) :− Height > 0 , m a k e a t o m r o w f u l l (Row, Width ) , RemainingHeight i s Height −1, m a k e a t o m g r i d f u l l ( Rest , Width , RemainingHeight ) . make atom row full ( [ ] , 0 ) : −!. m a k e a t o m r o w f u l l ( [ 1 | Rs ] , Width ) :− Width > 0 , RemainingWidth i s Width −1, m a k e a t o m r o w f u l l ( Rs , RemainingWidth ) . make atom grid ( [ ] , , 0 ) : − ! .
Hanjie Puzzle Solver
25
make atom grid ( [ Row | Rest ] , Width , Height ) :− Height > 0 , make atom row (Row, Width ) , RemainingHeight i s Height −1, make atom grid ( Rest , Width , RemainingHeight ) . make atom row ( [ ] , 0 ) : − ! . make atom row ( [ R| Rs ] , Width ) :− Width > 0 , random ( 0 , 2 ,R) , RemainingWidth i s Width −1, make atom row ( Rs , RemainingWidth ) .
