Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!dali.cs.montana.edu!milton!uw-beaver!ubc-cs!cpsc.ucalgary.ca!!kudu From: kudu@.ucalgary.ca (Gopi Kuduvalli, The Gemini) Newsgroups: comp.ai Subject: Re: 15-puzzle Message-ID: <1990Oct5.212749.5615@cpsc.ucalgary.ca> Date: 5 Oct 90 21:27:49 GMT References: <1491@meaddata.meaddata.com> <20930@well.sf.ca.us> Sender: news@cpsc.ucalgary.ca Reply-To: kudu@eneli.UUCP (Gopi Kuduvalli, The Gemini) Distribution: comp Organization: The University of Calgary Lines: 30 Nntp-Posting-Host: eneli.enel.ucalgary.ca In article coleman@moby.cs.ucla.edu (Michael Coleman) writes: >nagle@well.sf.ca.us (John Nagle) writes: >> One simple approach is to get the top row and left column in order by >>suitable manipulation. Having done this, which is easy, you have reduced the >>4x4 15-puzzle to the 3x3 8-puzzle. Repetition of this process reduces the >>8-puzzle to the 2x2 3-puzzle. A final repetition solves the puzzle. >>Who needs AI? > >It is not clear (to me) from inspection that this will necessarily always >work. Is it always the case that after you set up the top row and left >column, you can reach the final configuration without changing them? It may >be true for 4x4, but I don't think it is true for the 3x3 puzzle. > > >--Mike >-- The algorithm *certainly* fails at the 2x2 stage. (Cursory inspection would show this). Since it fails for atleast one case, it is not a *generalized* solution. -- Gopi Gopinath R. Kuduvalli = "In view of the stupidity of the majority Email : kudu@enel.UCalgary.CA * of the people, a widely held opinion is kudu@uncamyr.UCalgary.CA = more likely to be foolish than sensible." #include * - Bert Russell in 'Marriage and morals'