home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / ai / 3402 < prev    next >
Encoding:
Text File  |  1992-09-10  |  2.2 KB  |  51 lines
  1. Newsgroups: comp.ai
  2. Path: sparky!uunet!mcsun!sun4nl!rlmix1.rulimburg.nl!cs.rulimburg.nl!allis
  3. From: allis@cs.rulimburg.nl (Victor Allis)
  4. Subject: Re: 8 Puzzle (Is it connected)
  5. Message-ID: <1992Sep10.082350.10442@cs.rulimburg.nl>
  6. Organization: University of Limburg
  7. References: <babraham.3.715849833@unpcs1.cs.unp.ac.za> <1992Sep7.155720.19507@CSD-NewsHost.Stanford.EDU> <mgv.715889137@ash.cs.scarolina.edu>
  8. Date: Thu, 10 Sep 92 08:23:50 GMT
  9. Lines: 40
  10.  
  11. >The proof goes like this:
  12.  
  13. >1) A single move is an exchange between the empty space and one other
  14. >   piece.
  15.  
  16. >2) The empty space will, in a single move, change from a black square
  17. >   to a white or vice versa.
  18.  
  19. >3) Thus any sequence of moves that leaves the empty space on the same
  20. >   colour will have to be even.
  21.  
  22. >4) An even number of moves corresponds to an even number of exchanges
  23. >   of pieces (including the empty space).
  24.  
  25. >5) This can be seen from a result about permutations, stating that if
  26. >   the permutation can be achieved by an even number of exchanges, no
  27. >   odd number of exhanges will achieve the same permutation (and vice
  28. >   versa). The permotation is said to have even or odd parity.
  29.  
  30. >Thus, a solution exist if the empty space starts and ends on the same
  31. >colour and an even number of exchanges is required or the empty space
  32. >starts and ends on opposite colours and an odd number of exchanges is
  33. >required.
  34.  
  35. The five steps shown above just state that there are AT LEAST two classes
  36. of positions which are closed to the operation of making moves, not that
  37. there are EXACTLY two classes. The conclusion thus is premature.
  38.  
  39. Note that a similar argument applies to Rubik's Cube, where there are not
  40. two but twelve classes. Or look at a variation of the 8-puzzle, where we
  41. have 4 squares on a line, with one of them empty. Clearly, we can only achieve
  42. four positions, while there are 24 possible permutations, thus there are
  43. six classes.
  44.  
  45. I remember once proving that if the board has a form such that it can be fully
  46. covered by 2x2 squares, with each of these small squares covering exactly
  47. four squares of the original puzzle (thus not extending over the edge of the
  48. puzzle), then there are EXACTLY two classes of positions.
  49.  
  50. Victor Allis.
  51.