home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / sys / amiga / programmer / 6391 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.5 KB  |  69 lines
  1. Path: news.ao.net!news
  2. From: Jude Anthony <jude@p3.enzian.com>
  3. Newsgroups: comp.sys.amiga.programmer
  4. Subject: Re: scramble game algorithm?
  5. Date: Wed, 27 Mar 1996 10:22:23 -0800
  6. Organization: Enzian Technology
  7. Message-ID: <3159875F.7951@p3.enzian.com>
  8. References: <3157B388.3F20@sapiens.com>
  9. NNTP-Posting-Host: 204.240.62.132
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=us-ascii
  12. Content-Transfer-Encoding: 7bit
  13. X-Mailer: Mozilla 2.0 (Win16; I)
  14.  
  15. Avi L. wrote:
  16. > Hi there, i'm trying to figure out an algorithm for solving the
  17. > famous scramble game, i've succeeded in solving most of the game
  18. > however there are situations which require more logic added in
  19. > order to search for a better path to move the pieces around. 
  20. > especially the following situation is troublesome:
  21. > 
  22. > 1 2 3 4
  23. > 5 6 7 8
  24. > 9 10 11 12
  25. > 14 15 13 -1.
  26. > 
  27. > -1 == empty space.
  28. > how do you get the 13 piece to its proper place and then manage
  29. > to get the other pieces back to thier original position and thus
  30. > solve this damn game.
  31. > i know how to solve the game by hand however translating
  32. > it to software code isn't so straight forward. guess
  33. > life's too complex for that, eh?!
  34. > thank you in advance for any information.
  35.  
  36. You need a different algorythm, I think.  Forget the logic; this can be 
  37. easily solved with a simple tree.  Since there is no position from which 
  38. more than four pieces can move into the empty square, you create a tree 
  39. with four branches at each node.  A structure with four pointers will be 
  40. necessary; I would also include an array specifying the board position 
  41. after the move has been made and an integer specifying the array index of 
  42. the piece moved:
  43.  
  44. struct node_TAG
  45. {
  46.    int moveme;
  47.    int board[4][4];
  48.    struct node_TAG *next[4];
  49. } node;
  50.  
  51. Write a recursive function to tranverse this tree.  Every step, move each 
  52. possible tile into the space and create a new node for the new board 
  53. position.  Compare the node to previous board configurations to make sure 
  54. you're not duplicating your work.  Stop and return when there are no 
  55. non-repetetive board configurations, or you reach a node with a solved 
  56. board.
  57.  
  58. If you actually create the entire tree (instead of stopping when you 
  59. reach your first solve), this algorythm gives you the added bonus of 
  60. being able to find the fewest moves necessary to solve the board.
  61.  
  62. Thanks for making me think of this problem.  I may go and write it up 
  63. myself, for a practical exercise.  I hope this solution is more useful to 
  64. you.
  65.  
  66. Later,
  67. GreyFox
  68. jude@p3.enzian.com
  69.