Solving jigsaw puzzle with restriction in prolog

Question

I am starting to learn restrictions in prolog at the moment using SICStus Prolog. Though I know how solve simpe problems using this, I have one exercise where I must solve a Jigsaw puzzle. However I have no idea how to solve this since I will have several different elements with different proprieties (pieces) , can anyone give me an example of how to make represent a list of piece in prolog and what kind of restrictions should I use?

Answer 1

For a first try, I would do something along these lines:

For each field, use 5 variables. The first variable denotes the puzzle piece that goes into the field. Each piece has its own id. In the case of the puzzle that you mentioned in your comment above there are 12 pieces, so each variable would have a domain of {1..12}:

P #:: 1..12,

The other four variables denote the four edges of each field, and whether the puzzle piece placed in the field has a dent or tab there. In your puzzle, each "up" or "down" side has a tab and a dent, so you denote whether the tab is left or right. Again, boolean decision variables.

[EL,EU,ER,ED] #:: 0..1,

A puzzle piece can the be encoded like this:

piece(1,  [](0,1,1,0)).

This for instance is piece A in the description of your puzzle on the website that you gave in the comment.

Now you can define the neighbour relation between two adjacent fields. Since you have boolean variables, and a tab needs to meet a dent, you set a constraint (not "restriction") requiring that the sum be one:

R1 + L2 #= 1,

I.e., the right edge of the piece in field one must match the left edge of the piece in field 2.

You also set similar constraints for the edges along the borders.

The you set a constraint requiring that all fields must contain different pieces:

alldifferent(Fields),

(where Fields is the list containing the P variables)

You need a variable that denotes the orientation of the puzzle pieces:

O #:: 0..1,

You need just one, since in your puzzle, all pieces must be orientated in the same direction.

Finally, you need constraints that combine the piece, orientation and edge variables for each field, so that when you select a piece for a field (and the orientation is known) you can set the edge variables appropriately:

 once(piece(N, [](L,U,V,D))),
 ( ((P#=N) #/\ (O#=0)) #=> ((EL#=L) #/\ (EU#=  U) #/\ (ER#=R) #/\ (ED#=  D)) ),
 ( ((P#=N) #/\ (O#=1)) #=> ((EL#=R) #/\ (EU#=1-D) #/\ (ER#=L) #/\ (ED#=1-U)) ),

(the syntax is not for Sicstus, but ECLiPSe. The FD constraint libraries should be similar enough, though)

Note that I had to invert the encoding for the down edge when turning a piece upside-down. This is allowed me to keep the "sum equals one" constraints for up/down edges, but is sub-optimal, since it prevented me from easily propagating information from the edge variables to the piece variables (a piece may get the same encoding as another when turned upside down). But I was too lazy to change the encoding for this first try.

(Edit:this should be easy to fix by inverting the encoding for the down edge, e.g.: piece(1, [](0,1,1,1))., and using constraints that require up and down edges of neighbouring pieces to have the same value instead of having sum one.)

Throwing all together and simply labeling the P variables (after instantiating the orientation variable first) gives the two solutions:

?- rapids(S,O).
S = []([](5, 2, 8, 6), [](11, 10, 1, 4), [](3, 9, 12, 7))
O = 0
Yes (0.01s cpu, solution 1, maybe more)
S = []([](5, 3, 11, 12), [](8, 9, 7, 4), [](2, 10, 6, 1))
O = 1
Yes (0.04s cpu, solution 2, maybe more)
No (0.05s cpu)

I used matrices instead of lists, in order to make the rows of the puzzle field more prominent. Matrices also allow faster access to neighbouring fields in different rows.