NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/comp/lang/pascal/7797

Internet Message Format | 1993-01-02 | 3.4 KB

Xref: sparky comp.lang.pascal:7797 rec.games.programmer:5238 comp.sys.ibm.pc.misc:16281 comp.sys.ibm.pc.programmer:722
Path: sparky!uunet!munnari.oz.au!ariel.ucs.unimelb.EDU.AU!ucsvc.ucs.unimelb.edu.au!lugb!lux!cscmd
Newsgroups: comp.lang.pascal,rec.games.programmer,comp.sys.ibm.pc.misc,comp.sys.ibm.pc.programmer
Subject: Re: Source of a little puzzle under MS-DOS TurboPascal wanted
Message-ID: <[e-mail]>
From: [e-mail] (Mitch Davis)
Date: Sat, 2 Jan 1993 10:06:25 GMT
Sender: [e-mail] (USENET News System)
References: <[e-mail]>
Organization: La Trobe University
Lines: 70

In article <[e-mail]> [e-mail] (Stefan Bechtold) writes:
>Hi !
>
>A friend of mine is looking for a puzzle; it's a little bit difficult
>to describe but I'll try it.
>This puzzle shuffles a display like those old 16 square plastic
>puzzles.
>(Like:        9    14    10    4
>
>        6    1    8    12
>
>        2    15        5
>
>        11    7    3    13
>
>and you have to put those squares in the right order)
>
>The program should also be able to solve the problem itself.

First, I should mention that picking Turbo Pascal as a language for
solving this problem is fairly poor.  To do this in a language like LISP
or Scheme is about 100 lines (or at least, that is how big my CS
assignment this year to do it was), while I can't see how you'd do it
in TP would take less than say 600 lines.

Here is one way of tackling the problem:

First, make some way of representing the state of the puzzle.  In Scheme
terms, something like ((9 14 10 4)(6 1 8 12)(2 15 0 5)(11 7 3 13)), or a
4x4 array in TP.

Second, build a function which, given a transformation like "u","d","l"
or "r", it takes a puzzle state and returns the state of the puzzle
AFTER that transformation.

Next, you start with a few lists.  One list contains all the states
visited so far, so it starts off with only one item, the initial state.
Then to solve it, you use recursion to search the tree of possible
transformations until you either find some combination of
transformations which results in the final state, or you are left with
no states after any transform which have not occured before.  In effect,
you'll be applying "u,d,l,r,uu,ud,ul,ur,du,dd,dl,dr,lu,ld,ll,lr,ru,rd,rl,
rr,uuu,uud, etc" to the initial state, and seeing if you get the final
state.  The order of the letters you try gets read off when your
recursion unwinds, and this gives the moves you need.

Note that this is a VERY computationally intensive algorithm if the
solution is non-trivial (it is of the order O(4^n)), and only uses a
simple heuristic - that is, it doesn't search parts of the search tree
that have already been searched.  What it WON'T do is infalibly see
that a simple move would be shorter than a longer set.

Hmm.  Other thoughts:

Take each state in the list in turn:
  Apply in turn, u,d,l and r.
  Put the resultant states in another list.
  Are any of the resultant states the final state?  If so, unravel the
  recursion reading off the moves.
  If not, add the resultant states to the list of ones to search next
  time, unless they already occur, ie, no duplicates.

Having said all that, I think it IS possible to do it in TP (although
not a wise thing to do).  I must admit I am tempted, and if I get around
to doing it, my preferred method to use would be to hijack the
TSortedCollections from Turbo Vision.

Hope this helps.

Mitch.