home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / ai / 3362 < prev    next >
Encoding:
Text File  |  1992-09-08  |  1.0 KB  |  26 lines
  1. Newsgroups: comp.ai
  2. Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!t.Stanford.EDU!ginsberg
  3. From: ginsberg@t.Stanford.EDU (Matthew L. Ginsberg)
  4. Subject: Re: 8 Puzzle (Is it connected)
  5. Message-ID: <1992Sep7.155720.19507@CSD-NewsHost.Stanford.EDU>
  6. Sender: news@CSD-NewsHost.Stanford.EDU
  7. Organization: Computer Science Department, Stanford University
  8. References: <babraham.3.715849833@unpcs1.cs.unp.ac.za>
  9. Date: Mon, 7 Sep 1992 15:57:20 GMT
  10. Lines: 14
  11.  
  12. In article <babraham.3.715849833@unpcs1.cs.unp.ac.za> babraham@unpcs1.cs.unp.ac.za (Bobby Abraham) writes:
  13. >I recently gave the 8 puzzle to an Intro AI class.  I remember reading that 
  14. >the 15 puzzle was not solvable from any position.  In other words the graph 
  15. >of this problem was not connected.
  16. >
  17. >Can anyone tell me if the same applies to the 8 puzzle?  I would be 
  18. >interested in the proof as well.
  19.  
  20. None of these puzzles is connected.  If you consider the blank a tile,
  21. each legal move swaps two tiles and therefore obviously retains the "parity"
  22. of the overall position.
  23.  
  24.                     Matt Ginsberg
  25.  
  26.