home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / ai / 3401 < prev    next >
Encoding:
Text File  |  1992-09-10  |  1.6 KB  |  33 lines
  1. Newsgroups: comp.ai
  2. Path: sparky!uunet!sun-barr!cs.utexas.edu!torn!cunews!bws-pc.carleton.ca!bws
  3. From: bws@ccs.carleton.ca (Brian Sullivan)
  4. Subject: Re: How do I solve the 8/15... Puzzle (was (Is it connected))
  5. Message-ID: <bws.48@ccs.carleton.ca>
  6. Sender: news@cunews.carleton.ca (News Administrator)
  7. Organization: Carleton University
  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> <NAU.92Sep8225007@frabjous.cs.umd.edu> <mgv.716053877@ash.cs.scarolina.eOrganization: Carleton University
  9. Date: Thu, 10 Sep 1992 13:03:05 GMT
  10. Lines: 21
  11.  
  12. >       This does not indicate that SOLVING a generalized 15-puzzle
  13. >is NP-hard (it's far easier than that).  It indicates that finding the
  14. >OPTIMAL SOLUTION is NP-hard, which is something else again, and not
  15. >suprising.
  16.  
  17. >       An approach to solving such puzzles is as follows:
  18. >       1) Solve the top row.  Never modify the top row again.
  19. >       2) Solve the left column (less the top element).  Never
  20. >          modify the left column again.
  21. >       3) The puzzle has now been reduced from nxn to (n-1) x (n-1).
  22. >          If n>1, recurse, solving the remaining puzzle.
  23.  
  24. >Proving that this works is left to the reader.
  25.  
  26. >                                       John Nagle
  27.     
  28. This works fine when n > 2 (the last recursion). It is very probable
  29. that the last 3 tiles will be out of order. The only way to deal with
  30. this would be to disturb one of the other rows or columns.  
  31.  
  32. Sorry John, I've had a bad morning and am being picky.
  33.