home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / sci / math / 14728 < prev    next >
Encoding:
Internet Message Format  |  1992-11-10  |  2.2 KB
  1. Xref: sparky sci.math:14728 comp.theory:2388
  2. Newsgroups: rec.puzzle,sci.math,comp.theory
  3. Path: sparky!uunet!ukma!darwin.sura.net!zaphod.mps.ohio-state.edu!cs.utexas.edu!mercury.unt.edu!ponder.csci.unt.edu!ian
  4. From: ian@ponder.csci.unt.edu (Ian Parberry)
  5. Subject: the 16-puzzle
  6. Message-ID: <1992Nov10.212224.18874@mercury.unt.edu>
  7. Sender: usenet@mercury.unt.edu (UNT USENet Adminstrator)
  8. Organization: University of North Texas, Denton
  9. Date: Tue, 10 Nov 1992 21:22:24 GMT
  10. Lines: 33
  11.  
  12. The 16-puzzle consists of 15 tiles numbered 1-15, laid out on a 4x4
  13. grid with one hole.  A "move" consists of sliding one of the adjacent tiles
  14. into the hole.  The puzzle is set up by making a sequence of random moves,
  15. and then attempting to return the tiles to the "origin", defined to be
  16. row-major order with the hole in the bottom-right position.
  17.  
  18. The n^2 puzzle is the obvious generalization to an nxn grid.
  19.  
  20. I have 2 questions:
  21. 1.  What is the number of moves made by the best known algorithm?
  22. 2.  What is known about the group theory of the puzzle?
  23.  
  24. I have a naive algorithm for the n^2 puzzle that makes O(n^3) moves.
  25. I plan to use it in class to illustrate algorithm design techniques.
  26. The answer to Question 1 will tell me whether it is worthwhile
  27. putting in a lot of effort to analyze or improve the algorithm.
  28. The answer to Question 2 may help me to prove it correct.  It relies on a
  29. (yet unproven) conjecture about the generators of a certain group.  I'm
  30. too lazy to reinvent this from scratch, since I'd be very surprised if
  31. somebody hasn't already answered all of the "interesting" questions
  32. about the puzzle's group-theoretical foundations.  I remember seeing
  33. a paper that described all of the permutations that can be reached from
  34. the origin, but I've lost track of the reference.  This may contain the
  35. algebraic tools that I need.  Any pointers to this and other references
  36. would be appreciated.  The only papers I have found in the library use AI
  37. techniques and hand-waving analyses.
  38.  
  39. Please respond by email.  I will summarize to the net if there is
  40. sufficient interest.
  41. ____
  42. Ian Parberry (ian@ponder.csci.unt.edu)
  43. Dept. of Computer Sciences, Univ. of North Texas
  44. "Bureaucracy is expanding to meet the needs of an expanding bureaucracy"
  45.