Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!sdd.hp.com!elroy.jpl.nasa.gov!ucla-cs!moby!coleman From: coleman@moby.cs.ucla.edu (Michael Coleman) Newsgroups: comp.ai Subject: Re: 15-puzzle Message-ID: Date: 5 Oct 90 03:45:36 GMT References: <1491@meaddata.meaddata.com> <20930@well.sf.ca.us> Sender: news@CS.UCLA.EDU Distribution: comp Lines: 20 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. (In the terminology, I think I am asking whether or not this is a serializable subgoal.) --Mike -- Nothing's ever late when it's measured in Programmer's Time: ++ coleman | | | | | | | | | ++ @twinsun.com BEGIN 1/2 2/3 3/4 4/5 5/6 6/7 7/8 8/9 (etc) ++ @cs.ucla.edu