Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!ucsd!pacbell.com!pacbell!well!nagle From: nagle@well.sf.ca.us (John Nagle) Newsgroups: comp.ai Subject: Re: 15-puzzle Message-ID: <21153@well.sf.ca.us> Date: 13 Oct 90 00:56:25 GMT References: <1491@meaddata.meaddata.com> <20930@well.sf.ca.us> <1990Oct5.212749.5615@cpsc.ucalgary.ca> Distribution: comp Lines: 26 kudu@.ucalgary.ca (Gopi Kuduvalli, The Gemini) writes: > The algorithm *certainly* fails at the 2x2 stage. (Cursory inspection >would show this). Since it fails for at least one case, it is not a >*generalized* solution. Only half of the possible starting states allow a solution for puzzles of this class. If you can reach a state in an 8-puzzle of the form 1 2 3 4 5 6 8 7 it is not possible to reach the state 1 2 3 4 5 6 7 8 and it is a special case of this general principle that you are observing when you report that the 2x2 3-puzzle is not solvable for some conditions. A full analysis of this I leave to someone more into mathematical recreations than I. It is probably covered in the works of Martin Gardner. John Nagle