4,158 views

Skip to first unread message

Jan 4, 2019, 11:51:23 PM1/4/19

to SWI-Prolog

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 usingBFS(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

Jan 5, 2019, 3:01:50 AM1/5/19

to Tharushi Geethma, SWI-Prolog

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.

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.

Jan 5, 2019, 4:13:27 AM1/5/19

to Tharushi Geethma, SWI-Prolog

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

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

Jan 5, 2019, 3:13:47 PM1/5/19

to SWI-Prolog, Tharushi Geethma, Kuniaki Mukai

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 usingBFS (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 |

-----------------------------

| 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 |

-----------------------------

Jan 6, 2019, 5:12:45 AM1/6/19

to SWI-Prolog

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu