home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / cplus / 18552 < prev    next >
Encoding:
Text File  |  1992-12-30  |  1.9 KB  |  60 lines
  1. Newsgroups: comp.lang.c++
  2. Path: sparky!uunet!gatech!destroyer!ncar!csn!qwerty-gw.fsl.noaa.gov!kestrel.fsl.noaa.gov!bear
  3. From: bear@kestrel.fsl.noaa.gov (Bear Giles)
  4. Subject: Re: Intersting Data Structure
  5. Message-ID: <1992Dec30.183452.16715@fsl.noaa.gov>
  6. Sender: news@fsl.noaa.gov (USENET News System)
  7. Organization: Forecast Systems Labs, NOAA, Boulder, CO USA
  8. References: <BzMpBt.2Ip@cmcl2.nyu.edu> <rmartin.725130197@thor>
  9. Date: Wed, 30 Dec 1992 18:34:52 GMT
  10. Lines: 48
  11.  
  12. >reznick@acf3.nyu.edu (Daniel Reznick) writes:
  13. >
  14. >>Can anyone suggest a feasable Data Structure/Class Hierarchy to
  15. >>implement a Rubik's Cube?
  16.  
  17. What about a list of the rotations?  Each node would contain two
  18. pieces of information: the face (GREEN, WHITE, YELLOW, etc) and the
  19. rotation (1 to 3).  If necessary, you could fit this information into 5 bits!
  20.  
  21. Solving the cube would be easy -- follow the list backwards and 
  22. reverse each rotation.
  23.  
  24. Finding the representation of an existing cube would be more complex, but
  25. not as much as you might expect.  You would need an auxillary representation
  26. of the goal states (e.g., move subcube 4 into position 17; I think that
  27. uniquely identifies the goals but I'm not certain) and use the techniques
  28. developed for exchanging subcubes to satisfy all of the goals.  (I've seen
  29. a list of these rotations in "how-to-solve-it" books for the cube).
  30.  
  31. This will create a fairly long list of rotations, but shouldn't be too hard
  32. to implement.  Then run this list of rotations through a filter which
  33. optimizes moves.  For instance,
  34.  
  35.   GREEN 2
  36.   RED 2
  37.   GREEN 1
  38.  
  39. could be replaced with
  40.  
  41.   GREEN 3
  42.   RED 2
  43.  
  44. provided GREEN and RED are on opposite sides of the cube.  Obviously, if this
  45. was 
  46.  
  47.   GREEN 2
  48.   RED 2
  49.   GREEN 2
  50.  
  51. you could drop _both_ GREEN rotations since that has no net effect.
  52.  
  53. Of course, you can also reduce the list by optimizing your solution of the
  54. goal states -- you may be able to 'kill two birds with one stone' in many
  55. cases.
  56.  
  57.  
  58. Bear Giles
  59. bear@fsl.noaa.gov
  60.