home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / ai / 3385 < prev    next >
Encoding:
Internet Message Format  |  1992-09-08  |  2.3 KB
  1. Xref: sparky comp.ai:3385 rec.puzzles:6091
  2. Path: sparky!uunet!usc!wupost!darwin.sura.net!mojo.eng.umd.edu!mimsy!mimsy.umd.edu!nau
  3. From: nau@frabjous.cs.umd.edu (Dana Nau)
  4. Newsgroups: comp.ai,rec.puzzles
  5. Subject: Re: How do I solve the 8/15... Puzzle (was (Is it connected))
  6. Message-ID: <NAU.92Sep8225007@frabjous.cs.umd.edu>
  7. Date: 9 Sep 92 02:50:07 GMT
  8. References: <babraham.3.715849833@unpcs1.cs.unp.ac.za> <1992Sep7.155720.19507@CSD-NewsHost.Stanford.EDU> <mgv.715889137@ash.cs.scarolina.edu> <1992Sep8.041003.17677@ctr.columbia.edu>
  9. Sender: news@mimsy.umd.edu
  10. Followup-To: comp.ai
  11. Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
  12. Lines: 41
  13.  
  14.  
  15.    From: matthew@psych.psy.uq.oz.au (Matthew McDonald)
  16.    Newsgroups: comp.ai,rec.puzzles
  17.    Date: 8 Sep 92 04:10:03 GMT
  18.    Organization: Psychology Department, University of Queensland
  19.  
  20.        I believe there's a very simple algorithm for these puzzles
  21.    that will reach the solution in a reasonable number of moves.
  22.  
  23.        Could anybody tell me what algorithm is? (Most puzzle books
  24.    seem to only use Loyd's 15 puzzle to illustrate parity, saying that
  25.    actually solving the puzzle is trivial...)
  26.  
  27.        I can see plenty of ways of doing it but none of them are 
  28.    both simple and efficient for the larger versions of the puzzle.
  29.    (I do have a serious reason for wanting to know...)
  30.  
  31. It *is* trivial, provided that you are satisfied with a
  32. less-than-optimal solution (i.e., one that takes more than the least
  33. possible number of moves).  When I was a kid, I could solve the
  34. 15-puzzle in a few seconds, using the following simple-minded
  35. algorithm:
  36.  
  37.     for i = 1 to n (where n is the total number of tiles)
  38.     put tile i into its proper place,
  39.         while preserving the locations of tiles 1 through i-1
  40.  
  41. The only place there's any problem is that you have to temporarily
  42. disturb the tiles in the second-to-last row in order to get the tiles
  43. in the last row into their proper order.  But there's a simple
  44. procedure for that, too.  Try it a few times and you'll probably
  45. figure it out.
  46.  
  47. I haven't taken the time to do a proper complexity analysis, but I
  48. believe the total number of moves for this algorithm is no worse than
  49. O(n^4).
  50. --
  51.     Dana S. Nau
  52.     Computer Science Dept.        Internet:  nau@cs.umd.edu
  53.     University of Maryland        UUCP:  uunet!mimsy!nau
  54.     College Park, MD 20742        Telephone:  (301) 405-2684
  55.