PROLOG PROGRAM FOR BLOCK WORLD PROBLEM PLUS

Otherwise the program may cycle forever (depending on how it hits the move/2 move-generating predicate. You have to check on each state expansion whether a new state might already be on the path. In fact, you construct the path through state path on return only in the third argument here: path(X,Y,).

PROLOG PROGRAM FOR BLOCK WORLD PROBLEM PLUS

(Additionally, the solution you give is not a reachable state, the second line has a void on a wrong position, plus the path is reversed). Failure to test whether a state has already been visited.Depth first search through state space.Other improvements: Use a list to represent the stack, this makes the state much more appealing.ġ That's the year Prolog was discovered/conceived/delivered. Rather stick to your highly clean style and rather do more querying instead! That is what Prolog is excellent at! Yes, I could have improved it somewhat, say by using path/4, but not by much. Note that I did not dare to touch your clean code. OK, one heuristics would be the term size of a solution. You would need to inform the program what kind of preference you have. So if we are exploring this set, where shall we start? What does it mean to be the best solution? The one that when uploaded on Utube produces the most upvotes? So what we are doing here is completely uninformed search. Or, see it from another angle: The set of solutions for X is pretty large. These are all fundamental questions, but they are independent of the programming problem as such. Shouldn't it be finite? And: Is it possible to rule out such long paths for such trivial problems? Any toddler can keep the search space small. How far can you get with this formulation? Currently, I found a path of length 48. Oh yes, there are! Now it does make sense to rule out such paths. Are there really any cycles? Let's ask that first:Į = state(void,on(c,void),on(a,on(b,void))) Now, is this really the best way to ask? After all, many of the answers might be simple cycles, putting a block into one place and back again. And out of a sudden Prolog answered with a shorter answer than you expected! See what I did? I only added length(X, N) in front. Path( state(on(c,on(b,on(a,void))), void, void), OK, so let's try out any length! Also this is something Prolog loves. How long shall that list be? We know not (that is, I don't). Instead of asking for a concrete answer which demands from your Prolog system quite a bit of ingenuity, let's formulate your answer as a query! I tried it and realized that you have some nasty syntax errors in them, and after that, the query failed.īut there is a cheaper way! Let's just limit the length of the list and let Prolog fill out the rest. Instead, you can reformulate your queries sparingly. State(on(c,on(b,on(a,void))), void, void)].įor a first test, there is no need to rewrite your code. State(void, on(c,void), on(void(a,on(b,void))), I got ERROR: Out of local stack, but I want that that X would be X=[state(void, void, on(c,on(a,on(b,void)))), The problem is that the predicate path doesn't work as I want, i.e., if I type path(state(on(c,on(b,on(a,void))), void, void), state(void, void, on(c,on(a,on(b,void)))), X). Where move give us the possible movements that you can use and path should give us the path that you have to take from X to Y. Move(state(X, OldY, on(Z, NewZ)), state(X, on(Z, OldY), NewZ)). Move(state(OldX, Y, on(Z, NewZ)), state(on(Z, OldX), Y, NewZ)). Move(state(X, on(Y, NewY), OldZ), state(X, NewY, on(Y, OldZ))). Move(state(OldX, on(Y, NewY), Z), state(on(Y, OldX), NewY, Z)). Move(state(on(X, NewX), Y, OldZ), state(NewX, Y, on(X, OldZ))). I have the following code: move(state(on(X, NewX), OldY, Z), state(NewX, on(X, OldY), Z)).

Prolog program for block world problem