Solving a puzzle using swi-prolog

Question

I've been given as an assignment to write using prolog a solver for the battleships solitaire puzzle. To those unfamiliar, the puzzle deals with a 6 by 6 grid on which a series of ships are placed according to the provided constraints on each row and column, i.e. the first row must contain 3 squares with ships, the second row must contain 1 square with a ship, the third row must contain 0 squares etc for the other rows and columns.

Each puzzle comes with it's own set of constraints and revealed squares, typically two. An example can be seen here: battleships

So, here's what I've done:

step([ShipCount,Rows,Cols,Tiles],[ShipCount2,Rows2,Cols2,Tiles2]):-
   ShipCount2 is ShipCount+1,
   nth1(X,Cols,X1),
   X1\==0,
   nth1(Y,Rows,Y1),
   Y1\==0,
   not(member([X,Y,_],Tiles)),
       pairs(Tiles,TilesXY),
   notdiaglist(X,Y,TilesXY),
   member(T,[1,2,3,4,5,6]),
   append([X,Y],[T],Tile),
   append([Tile],Tiles,Tiles2),
   dec_elem1(X,Cols,Cols2),dec_elem1(Y,Rows,Rows2).


dec_elem1(1,[A|Tail],[B|Tail]):- B is A-1.
dec_elem1(Count,[A|Tail],[A|Tail2]):- Count1 is Count-1,dec_elem1(Count1,Tail,Tail2).

neib(X1,Y1,X2,Y2) :- X2 is X1,(Y2 is Y1 -1;Y2 is Y1+1; Y2 is Y1).
neib(X1,Y1,X2,Y2) :- X2 is X1-1,(Y2 is Y1 -1;Y2 is Y1+1; Y2 is Y1).
neib(X1,Y1,X2,Y2) :- X2 is X1+1,(Y2 is Y1 -1;Y2 is Y1+1; Y2 is Y1).

notdiag(X1,Y1,X2,Y2) :- not(neib(X1,Y1,X2,Y2)).
notdiag(X1,Y1,X2,Y2) :- neib(X1,Y1,X2,Y2),((X1 == X2,t(Y1,Y2));(Y1 == Y2,t(X1,X2))). 
notdiaglist(X1,Y1,[]).
notdiaglist(X1,Y1,[[X2,Y2]|Tail]):-notdiag(X1,Y1,X2,Y2),notdiaglist(X1,Y1,Tail).

t(X1,X2):- X is abs(X1-X2), X==1.

pairs([],[]).
pairs([[X,Y,Z]|Tail],[[X,Y]|Tail2]):-pairs(Tail,Tail2).

I represent a state with a list: [Count,Rows,Columns,Tiles]. The last state must be [10,[0,0,0,0,0,0],[0,0,0,0,0,0], somelist]. A puzzle starts from an initial state, for example

initial([1, [1,3,1,1,1,2] , [0,2,2,0,0,5] , [[4,4,1],[2,1,0]]]).

I try to find a solution in the following manner:

run:-initial(S),step(S,S1),step(S1,S2),....,step(S8,F).

Now, here's the difficulty: if i restrict myself to one type of ship parts by using member(T,[1])

instead of

member(T,[1,2,3,4,5,6])

it works fine. However, when I use the full range of possible values for T which are needed later, the query never ends since it runs for too long. this puzzles me, since :

(a) it works for 6 types of ships but only for 8 steps instead of 9
(b) going from a single type of ship to 6 types increases the number of options for just the last step by a factor of 6, which shouldn't have such a dramatic effect.

So, what's going on?

The head of the last clause in notdiaglist should probably be notdiaglist(X1, Y1, [[X2, Y2, _] | Tail]), no? step fails very quickly otherwise. I'm also getting a failure for nine iterations of step no matter what options for T there are. It takes a long time (48s) and it fails. — jgriego
Hi, thanks for your answer. 1. the last clause in notdiaglist should not be x2,y2,_ because the list it expects is a list of 2d-points. I use two list types: 2d points and "3d" points - 2d coordinates + ship type 2. strange that you're getting a failure. my query doesn't end at all. what version of swi-prolog do you use? — Dani
EDIT: I've changed the code a bit because you're right- I doesn't work as is. I've added a a predicate "pairs" to convert from "3d" points to 2d points. I apologize, I wasn't careful when pasting from the editor. — Dani

jgriego jgriego · Accepted Answer · 2014-05-09T07:02:25

To answer your question directly, what's going on is that Prolog is trying to sift through an enormous space of possibilities.

You're correct that altering that line increases the search space of the last call by a factor of six, note that the size of the search space of, say, nine calls, isn't proportional to 9 times the size of one call. Prolog will backtrack on failure, so it's proportional (bounded above, actually) to the size of the possible results of one call raised to the ninth power.

That means we can expect the size of the space Prolog needs to search to grow by at most a factor of 6^9 = 10077696 when we allow T to take on 6 times as many values.

Of course, it doesn't help that (as far as I was able to tell) a solution doesn't exist if we call step 9 times starting with initial anyways. Since that last call is going to fail, Prolog will keep trying until it's exhausted all possibilities (of which there are a great many) before it finally gives up.

As far as a solution goes, I'm not sure I know enough about the problem. If the value if T is the kind of ship that fits in the grid (e.g. single square, half of a 2-square-ship, part of a 3-square-ship) you should note that that gives you a lot more information than the numbers on the rows/columns.

Right now, in pseudocode, your step looks like this:

Find a (X,Y) pair that has non-zero markings on its row/column
Check that there isn't already a ship there
Check that it isn't diagonal to a ship
Pick a kind of ship-part for it to be.

I'd suggest you approach like this:

Finish any already placed ship-bits to form complete ships (if we can't: fail)
Until we're finished:
- Find acceptable places to place ship
- Check that the markings on the row/column aren't zero
- Try to place an entire ship here. (instead of a single part)

By using the most specific information that we have first (in this case, the previously placed parts), we can reduce the amount of work Prolog has to do and make things return reasonably fast.

Solving a puzzle using swi-prolog

1 Answers