Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

8-puzzle ?

1,703 views
Skip to first unread message

Carel Schutte

unread,
Oct 15, 1998, 3:00:00 AM10/15/98
to
I need to write a Prolog program to implement the 8-puzzle problem for a
project. Here is an example :

-------------------------
| 2 | 8 | 3 |
-------------------------
| 1 | 6 | 4 |
-------------------------
| 7 | 5 | |
-------------------------

You have to move the blocks so that the digits are in the correct order,
1..8 with the blank in the bottom right corner.

If anyone have any ideas, please let me know.
(It is easier to move the blank than moving the digits)

Thanks

Carel
car...@lantic.co.za

Nick Wedd

unread,
Oct 16, 1998, 3:00:00 AM10/16/98
to
In article <70388j$p...@news1.saix.net>, Carel Schutte
<car...@lantic.co.za> writes

1. Write a representation for the current state of the puzzle.

2. Write a rule that says if you can go from position A to position B
in one move.

3. Write a way of searching out a route from the starting position to
the finishing position. Many books describe methods for this.

Nick
--
Nick Wedd ni...@maproom.co.uk

Matthew M. Huntbach

unread,
Oct 16, 1998, 3:00:00 AM10/16/98
to
Nick Wedd (Ni...@maproom.co.uk) wrote:
> In article <70388j$p...@news1.saix.net>, Carel Schutte
> <car...@lantic.co.za> writes
> >I need to write a Prolog program to implement the 8-puzzle problem for a

> >If anyone have any ideas, please let me know.


> >(It is easier to move the blank than moving the digits)

> 1. Write a representation for the current state of the puzzle.

> 2. Write a rule that says if you can go from position A to position B
> in one move.

> 3. Write a way of searching out a route from the starting position to
> the finishing position. Many books describe methods for this.

The problem with doing this problem in Prolog is that it illustrates what I
see as the fundamental flaw in the language. It promises built-in search,
but the search it gives is straight depth-first, which if you are going to
do any serious search is not what you want at all. New Prolog programmers,
once they have got beyond the novice stage where built-in backtracking is
utterly confusing, get even more confused trying to apply backtracking to
problems where it is not appropriate. Of course the way to deal with the
8-puzzle in Prolog is to subvert Prolog's backtracking and write your own
search. It seems to me to be silly to have built-in search in a language
only to find you have to subvert it if you want to write serious search
programs.

Matthew Huntbach

Wolfgang Schmid

unread,
Oct 16, 1998, 3:00:00 AM10/16/98
to Carel Schutte
sorry!
Here is the text-version !
--------------------------- cut here -------------------------------
PROBLEM8.TXT

Nick Wedd

unread,
Oct 17, 1998, 3:00:00 AM10/17/98
to
In article <707ecl$r2b$2...@beta.qmw.ac.uk>, Matthew M. Huntbach
<m...@dcs.qmw.ac.uk> writes

>The problem with doing this problem in Prolog is that it illustrates what I
>see as the fundamental flaw in the language. It promises built-in search,
>but the search it gives is straight depth-first, which if you are going to
>do any serious search is not what you want at all. New Prolog programmers,
>once they have got beyond the novice stage where built-in backtracking is
>utterly confusing, get even more confused trying to apply backtracking to
>problems where it is not appropriate. Of course the way to deal with the
>8-puzzle in Prolog is to subvert Prolog's backtracking and write your own
>search. It seems to me to be silly to have built-in search in a language
>only to find you have to subvert it if you want to write serious search
>programs.

Yes, you have to do something to "subvert" Prolog's built-in depth-first
search.

You can tell it how to do a breadth-first search; or you can tell it
never to search deeper than, say, 30; or you can tell it to remember
where it has been and never to go round in circles. All of these are
quite easy to program, once you have got the hang of them.

I like a language which lets you program these search strategies so
easily. I would not like a language which enforced its implementor's
favorite search strategy.

Andrew Bromage

unread,
Oct 18, 1998, 3:00:00 AM10/18/98
to
G'day all.

Wolfgang Schmid <wsc...@edu.uni-klu.ac.at> writes:

[...]
> % I have a i-486 100Mhz system,
> % it required 3 minutes of calculation :-( !

Not to be outdone, here's a Mercury solution which uses A* search.

Note that it _also_ uses default depth-first-search to find the
successor positions from some position (using the Mercury primitive
aggregate, which is a nice alternative to solutions), which just goes
to show that default search strategies are often fine.

It runs in about 0.3 seconds on a Pentium 166MHz GNU/Linux machine
(66.15 BogoMIPS), using the default optimisation level.

Cheers,
Andrew Bromage

%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%

:- module puzzle8.

%---------------------------------------------------------------------------%

:- interface.
:- import_module io.

:- pred main(io__state :: di, io__state :: uo) is det.

%---------------------------------------------------------------------------%

:- implementation.
:- import_module std_util, pqueue, list, int, require, set_bbbtree.

:- type cell
---> blank
; stone(int).

:- type board
---> board(
cell, cell, cell,
cell, cell, cell,
cell, cell, cell
).

:- type position
---> position(
board, % Current board
list(int) % Reversed solution so far
).

%---------------------------------------------------------------------------%

:- pred start_state(board :: out) is det.

start_state(board(
stone(1), stone(3), stone(2),
stone(4), stone(6), stone(5),
stone(7), blank, stone(8)
)).

:- pred end_state(board :: in) is semidet.

end_state(board(
stone(1), stone(2), stone(3),
stone(4), stone(5), stone(6),
stone(7), stone(8), blank
)).

%---------------------------------------------------------------------------%

:- pred move(board, board, int).
:- mode move(in, out, out) is nondet.
:- mode move(out, in, out) is nondet.

move(board(blank,stone(X),B13,B21,B22,B23,B31,B32,B33),
board(stone(X),blank,B13,B21,B22,B23,B31,B32,B33), X).
move(board(B11,blank,stone(X),B21,B22,B23,B31,B32,B33),
board(B11,stone(X),blank,B21,B22,B23,B31,B32,B33), X).
move(board(B11,B12,B13,blank,stone(X),B23,B31,B32,B33),
board(B11,B12,B13,stone(X),blank,B23,B31,B32,B33), X).
move(board(B11,B12,B13,B21,blank,stone(X),B31,B32,B33),
board(B11,B12,B13,B21,stone(X),blank,B31,B32,B33), X).
move(board(B11,B12,B13,B21,B22,B23,blank,stone(X),B33),
board(B11,B12,B13,B21,B22,B23,stone(X),blank,B33), X).
move(board(B11,B12,B13,B21,B22,B23,B31,blank,stone(X)),
board(B11,B12,B13,B21,B22,B23,B31,stone(X),blank), X).
move(board(blank,B12,B13,stone(X),B22,B23,B31,B32,B33),
board(stone(X),B12,B13,blank,B22,B23,B31,B32,B33), X).
move(board(B11,blank,B13,B21,stone(X),B23,B31,B32,B33),
board(B11,stone(X),B13,B21,blank,B23,B31,B32,B33), X).
move(board(B11,B12,blank,B21,B22,stone(X),B31,B32,B33),
board(B11,B12,stone(X),B21,B22,blank,B31,B32,B33), X).
move(board(B11,B12,B13,blank,B22,B23,stone(X),B32,B33),
board(B11,B12,B13,stone(X),B22,B23,blank,B32,B33), X).
move(board(B11,B12,B13,B21,blank,B23,B31,stone(X),B33),
board(B11,B12,B13,B21,stone(X),B23,B31,blank,B33), X).
move(board(B11,B12,B13,B21,B22,blank,B31,B32,stone(X)),
board(B11,B12,B13,B21,B22,stone(X),B31,B32,blank), X).

%---------------------------------------------------------------------------%

% The heuristic we are using is to use the sum of the distances
% of all stones from where they should be, using "taxicab
% distance". This is a lower bound on the number of moves
% required to return all stones to where they should be, so
% this heuristic is safe.

:- func heuristic(board) = int.
heuristic(board(A, B, C, D, E, F, G, H, I)) =
dist(A, 1, 1) + dist(B, 1, 2) + dist(C, 1, 3) +
dist(D, 2, 1) + dist(E, 2, 2) + dist(F, 2, 3) +
dist(G, 3, 1) + dist(H, 3, 2) + dist(I, 3, 3).

:- func dist(cell, int, int) = int.
dist(Cell, FoundX, FoundY) = Dist :-
( Cell = stone(Stone),
( realpos(Stone, RealX, RealY) ->
int__abs(RealX - FoundX, XDist),
int__abs(RealY - FoundY, YDist),
Dist = XDist + YDist
;
error("dist")
)
; Cell = blank,
Dist = 0
).

:- pred realpos(int :: in, int :: out, int :: out) is semidet.
realpos(1, 1, 1).
realpos(2, 1, 2).
realpos(3, 1, 3).
realpos(4, 2, 1).
realpos(5, 2, 2).
realpos(6, 2, 3).
realpos(7, 3, 1).
realpos(8, 3, 2).

%---------------------------------------------------------------------------%

:- pred solve(set_bbbtree(board), pqueue(int, position), list(int)).
:- mode solve(in, in, out) is semidet.

solve(Seen0, Pos0, Solution) :-
pqueue__remove(Pos0, _, position(Board0, Soln0), Pos1),
( set_bbbtree__member(Board0, Seen0) ->
solve(Seen0, Pos1, Solution)
; end_state(Board0) ->
reverse(Soln0, Solution)
;
set_bbbtree__insert(Seen0, Board0, Seen),
list__length(Soln0, Cost0),
Cost is Cost0 + 1,
aggregate((pred(NextPos :: out) is nondet :-
( move(Board0, Board, X)
; move(Board, Board0, X)
),
% This optimisation seems to speed
% things up by about 30%, though the
% timings are quite small as it is.
\+ set_bbbtree__member(Board, Seen),
NextPos = position(Board, [X | Soln0])
), (pred(NextPos :: in, P0 :: in, P :: out) is det :-
NextPos = position(Board, _),
pqueue__insert(P0, Cost + heuristic(Board), NextPos, P)
), Pos0, Pos),
solve(Seen, Pos, Solution)
).

%---------------------------------------------------------------------------%

main -->
{
pqueue__init(Pos0),
start_state(Board0),
pqueue__insert(Pos0, heuristic(Board0),
position(Board0, []), Pos),
set_bbbtree__init(Seen0)
},
( { solve(Seen0, Pos, Solution) } ->
write(Solution),
nl
;
write_string("No solution.\n")
).

%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%

Thomas Charles CONWAY

unread,
Oct 18, 1998, 3:00:00 AM10/18/98
to
bro...@cs.mu.oz.au (Andrew Bromage) writes:

>Note that it _also_ uses default depth-first-search to find the
>successor positions from some position (using the Mercury primitive
>aggregate, which is a nice alternative to solutions), which just goes
>to show that default search strategies are often fine.

The use of depth-first search in Mercury is still somewhat different
to its use in Prolog. The reason is that in Mercury there are clear
and *enforced* divisions between nondeterministic search code and
deterministic code. Using aggregate (like using findall/etc) guarantees
that nondeterminism does not escape, and the compiler can use this
information to generate efficient code. In Prolog there is this recurring
difficulty that it is very easy to accidentally introduce nondeterminism
or to allow the intended nondeterminism to escape from the intended
scope. Often as not this results in strange behaviour where a bug in
one part of the program causes failure and backtracking into an unrelated
part of the program where a choice point was accidentally left behind.

Before everyone flames me all the way to hell and gone, I should point
out that one of the unsolved (or at least not well solved) problems
with Mercury is how to do "pruned" searches neatly as one does in Prolog.

>It runs in about 0.3 seconds on a Pentium 166MHz GNU/Linux machine
>(66.15 BogoMIPS), using the default optimisation level.

BogoMIPS doesn't really tell you anything much - only how fast the
CPU can do a tight non-memory-referencing loop.

Thomas
--
Thomas Conway <con...@cs.mu.oz.au>
Nail here [] for new monitor. )O+

Fergus Henderson

unread,
Oct 19, 1998, 3:00:00 AM10/19/98
to
con...@cs.mu.oz.au (Thomas Charles CONWAY) writes:

>Before everyone flames me all the way to hell and gone, I should point
>out that one of the unsolved (or at least not well solved) problems
>with Mercury is how to do "pruned" searches neatly as one does in Prolog.

Could you elaborate and/or give an example?

There are some aspects of pruning which are not solved as well as they
could be in Mercury, but in general I would say that Mercury handles
pruning much more elegantly than Prolog does.

--
Fergus Henderson <f...@cs.mu.oz.au> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger f...@128.250.37.3 | -- the last words of T. S. Garp.

cahu...@ysu.edu

unread,
Oct 23, 1998, 3:00:00 AM10/23/98
to

A logic programming approach to Prolog programs usually requires no subverting of the
prolog search engine. If you find yourself working against the prolog
environment, then you should rethink your solution to a given problem.
I'm sure you know that a logic program can be specified in a variety of ways.
when writing in Prolog, pick one that works.

Cameron Hughes
cahu...@cis.ysu.edu
cahu...@cc.ysu.edu


Matthew M. Huntbach

unread,
Oct 26, 1998, 3:00:00 AM10/26/98
to
cahu...@ysu.edu wrote:

> A logic programming approach to Prolog programs usually requires no
> subverting of the prolog search engine. If you find yourself working
> against the prolog environment, then you should rethink your solution to a
> given problem. I'm sure you know that a logic program can be specified in a
> variety of ways. when writing in Prolog, pick one that works.

The "obvious" Prolog solution to the 8-puzzle is:

puzzle(State,State) :- goal(State).
puzzle(State,Solution) :- leftmove(Solution,State1), puzzle(State1,Solution).
puzzle(State,Solution) :- rightmove(Solution,State1), puzzle(State1,Solution).
puzzle(State,Solution) :- upmove(Solution,State1), puzzle(State1,Solution).
puzzle(State,Solution) :- downmove(Solution,State1), puzzle(State1,Solution).

I find that people who have done a bit of Prolog programming tend to think
something like this is the way to do the 8-puzzle in Prolog. In reality it
is daft to solve this problem in any way except one using heuristics, in
which case you have to build in your own representation of the state of
search i.e. you don't use Prolog's. Of course you can do this in Prolog,
and you can do it quite neatly in Prolog. But that doesn't change my point
that Prolog's built-in search is of no help to you in solving this problem,
indeed it may well be a hindrance in making you think there are easier ways
of solving it than there really are, or a hindrance in making you think some
inefficient depth-first search program is a good one, simply because it can
be done neatly in Prolog.

Matthew Huntbach

Rolf Czedzak

unread,
Oct 26, 1998, 3:00:00 AM10/26/98
to
wrote: <70qmcq$ktd$1...@news.ysu.edu>

> A logic programming approach to Prolog programs usually requires no
> subverting of the prolog search engine. If you find yourself working
> against the prolog environment, then you should rethink your solution
> to a given problem. I'm sure you know that a logic program can be
> specified in a variety of ways. when writing in Prolog, pick one that
> works.

I don't back this. The fact that depth first is prolog search engine's
default does not mean that it's the "natural" way which is well suited
to any problem. Sticking to just the default would IMHO unneccessarily
limit the power of the language.

> Cameron Hughes
> cahu...@cis.ysu.edu
> cahu...@cc.ysu.edu

Rolf (C)

Matthew M. Huntbach

unread,
Oct 27, 1998, 3:00:00 AM10/27/98
to
Rolf Czedzak (r...@sensecom.de) wrote:

> I don't back this. The fact that depth first is prolog search engine's
> default does not mean that it's the "natural" way which is well suited
> to any problem. Sticking to just the default would IMHO unneccessarily
> limit the power of the language.

It's not the default, it's the *only* search engine Prolog has. If you
want Prolog to search in any way other than depth-first, you have to
program it yourself, just as you would if you used any other programming
language. Since any program making serious use of search doesn't use
depth-first search, I conclude Prolog's built-in search is not nearly so
useful an aspect of the language as many of its advocates suggest.

Matthew Huntbach

Torkel Franzen

unread,
Oct 27, 1998, 3:00:00 AM10/27/98
to
m...@dcs.qmw.ac.uk (Matthew M. Huntbach) writes:

> Since any program making serious use of search doesn't use
> depth-first search, I conclude Prolog's built-in search is not nearly so
> useful an aspect of the language as many of its advocates suggest.

Hmm..are you saying that programs that use depth-first search are
frivolous?

John Dowding

unread,
Oct 27, 1998, 3:00:00 AM10/27/98
to
>>>>> "Matthew" == Matthew M Huntbach <m...@dcs.qmw.ac.uk> writes:

Matthew> It's not the default, it's the *only* search engine
Matthew> Prolog has. If you want Prolog to search in any way other
Matthew> than depth-first, you have to program it yourself, just
Matthew> as you would if you used any other programming
Matthew> language.

That's not true. Extensions to Prolog's top-down search, like
memoization and iterative-deepening, give more powerful search
capabilities, but are significantly easier to implement in Prolog than
in other general purpose programming languages.

Matthew> Since any program making serious use of search
Matthew> doesn't use depth-first search, I conclude Prolog's
Matthew> built-in search is not nearly so useful an aspect of the
Matthew> language as many of its advocates suggest.

Well, I claim to be writting programs that make serious use of search,
and I disagree. Particularly when adding memoization, depth-first
search is effective for natural language generation.


--

John Dowding
dow...@ai.sri.com
http://www.ai.sri.com/~dowding

Matthew M. Huntbach

unread,
Oct 28, 1998, 3:00:00 AM10/28/98
to

Prolog's depth-first search is part of the technique of Prolog programming.
You can use it in circumstances where in imperative languages you might use
a loop. What it isn't sensible to use it for is search of a large search-space,
because in that case you would most likely want to use some sort of
heuristics.

Matthew Huntbach

Matthew M. Huntbach

unread,
Oct 28, 1998, 3:00:00 AM10/28/98
to
John Dowding (dow...@AI.SRI.COM) wrote:
> >>>>> "Matthew" == Matthew M Huntbach <m...@dcs.qmw.ac.uk> writes:

> Matthew> It's not the default, it's the *only* search engine
> Matthew> Prolog has. If you want Prolog to search in any way other
> Matthew> than depth-first, you have to program it yourself, just
> Matthew> as you would if you used any other programming
> Matthew> language.

> That's not true. Extensions to Prolog's top-down search, like
> memoization and iterative-deepening, give more powerful search
> capabilities, but are significantly easier to implement in Prolog than
> in other general purpose programming languages.

I'm not saying they are not easy to program in Prolog. I am just saying you
have to program them yourself - they're not built in to Prolog. So the
advantages Prolog has to offer may have more to do with other aspects of the
language than its built-in depth-first-with-backtracking search.

Matthew Huntbach

Torkel Franzen

unread,
Oct 28, 1998, 3:00:00 AM10/28/98
to

But surely in an imperative language you would use a loop for a
large space as well, no matter what the heuristic?


Lee Naish

unread,
Oct 28, 1998, 3:00:00 AM10/28/98
to
m...@dcs.qmw.ac.uk (Matthew M. Huntbach) writes:

> The "obvious" Prolog solution to the 8-puzzle is:
>
> puzzle(State,State) :- goal(State).
> puzzle(State,Solution) :- leftmove(Solution,State1), puzzle(State1,Solution).

...


>
> I find that people who have done a bit of Prolog programming tend to think
> something like this is the way to do the 8-puzzle in Prolog.

People who have done a bit of programming in any language tend to have all
sorts of wrong ideas, especially if they don't appreciate complexity
theory. This tends to be compounded in Prolog due to poor teaching, poor
textbooks, and mis-information from other sources such as the net.

> But that doesn't change my point
> that Prolog's built-in search is of no help to you in solving this problem,
> indeed it may well be a hindrance in making you think there are easier ways
> of solving it than there really are, or a hindrance in making you think some
> inefficient depth-first search program is a good one, simply because it can
> be done neatly in Prolog.

I disagree. A key part of solving state-space problems (by whatever search
method) is finding the set of successor states from a given state. It is
often very natural to code a nondeterministic successor predicate and call
it inside an all solutions predicate. This relies on *some* search
mechanism in the language, and the most efficient method for cases like
this, where typically the search space is a finite tree, is depth first
search. Aggregates are often a concise and elegant coding technique (they
might not be the most efficient, but thats a small matter of
implementation:-). Doing a quick grep or two of some recently written code
of mine revealed over a dozen uses of aggregates. This suggests that the
Prolog builtin search saved me quite a lot of programming time in that
application, even though its basically deterministic.

lee

Rolf Czedzak

unread,
Oct 28, 1998, 3:00:00 AM10/28/98
to
Matthew M. Huntbach wrote: <714n7q$7ur$1...@beta.qmw.ac.uk>

> Rolf Czedzak (r...@sensecom.de) wrote:
>
> > I don't back this. The fact that depth first is prolog search
> > engine's default does not mean that it's the "natural" way which is
> > well suited to any problem. Sticking to just the default would IMHO
> > unneccessarily limit the power of the language.
>

> It's not the default, it's the *only* search engine Prolog has.

Well, my understanding of "default" is: If You don't specify any
search ttechnique, the one the language uses, is it's "default". (?)
But in some way You are nevertheless "programming" it. :-)

> If you
> want Prolog to search in any way other than depth-first, you have to
> program it yourself, just as you would if you used any other
> programming language.

Agreed, but let me use a slightly different formulation. If You want
prolog to search in any other way than depth-first, You may specify
this in Your clauses AKA the logic of the problem. It's just (IMHO) that
prolog supports YOu more on this task than many other languages. (Not
heading for a language war.)

> Since any program making serious use of search

> doesn't use depth-first search, I conclude Prolog's built-in search is


> not nearly so useful an aspect of the language as many of its advocates
> suggest.

Neither You nor me know each program "making serious use of search", I
conclude that You are most probably wrong. ;-)

> Matthew Huntbach

Rolf

Matthew M. Huntbach

unread,
Oct 29, 1998, 3:00:00 AM10/29/98
to
Rolf Czedzak (r...@sensecom.de) wrote:
> Matthew M. Huntbach wrote: <714n7q$7ur$1...@beta.qmw.ac.uk>
> > Rolf Czedzak (r...@sensecom.de) wrote:

> > > I don't back this. The fact that depth first is prolog search
> > > engine's default does not mean that it's the "natural" way which is
> > > well suited to any problem. Sticking to just the default would IMHO
> > > unneccessarily limit the power of the language.

> > It's not the default, it's the *only* search engine Prolog has.

> Well, my understanding of "default" is: If You don't specify any
> search ttechnique, the one the language uses, is it's "default". (?)
> But in some way You are nevertheless "programming" it. :-)

My understanding of "default" is that it implies there are other options.
There are no other options in Prolog. It searches its space depth-first.
Any other search method you don't use a built-in Prolog option, you write
it yourself.

Matthew Huntbach

Matthew M. Huntbach

unread,
Oct 29, 1998, 3:00:00 AM10/29/98
to
Torkel Franzen (tor...@sm.luth.se) wrote:
> m...@dcs.qmw.ac.uk (Matthew M. Huntbach) writes:

You would program the search space yourself, as a linked-list or something,
inserting the states in it in heuristic order. As you do if you don't want
depth-first search in Prolog.

Matthew Huntbach


Matthew M. Huntbach

unread,
Oct 29, 1998, 3:00:00 AM10/29/98
to
Lee Naish (na...@elcano.dia.fi.upm.es) wrote:
> m...@dcs.qmw.ac.uk (Matthew M. Huntbach) writes:

> > But that doesn't change my point
> > that Prolog's built-in search is of no help to you in solving this problem,
> > indeed it may well be a hindrance in making you think there are easier ways
> > of solving it than there really are, or a hindrance in making you think some
> > inefficient depth-first search program is a good one, simply because it can
> > be done neatly in Prolog.

> I disagree. A key part of solving state-space problems (by whatever search
> method) is finding the set of successor states from a given state. It is
> often very natural to code a nondeterministic successor predicate and call
> it inside an all solutions predicate. This relies on *some* search
> mechanism in the language, and the most efficient method for cases like
> this, where typically the search space is a finite tree, is depth first
> search. Aggregates are often a concise and elegant coding technique (they
> might not be the most efficient, but thats a small matter of
> implementation:-).

Yes, Prolog's depth-first search is of some use in aspects of programming.
The fact that it's there compensates for the lack of other control
structures. But it seems to me the common notion that Prolog is good for
search programs because it's got built-in search is wrong.

Matthew Huntbach

Torkel Franzen

unread,
Oct 29, 1998, 3:00:00 AM10/29/98
to
m...@dcs.qmw.ac.uk (Matthew M. Huntbach) writes:

>You would program the search space yourself, as a linked-list or something,
>inserting the states in it in heuristic order.

And then use a loop...?

Nick Wedd

unread,
Oct 29, 1998, 3:00:00 AM10/29/98
to
In article <7198pa$kce$4...@beta.qmw.ac.uk>, Matthew M. Huntbach
<m...@dcs.qmw.ac.uk> writes

>Yes, Prolog's depth-first search is of some use in aspects of programming.


>The fact that it's there compensates for the lack of other control
>structures. But it seems to me the common notion that Prolog is good for
>search programs because it's got built-in search is wrong.

It seems right to me.

In the very simplest cases, depth-first is what I want anyway. In cases
where I need to use some other method, the presence of depth-first makes
it much easier to write the search strategy that I want.

Lee Naish

unread,
Oct 30, 1998, 3:00:00 AM10/30/98
to
m...@dcs.qmw.ac.uk (Matthew M. Huntbach) writes:

> Yes, Prolog's depth-first search is of some use in aspects of programming.

> But it seems to me the common notion that Prolog is good for

> search programs because it's got built-in search is wrong.

I agree Prolog has been over-sold in this respect by some people. DFS is
certainly no good for more complex search problems. However, there are
many applications, such as the aggregates I mentioned, in which DFS is
fine. In "typical" programming these applications are quite common. The
more complex search problems are less common than text books, courses and
comp.lang.prolog would suggest (there are very few countries where zebras
are allowed as pets for a start:-).

You can make the same kind of criticism for other languages which claim to
have built-in support for integers. In non-trivial numerical applications
the built-in integers just don't work. When someone writes x+y in C
and it produces the wrong result because x and y are too big, no-one seems
to complain about the language. Yet when someone writes a naive solution
to the eight puzzle in Prolog and it doesn't work well (though it never
produces a wrong answer), this is loudly proclaimed to be a defect of the
language. It seems to me like there is a double standard here:
C is not even expected to implement integer addition correctly, whereas
Prolog is expected to solve all the world's problems (and in polynomial
time, of course).

lee

Ulrich Neumerkel

unread,
Oct 30, 1998, 3:00:00 AM10/30/98
to
In article <xlh4ssm...@elcano.dia.fi.upm.es>,

Lee Naish <na...@elcano.dia.fi.upm.es> writes:
> m...@dcs.qmw.ac.uk (Matthew M. Huntbach) writes:
>
> > Yes, Prolog's depth-first search is of some use in aspects of programming.
>
> > But it seems to me the common notion that Prolog is good for
> > search programs because it's got built-in search is wrong.
>
> I agree Prolog has been over-sold in this respect by some people. DFS is
> certainly no good for more complex search problems. However, there are
> many applications, such as the aggregates I mentioned, in which DFS is
> fine. In "typical" programming these applications are quite common.

Another example where the native search of Prolog is useful is
iterative deepening. Here DFS is used almost directly without
resorting to second order predicates.

--
Ulrich Neumerkel http://www.complang.tuwien.ac.at/ulrich/

cahu...@ysu.edu

unread,
Oct 30, 1998, 3:00:00 AM10/30/98
to
In <71204m$36l$1...@beta.qmw.ac.uk>, m...@dcs.qmw.ac.uk (Matthew M. Huntbach) writes:

>cahu...@ysu.edu wrote:
>
>> A logic programming approach to Prolog programs usually requires no
>> subverting of the prolog search engine. If you find yourself working
>> against the prolog environment, then you should rethink your solution to a
>> given problem. I'm sure you know that a logic program can be specified in a
>> variety of ways. when writing in Prolog, pick one that works.
>
>The "obvious" Prolog solution to the 8-puzzle is:
>
>puzzle(State,State) :- goal(State).
>puzzle(State,Solution) :- leftmove(Solution,State1), puzzle(State1,Solution).
>puzzle(State,Solution) :- rightmove(Solution,State1), puzzle(State1,Solution).
>puzzle(State,Solution) :- upmove(Solution,State1), puzzle(State1,Solution).
>puzzle(State,Solution) :- downmove(Solution,State1), puzzle(State1,Solution).
>
>I find that people who have done a bit of Prolog programming tend to think
>something like this is the way to do the 8-puzzle in Prolog. In reality it
>is daft to solve this problem in any way except one using heuristics, in
>which case you have to build in your own representation of the state of
>search i.e. you don't use Prolog's. Of course you can do this in Prolog,
>and you can do it quite neatly in Prolog. But that doesn't change my point

>that Prolog's built-in search is of no help to you in solving this problem,
>indeed it may well be a hindrance in making you think there are easier ways
>of solving it than there really are, or a hindrance in making you think some
>inefficient depth-first search program is a good one, simply because it can
>be done neatly in Prolog.
>
>Matthew Huntbach


I can appreciate your position. However, the amount of work that prolog
does or does not do is dependant on how you logically represent the problem.
I'm sure you know that the search space for a problem is contingent on the
data structures and knowledge structures involved. Also prolog simply provides
logical primitives, and a fundamental search engine that you can build upon.
It is up to the logic programmer, to design higher level search engines
if necessary. The trick is to work with prolog not against prolog when designing
a new search strategy. There are very many graph traversal algorithms.
Depth first and breadth first are among those most elemental. Judgement
with respect to power of Prolog should be witheld until you have had the
opportunity to investigate other types of graph traversal. Also it would be
instructive if may an honest attemp to represent your 8-puzzle as another
kind of search space in Prolog. If you would like some direction with
respect to some of the more challenging graph representations let me
know.


Cameron A. Hughes
cahu...@cc.ysu.edu

"The emperor's wall building and book burining are opposite terms in
an equation whose sum is nothing"

Proteus IV "Demon Seed"


cahu...@ysu.edu

unread,
Oct 30, 1998, 3:00:00 AM10/30/98
to


The other problem with calling Prolog's execution mechanism a search
strategy is a matter of classification. In 3GLs and 4GLs they have
a simple sequence execution model as the "default" if you want to
call it that. In order for the programmer to achieve other than simple
sequence execution the programmer must use loops, and decision structures.
Prolog does not have a simple sequence execution model as the default.
It uses top to bottom, left to right etc. If the programmer wants to
use some sequence other that Prolog's basic execution sequence then
the Prolog programmer has to use other features of the language,
e.g. List processing, difference structures, unification and inverse
unification.

Matthew M. Huntbach

unread,
Nov 2, 1998, 3:00:00 AM11/2/98
to
cahu...@ysu.edu wrote:

> In <71204m$36l$1...@beta.qmw.ac.uk>, m...@dcs.qmw.ac.uk (Matthew M. Huntbach) writes:
>>The "obvious" Prolog solution to the 8-puzzle is:
>>
>>puzzle(State,State) :- goal(State).
>>puzzle(State,Solution) :- leftmove(Solution,State1), puzzle(State1,Solution).
>>puzzle(State,Solution) :- rightmove(Solution,State1), puzzle(State1,Solution).
>>puzzle(State,Solution) :- upmove(Solution,State1), puzzle(State1,Solution).
>>puzzle(State,Solution) :- downmove(Solution,State1), puzzle(State1,Solution).
> >
> >I find that people who have done a bit of Prolog programming tend to think
> >something like this is the way to do the 8-puzzle in Prolog. In reality it
> >is daft to solve this problem in any way except one using heuristics, in
> >which case you have to build in your own representation of the state of
> >search i.e. you don't use Prolog's.

> There are very many graph traversal algorithms.


> Depth first and breadth first are among those most elemental. Judgement
> with respect to power of Prolog should be witheld until you have had the
> opportunity to investigate other types of graph traversal. Also it would be
> instructive if may an honest attemp to represent your 8-puzzle as another
> kind of search space in Prolog. If you would like some direction with
> respect to some of the more challenging graph representations let me know.

As I've been programming in Prolog since I was taught it by Bob Kowalski in the
1970s, and have had papers published on search programs in logic languages,
thank you for your kind offer, but I do not think I am in need of your
assistance.

Matthew Huntbach

Matthew M. Huntbach

unread,
Nov 2, 1998, 3:00:00 AM11/2/98
to
Lee Naish (na...@elcano.dia.fi.upm.es) wrote:
> m...@dcs.qmw.ac.uk (Matthew M. Huntbach) writes:

> > Yes, Prolog's depth-first search is of some use in aspects of programming.

> > But it seems to me the common notion that Prolog is good for
> > search programs because it's got built-in search is wrong.

> I agree Prolog has been over-sold in this respect by some people.

[... snip ...]

> You can make the same kind of criticism for other languages which claim to
> have built-in support for integers. In non-trivial numerical applications
> the built-in integers just don't work. When someone writes x+y in C
> and it produces the wrong result because x and y are too big, no-one seems
> to complain about the language. Yet when someone writes a naive solution
> to the eight puzzle in Prolog and it doesn't work well (though it never
> produces a wrong answer), this is loudly proclaimed to be a defect of the
> language. It seems to me like there is a double standard here:
> C is not even expected to implement integer addition correctly, whereas
> Prolog is expected to solve all the world's problems (and in polynomial
> time, of course).

Sorry, who is saying Prolog is defective? The *only* point I was trying to
make is the very one you have now made yourself - that Prolog has at times
been over-sold with regards to its built-in search. I'm not saying that
there shouldn't be DFS in Prolog, or that it's entirely useless, all I'm
saying is that it doesn't give you quite the power some have naively
suggested. There was a time when Prolog advocates were almost saying that
it would solve all the world's problems. I think this overselling of Prolog
has contributed to the drop in interest when it didn't meet the hype.

Matthew Huntbach

cahu...@ysu.edu

unread,
Nov 3, 1998, 3:00:00 AM11/3/98
to


I apologize. No offense meant. Did not mean to have a condescending tone.
I do however find the field of graph theory vast, and
it grows almost daily. I can't recall anyone that has a complete
mastery of the techniques in graph traversal, or for that matter a large enough
picture of the field to be able to exclude certain elegant solutions. It is quite
possible you are unique in that respect. Considering that you studied with or under
Kowalski, could you post a formal proof that demonstrates that the Prolog
search mechanism cannot be easily adapted to implement for elegant and
powerful search techniques?

Nothing fancy. Just something that says that back tracking and DFS do not
have homorphisms among more sophisticated graph traversal techniques. Since
you are obviously a student of logic and probably up to date on current
approaches to graph traversal and DFS, could you post your ideas on how
complex variable vector spaces can be implemented in Prolog to provide
an elegant and effective solution to the 8-puzzle?

Also I have seen a pretty elegant black board engine implemented in Prolog
that does a masterful job of solving the entire class of 8-puzzle problems.

Perhaps revisiting some of the structures you learned under
Kowalski in the 70's in light of some of the current work in graph theory might
help to develop a new paradigm for solving the 8-puzzle in prolog.

I am happy that you are published. I am too. Keep up the good work.
I look forward to seeing papers from you in the future.

Cameron A. Hughes
cahu...@cc.ysu.edu


Matthew M. Huntbach

unread,
Nov 4, 1998, 3:00:00 AM11/4/98
to
cahu...@ysu.edu wrote:
> Considering that you studied with or under
> Kowalski, could you post a formal proof that demonstrates that the Prolog
> search mechanism cannot be easily adapted to implement for elegant and
> powerful search techniques?

> Nothing fancy. Just something that says that back tracking and DFS do not
> have homorphisms among more sophisticated graph traversal techniques.

But that's not what I've been saying. All I've been saying is that if you
want anything other than DFS, you have to program it yourself in Prolog.
Just as you have to program it yourself in any other languages. That's not
to say you can't do it in Prolog, just to suggest that Prolog's built-in
DFS isn't as useful as some make out. You can program search elegantly
in functional languages, for example, though they don't have built-in DFS.
My particular interest is in the use of the concurrent logic languages,
which don't have Prolog's DFS mechanism. I've programmed in Prolog and I've
programmed in the concurrent logic languages, and I find the lack of DFS
in the latter to be far less of an issue than people used only to Prolog
might imagine.

Matthew Huntbach

praful...@gmail.com

unread,
Sep 15, 2017, 11:34:39 AM9/15/17
to
Plzzz tell me how to solve this tell me a prcedure

burs...@gmail.com

unread,
Sep 15, 2017, 11:40:28 PM9/15/17
to
What has changed since 1998 when the hype dropped?

In my opinion a replacement for Prolog wasn't
found so far. Take the recent interest in
"pattern matching", exemplified here:

"Among the existing systems, Mathematica offers
the most expressive pattern matching"
Non-linear Associative-Commutative Many-to-One
Pattern Matching with Sequence Variables - Manuel Krebber, 2017
https://arxiv.org/abs/1705.00907

"Egison Programming Language Paper: matching
against not only algebraic data types but also
unfree data types such as sets, graphs and
any other data types"
Non-Linear Pattern-Matching against Unfree
Data Types with Lexical Scoping - Satoshi Egi, 2014
https://arxiv.org/abs/1407.0729

How expressive is Prolog? Isnt every Prolog
predicate a pattern matcher?

Dhu on Gate

unread,
Sep 17, 2017, 11:17:54 AM9/17/17
to
On Fri, 15 Sep 2017 20:40:27 -0700, bursejan wrote:

> What has changed since 1998 when the hype dropped?
>
> In my opinion a replacement for Prolog wasn't
> found so far. Take the recent interest in

Scheme could. Doesn't have horn clause form intrinsic, tho'
(which is easy to parse as homologue), which makes for a
steep learning curve.

Dhu


> "pattern matching", exemplified here:
>
> "Among the existing systems, Mathematica offers
> the most expressive pattern matching"
> Non-linear Associative-Commutative Many-to-One
> Pattern Matching with Sequence Variables - Manuel Krebber, 2017
> https://arxiv.org/abs/1705.00907
>
> "Egison Programming Language Paper: matching
> against not only algebraic data types but also
> unfree data types such as sets, graphs and
> any other data types"
> Non-Linear Pattern-Matching against Unfree
> Data Types with Lexical Scoping - Satoshi Egi, 2014
> https://arxiv.org/abs/1407.0729
>
> How expressive is Prolog? Isnt every Prolog
> predicate a pattern matcher?
>
> Am Freitag, 15. September 2017 17:34:39 UTC+2 schrieb praful...@gmail.com:
>> Plzzz tell me how to solve this tell me a prcedure





--
Je suis Canadien. Ce n'est pas Francais ou Anglaise.
C'est une esp`ece de sauvage: ne obliviscaris, vix ea nostra voco;-)

http://babayaga.neotext.ca/PublicKeys/Duncan_Patton_a_Campbell_pubkey.txt

burs...@gmail.com

unread,
Sep 17, 2017, 11:25:51 AM9/17/17
to
How long does run queen11.pl in a Scheme or a LISP
Prolog Library? Do you know the figures?

Remember PrologCafe does it in around ~250ms, all
queen11 solutions, without printing them.

Show figures please!

Dhu on Gate

unread,
Sep 26, 2017, 5:37:58 PM9/26/17
to
On Sun, 17 Sep 2017 08:25:50 -0700, bursejan wrote:

> How long does run queen11.pl in a Scheme or a LISP
> Prolog Library? Do you know the figures?
>
> Remember PrologCafe does it in around ~250ms, all
> queen11 solutions, without printing them.
>
> Show figures please!

That's compiler optimization. I was referring to the ease with which
Prolog can be described in Human language (homologue), which is it's
true strength.

Dhu

>
> Am Sonntag, 17. September 2017 17:17:54 UTC+2 schrieb Dhu on Gate:
>> On Fri, 15 Sep 2017 20:40:27 -0700, bursejan wrote:
>>
>> > What has changed since 1998 when the hype dropped?
>> >
>> > In my opinion a replacement for Prolog wasn't
>> > found so far. Take the recent interest in
>>
>> Scheme could. Doesn't have horn clause form intrinsic, tho'
>> (which is easy to parse as homologue), which makes for a
>> steep learning curve.
>>
>> Dhu





0 new messages