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