Prolog Code for 8-puzzle Problem using BFS(breath first search)

[Tharushi Geethma]

I'm new to prolog. I need yor kind support regarding the following problm.

Given a start state and the end state of the puzzle, the prolog program should be able to print all the moves using BFS(breadth first search). For example, 


1 3 2		1 2 3
4 6 5	->->	4 5 6 
7 x 8		7 8 x

x is the empty tile. The other tiles should be moved up, down, right and left using the empty tile(x),and the final state should be arrived.
As the output, all the moves should be printed.

Thank you very much

[Kuniaki Mukai]

Hi,

This comment  may be not useful for you, but here 

is an old  cgi of mine in prolog ( around 1995 ) for N-puzzle, 

which is in Japanese, sorry.

http://web.sfc.keio.ac.jp/~mukai/paccgi7/npuzzle.html

It  finds only one solution when it is solvable, otherwise it terminates with “unsolvable” message.

IMHO,  the enumerating all “solutions" for N-puzzle in BFS sounds very hard. 

However  your  case for N = 3 could be solved by a simple  brute force, 

though I have no idea for now how to  write such codes.  

Sorry for  this useless comment,  but  nevertheless, 

 I hope  you can find a way through.

Good luck, 

K.M.

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.
Visit this group at https://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

[Paulo Moura]

See:

https://github.com/LogtalkDotOrg/logtalk3/tree/master/examples/searching

The solution for the 8-puzzle is coded in the eight_puzzle.lgt file.

-----------------------------------------------------------------
Paulo Moura
Logtalk developer

[Barb Knox]

On 5/01/2019, at 21:01, Kuniaki Mukai <kuniak...@gmail.com> wrote:

[...]

IMHO,  the enumerating all “solutions" for N-puzzle in BFS sounds very hard. 

[...]

The OP is not asking for all solutions, but for all the *moves* of (presumably) a shortest solution (the first one found by a BFS).

Finding all the solutions is impossible, since with repeated states there are unlimited solutions.  Finding all non-repeating solutions is doable, but that doesn't seem to be what is requested.

If BFS is only a tool for finding a shortest solution and not a requirement of the homework assignment then you should consider an "iterative deepening" DFS, which is much easier to code in Prolog than a BFS (unless you already have a library that takes care of all the BFS admin).

And for a hint, definitely separate the code for finding a solution from the code for printing all its moves.  You need some representation for a solution (or solution-so-far); a simple one is just an ordered list of  u,d,l,r tracking the movements of the "x", but there are others that might be more suitable for your purposes.

(And IMO, this is rather too difficult a problem for an average beginner.)

On Jan 5, 2019, at 13:51, Tharushi Geethma <tharushi...@gmail.com> wrote:

I'm new to prolog. I need yor kind support regarding the following problm.

Given a start state and the end state of the puzzle, the prolog program should

 be able to print all the moves using BFS (breadth first search). For example, 

1 3 2		1 2 3
4 6 5	->->	4 5 6 
7 x 8		7 8 x

x is the empty tile. The other tiles should be moved up, down, right and left using the empty tile(x),and the final state should be arrived.
As the output, all the moves should be printed.

Thank you very much

-- 

---------------------------
|  BBB                b    \    Barbara at LivingHistory stop co stop uk
|  B  B   aa     rrr  b     |
|  BBB   a  a   r     bbb   |   ,008015L080180,022036,029037
|  B  B  a  a   r     b  b  |   ,047045,L014114L4.
|  BBB    aa a  r     bbb   |
-----------------------------

[Krishnan Govindraj]

In our course, we were thought to think of search as an algorithm involving a fringe and a successor function. 

What i mean is something like:

% Common search algorithm
search(Algorithm, Goal, [FringeHead|FringeTail], Solution ):-
    is_solution( FringeHead, Goal, Solution).

search(Algorithm, Goal, [FringeHead|FringeTail], Solution):-
    update_fringe( Algorithm, FringeHead, FringeTail, UpdatedFringe),
    search(Algorithm, Goal, UpdatedFringe, Solution).


% Only expand_fringe differs from bfs and dfs ( And UCS and A*) 
update_fringe( bfs, CurrentState, CurrentFringe, UpdatedFringe):-
    findall( S, successor(CurrentState, S), Successors),   % Optionally add anti-cycle logic
    append( CurrentFringe, Successors, UpdatedFringe). % FIFO append

update_fringe(dfs, CurrentState, CurrentFringe, UpdatedFringe):-
    findall( S, successor(CurrentState, S), Successors),  % TODO: Add anti-cycle logic
    append( Successors, CurrentFringe,  UpdatedFringe). % LIFO append

Or you can forget about the queue and work with whole fringes at a time. It's simpler.

% bfs(+Fringe, +Goal, -Solution).
bfs( Fringe, Goal, Solution ):-
    member(SomeState, Fringe),
    is_solution(SomeState, Goal, Solution). % Base case

bfs( Fringe, Goal, Solution ):-
    expand_fringe(Fringe, NewFringe),
    bfs(NewFringe, Goal, Solution ). % Recursive case ( I hope this does tail recursion )
   
%  expand_fringe( +OldFringe, -NewFringe)
expand_fringe( OldFringe, NewFringe):-
    findall( S, ( member(X, OldFringe), successor(X,S) ), NewFringe).

Note that this doesn't handle repeated states and leaves out the (challenging) part of defining the successor function.