>From: gerhard@vmars.tuwien.ac.at (Gerhard Fohler) Newsgroups: comp.ai Subject: Re: 15-puzzle Date: 2 Oct 90 14:18:48 GMT gordon@meaddata.com (Gordon Edwards) writes: >I would like references on the 15-puzzle and various approaches to solving it. >I know Pohl used it when performing his bi-directional and heuristic search >work. A well-known algorithm capable of solving the 15-puzzle on existing machines is depth-first iterative deepening by Richard Korf(1). As a summary of algorithms for search problems I would recommend Korf (2), which briefly addresses future directions for research on search also. At our department we use a modified version of this algorithm for finding schedules for distributed hard real-time systems, a NP hard problem. Our experiences so far are quite promissing. Gerhard Fohler -------------- (1) Korf, R.E., 1985: Depth-first iterative deepening: An optimal admissible tree search, Artificial Intelligence. 27(1):97-109 (2) Korf, R.E., 1988: Search: A Survey of Recent Results, in: Shrobe, H.E.: Exploring Artificial Intelligence, Survey Talks from the National Conferences on Artificial Intelligence, Morgan Kaufmann Publishers, Inc., San Mateo, California ------------------------------------------------------------------------- >From: pmm@acsu.buffalo.edu (patrick m mullhaupt) Newsgroups: comp.ai Subject: Re: 15-puzzle Date: 2 Oct 90 18:14:52 GMT In article <1491@meaddata.meaddata.com> meaddata!gordon@uunet.uu.net writes: >I would like references on the 15-puzzle and various approaches to solving it. > >Thanks, >-- Gordon (gordon@meaddata.com) A good reference for information on the 8-puzzle, (little brother of the 15-puzzle), is: Problem Solving in Artificial Intelligence, by Nils Nilsson (1971) I'm citing this from memory, so it may not be exactly correct, but it's correct enough so that you can look it up. To find other information on the 15-puzzle, it might help to look under 8-puzzle, since I believe the 8-puzzle is the more common variant. Hope this helps, Patrick Mullhaupt ------------------------------------------------------------------------- >From: nagle@well.sf.ca.us (John Nagle) Newsgroups: comp.ai Subject: Re: 15-puzzle Date: 4 Oct 90 07:34:20 GMT gordon@meaddata.com (Gordon Edwards) writes: >I would like references on the 15-puzzle and various approaches to solving it. 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? John Nagle ------------------------------------------------------------------------- >From: lindsay@comp.vuw.ac.nz (Lindsay Groves) Newsgroups: comp.ai Subject: Re: 15-puzzle Date: 5 Oct 90 01:02:38 GMT Organization: Computer Science Dept, Victoria University, Wellington, NEW ZEALAND In article <20930@well.sf.ca.us>, nagle@well.sf.ca.us (John Nagle) writes: |> gordon@meaddata.com (Gordon Edwards) writes: |> |> >I would like references on the 15-puzzle and various approaches to |> solving it. |> |> 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? |> |> John Nagle I'd like to see a system that, given a description of the puzzle, could find this way of solving the puzzle, rather than just finding *a* solution. Then I'd think there might be something intelligent going on! Lindsay ------------------------------------------------------------------------- >From: coleman@moby.cs.ucla.edu (Michael Coleman) Newsgroups: comp.ai Subject: Re: 15-puzzle Date: 5 Oct 90 03:45:36 GMT 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 ------------------------------------------------------------------------- >From: houpt@svax.cs.cornell.edu (Charles E. Houpt) Newsgroups: comp.ai Subject: Re: 15-puzzle Date: 5 Oct 90 06:12:13 GMT Organization: Cornell Univ. CS Dept, Ithaca NY One method commonly used by humans to solve the 8 puzzle (and the 15 puzzle) is the Round-About or Merry-Go-Round method. This method has two phases. In the first you find and extend the longest sequence of tiles around the outer ring of squares. You do this by "parking" a tile in the center square and circulating the other tiles around until there is a gap to insert the parked tile into the sequence. Once you have all the tiles in the correct order (but not necessarily the correct positions), you start the second phase. In the second phase you park one tile and rotate the other tiles into their correct position. This method can be extended to the 15 puzzle by using two rings, an inner 4 square ring and an outer 12 square ring. Both rings use the other to "park" tiles. Despite the fact that this is a common method among humans, there are very few AI programs that solve the 8-puzzle this way, and there are none that can learn the Merry-Go-Round method. I find this method interesting because it solves the problem of conflicting subgoals by modifying the goals. So, instead of trying to get the tiles into their correct position all at once, you first get them into a correct sequence, and only then do you move them into their correct positions. Michie describes this method in: Michie, D. "Strategy-Building with the Graph Traverser" in Machine Intelligence 1, N. L. Collins and D. Michie (eds), American Elsevier, NY 1967 pg135-152. -Chuck Houpt P.S. Here an complete example: 6 2 3 Notice the sequence 2-3-4-5 1 0 4 So you first park 1 in the center and insert 7 8 5 it before the 2. RULLDDRU 6 1 2 7 0 3 Now park the 7 and insert it after the 5. 8 5 4 RDLLUURD 1 2 3 Now every tile except the 6 is in the correct order. 6 0 4 So park 6 and rotate 8 and 7 to their final position. 8 7 5 RULD 1 2 3 Solved! 8 0 4 7 6 5 In this case the second phase was short (just moving 8 and 7), but this is not always the case. For example: 7 8 0 6 4 1 5 3 2 Requires a lot of rotation: UURRDDLLUURRDDLLUR. ------------------------------------------------------------------------- >From: druby@ics.uci.edu (David Ruby) Newsgroups: comp.ai Subject: Re: 15-puzzle Date: 5 Oct 90 17:35:44 GMT Organization: UC Irvine Department of ICS >In article <20930@well.sf.ca.us>, nagle@well.sf.ca.us (John Nagle) writes: >|> gordon@meaddata.com (Gordon Edwards) writes: >|> >|> >I would like references on the 15-puzzle and various approaches to >|> solving it. >|> >|> 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? >|> >|> John Nagle >I'd like to see a system that, given a description of the puzzle, could >find this way of solving the puzzle, rather than just finding *a* >solution. Then I'd think there might be something intelligent going >on! >Lindsay SteppingStone, a learning problem solver, does solve the tile sliding puzzle is a manner very similar to this. It begins by ordering the subgoals (tiles to be placed) using a general heuristic called openness. The effect of this ordering is to set up the tiles along the upper row and left hand column to be solved first, reducing the problem difficulty as mentioned. A means-ends analysis like approach is then used to try and place the tiles without undoing them once solved. With the orderings produced using the openness heuristic, there is only one tile along the upper row and one tile along the left hand column that can't be solved in this manner. When a tile cannot be solved under this assumption, the system searches through its knowledge to see if it has an approach for solving this type of subproblem. Knowledge is stored as a new sequence of subgoals for leading the means-ends analysis component to a state where all of the previously solved subgoals are still solved and the current subgoal is also solved. When the system does not have knowledge for solving a particular subgoal it falls back on a local search approach. After solving the subproblem, the solution is generalized into a new sequence of subgoals for reuse on other problems. Note, that the system only checks its knowledge when it cannot solve a subgoal (tile) under its simplifying assumption. Unlike previous learning problem solvers that learn control rules or macro-operators, SteppingStone learns sequences of subgoals or stepping stones. Here a subgoal is a partial state description. The stepping stones are used by the means-ends analysis component to lead the system through difficult portions of the problem. SteppingStone solved tile sliding problems ranging in size from the 3x3 8-puzzle to the 6x6 35-puzzle. The results were published in the article: "Learning subgoal sequences for planning" by David Ruby and Dennis Kibler in the proceeding of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89). More recently SteppingStone has been used to learn to optimize logic synthesis problems. The goal is now to demonstrate it on a series of benchmarks in the logic synthesis community as well as extend it to other domains. David Ruby Graduate Student University of California, Irvine ------------------------------------------------------------------------- >From: mmh@cs.qmw.ac.uk (Matthew Huntbach) Newsgroups: comp.ai Subject: Re: 15-puzzle Date: 10 Oct 90 16:58:34 GMT Organization: Computer Science Dept, QMW, University of London, UK. In article <46717@cornell.UUCP> houpt@svax.cs.cornell.edu (Charles E. Houpt) writes: > > One method commonly used by humans to solve the 8 puzzle (and the 15 >puzzle) is the Round-About or Merry-Go-Round method. All these methods involving macro-operators and subgoals are not guaranteed to give the optimal solution. If you want the least number of moves to reach the goal you must still employ the standard search techniques. Matthew Huntbach ------------------------------------------------------------------------- >From: kudu@.ucalgary.ca (Gopi Kuduvalli, The Gemini) Newsgroups: comp.ai Subject: Re: 15-puzzle Date: 5 Oct 90 21:27:49 GMT Organization: The University of Calgary 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' ------------------------------------------------------------------------- >From: nagle@well.sf.ca.us (John Nagle) Newsgroups: comp.ai Subject: Re: 15-puzzle Date: 13 Oct 90 00:56:25 GMT 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 ------------------------------------------------------------------------- >From: sjr87@ecs.soton.ac.uk (Simon Roberts) Newsgroups: comp.ai Subject: 8-puzzle heuristic needed Date: 29 Nov 90 10:37:16 GMT I am currently engaged in writing a PROLOG program to solve the 8-puzzle, ie get 123 456 78 from any starting configuration. I have been using the heuristic: h = d + (3*s) to solve it but I run into problems. Can anyone supply me with an appropriate formula to apply to the problem, along with any relevant scoring criteria?? I would be most grateful if you could email rather than post to the address below. Regards, Zak Roberts : sjr87@ecs.soton.ac.uk (+ nsfnet-relay.ac.uk) ------------------------------------------------------------------------- >From: sjr87@ecs.southampton.ac.uk (Simon Roberts) Newsgroups: comp.ai Subject: 8-puzzle (repost) Date: 30 Nov 90 20:03:06 GMT Organization: The University of Southampton, Hampshire, UK. Sorry for reposting this, but I'm not sure if our news software sent it out the first time. I am having problems with writing a PROLOG problem to solve the 8-puzzle from any starting goal to: 123 456 78 I have up to now been using the heuristic d + 3*s which is normally used for the goal: 123 8 4 765 But this is not so good for the first case. Can anyone push me in the right direction as how to tackle this problem to achieve the optimal solution?? I would be most grateful. Regards, Simon #################################################################### # -- Simon Roberts -- # #################################################################### # JANET : sjr87@uk.ac.soton.ecs # # INTERNET : sjr87@ecs.soton.ac.uk (+ nsfnet-relay.ac.uk) # #################################################################### ------------------------------------------------------------------------- >From: eiverson@nmsu.edu (Eric Iverson) Newsgroups: comp.ai Subject: Solving the 8 puzzle through hill climbing Date: 18 Aug 92 08:06:23 GMT Organization: Computing Research Lab Below is a brief series of steps to solve one configuration of the 8 puzzle. I am looking for a fitness function such that each successive step would be judged to be more fit than its predecessor, thus enabling hill climbing. I realize that hill climbing is not the best way to solve the 8 puzzle, but that's what I want to do. (No, this isn't homework. It's a question in Rich's textbook that I just happen to be rereading.) Any suggestions would be appreciated. [1,2,3] [8,5,6] [4,7,*] [1,2,3] [8,5,*] [4,7,6] [1,2,3] [8,*,5] [4,7,6] [1,2,3] [*,8,5] [4,7,6] [1,2,3] [4,8,5] [*,7,6] [1,2,3] [4,8,5] [7,*,6] [1,2,3] [4,*,5] [7,8,6] [1,2,3] [4,5,*] [7,8,6] [1,2,3] [4,5,6] [7,8,*] -- ------------------------------------------------------------------------ Eric Iverson Internet: eiverson@nmsu.edu Computing Research Lab Box 30001/3CRL Life is something to do when New Mexico State University you can't get to sleep. Las Cruces, NM 88003-0001 -Fran Lebowitz VOICE: (505) 646-5711 FAX: (505) 646-6218 ------------------------------------------------------------------------- >From: babraham@unpcs1.cs.unp.ac.za (Bobby Abraham) Newsgroups: comp.ai Subject: 8 Puzzle (Is it connected) Date: 7 Sep 92 07:10:34 GMT Organization: Dept. Computer Science, UNP I recently gave the 8 puzzle to an Intro AI class. I remember reading that the 15 puzzle was not solvable from any position. In other words the graph of this problem was not connected. Can anyone tell me if the same applies to the 8 puzzle? I would be interested in the proof as well. Thank you ------------------------------------------------------------------- Bobby Abraham Dept. of Computer Science University of Natal, Pietermaritzburg email - babraham@unpcs1.cs.unp.ac.za abraham@unpsun1.cc.unp.ac.za ------------------------------------------------------------------- >From: ginsberg@t.Stanford.EDU (Matthew L. Ginsberg) Newsgroups: comp.ai Subject: Re: 8 Puzzle (Is it connected) Date: 7 Sep 92 15:57:20 GMT Organization: Computer Science Department, Stanford University In article babraham@unpcs1.cs.unp.ac.za (Bobby Abraham) writes: >I recently gave the 8 puzzle to an Intro AI class. I remember reading that >the 15 puzzle was not solvable from any position. In other words the graph >of this problem was not connected. > >Can anyone tell me if the same applies to the 8 puzzle? I would be >interested in the proof as well. None of these puzzles is connected. If you consider the blank a tile, each legal move swaps two tiles and therefore obviously retains the "parity" of the overall position. Matt Ginsberg ------------------------------------------------------------------------- >From: mgv@cs.scarolina.edu (Marco Valtorta) Newsgroups: comp.ai Subject: Re: 8 Puzzle (Is it connected) Date: 7 Sep 92 18:05:37 GMT Organization: USC Department of Computer Science ginsberg@t.Stanford.EDU (Matthew L. Ginsberg) writes: >In article babraham@unpcs1.cs.unp.ac.za (Bobby Abraham) writes: >>I recently gave the 8 puzzle to an Intro AI class. I remember reading that >>the 15 puzzle was not solvable from any position. In other words the graph >>of this problem was not connected. >> >>Can anyone tell me if the same applies to the 8 puzzle? I would be >>interested in the proof as well. >None of these puzzles is connected. If you consider the blank a tile, >each legal move swaps two tiles and therefore obviously retains the "parity" >of the overall position. > Matt Ginsberg A while ago, Torben Mogensen gave the argument in more detail. (What follows is e-mail he sent me relating to his posting, rather than his actual posting to comp.ai.) For the trivia enthusiast, the argument was first made by William E. Story in Woolsey Johnson, Wm. and William E. Story. "Notes on the "15" Puzzle." _American Journal of Mathematics, 2 (1879), 397-404. Marco Valtorta, Assistant Professor usenet: ...!ncrcae!usceast!mgv Department of Computer Science internet: mgv@usceast.cs.scarolina.edu University of South Carolina tel.: (1)(803)777-4641 Columbia, SC 29208 tlx: 805038 USC U.S.A. fax: (1)(803)777-3767 usenet from Europe: ...!mcvax!uunet!ncrlnk!ncrcae!usceast!mgv ------------------------------------------------------------------------- Date: Thu, 10 Oct 91 11:18:02 +0100 >From: Torben AEgidius Mogensen To: mgv@usceast.cs.scarolina.edu Subject: Re: Re: Tiled Puzzle Problem for 2x2 or 5x5 square >Could you please sketch the argument or give a reference to the proof >of the result? The argument I gave you was actually slightly incomplete: it requires that the empty space is in the same position in the initial and final states. Or, more precisely, that the empty space is an even number of squares away from the initial position (the initial and final squares would have the same colour on a chess board). The proof goes like this: 1) A single move is an exchange between the empty space and one other piece. 2) The empty space will, in a single move, change from a black square to a white or vice versa. 3) Thus any sequence of moves that leaves the empty space on the same colour will have to be even. 4) An even number of moves corresponds to an even number of exchanges of pieces (including the empty space). 5) This can be seen from a result about permutations, stating that if the permutation can be achieved by an even number of exchanges, no odd number of exhanges will achieve the same permutation (and vice versa). The permotation is said to have even or odd parity. Thus, a solution exist if the empty space starts and ends on the same colour and an even number of exchanges is required or the empty space starts and ends on opposite colours and an odd number of exchanges is required. Torben Mogensen (torbenm@diku.dk) ------------------------------------------------------------------------- >From: matthew@psych.psy.uq.oz.au (Matthew McDonald) Newsgroups: comp.ai,rec.puzzles Subject: How do I solve the 8/15... Puzzle (was (Is it connected)) Date: 8 Sep 92 04:10:03 GMT Organization: Psychology Department, University of Queensland Marco Valtorta writes: > ginsberg@t.Stanford.EDU (Matthew L. Ginsberg) writes: > > >In article babraham@unpcs1.cs.unp.ac.za (Bobby Abraham) writes: > >>I recently gave the 8 puzzle to an Intro AI class. I remember reading that > >>the 15 puzzle was not solvable from any position. In other words the graph > >>of this problem was not connected. [...] I believe there's a very simple algorithm for these puzzles that will reach the solution in a reasonable number of moves. Could anybody tell me what algorithm is? (Most puzzle books seem to only use Loyd's 15 puzzle to illustrate parity, saying that actually solving the puzzle is trivial...) I can see plenty of ways of doing it but none of them are both simple and efficient for the larger versions of the puzzle. (I do have a serious reason for wanting to know...) I don't think this is of general interest, but I'll gladly summarise if anyone wants. =-=- Matthew McDonald matthew@psych.psy.uq.oz.au ------------------------------------------------------------------------- >From: nau@frabjous.cs.umd.edu (Dana Nau) Newsgroups: comp.ai,rec.puzzles Subject: Re: How do I solve the 8/15... Puzzle (was (Is it connected)) Date: 9 Sep 92 02:50:07 GMT Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742 From: matthew@psych.psy.uq.oz.au (Matthew McDonald) Newsgroups: comp.ai,rec.puzzles Date: 8 Sep 92 04:10:03 GMT Organization: Psychology Department, University of Queensland I believe there's a very simple algorithm for these puzzles that will reach the solution in a reasonable number of moves. Could anybody tell me what algorithm is? (Most puzzle books seem to only use Loyd's 15 puzzle to illustrate parity, saying that actually solving the puzzle is trivial...) I can see plenty of ways of doing it but none of them are both simple and efficient for the larger versions of the puzzle. (I do have a serious reason for wanting to know...) It *is* trivial, provided that you are satisfied with a less-than-optimal solution (i.e., one that takes more than the least possible number of moves). When I was a kid, I could solve the 15-puzzle in a few seconds, using the following simple-minded algorithm: for i = 1 to n (where n is the total number of tiles) put tile i into its proper place, while preserving the locations of tiles 1 through i-1 The only place there's any problem is that you have to temporarily disturb the tiles in the second-to-last row in order to get the tiles in the last row into their proper order. But there's a simple procedure for that, too. Try it a few times and you'll probably figure it out. I haven't taken the time to do a proper complexity analysis, but I believe the total number of moves for this algorithm is no worse than O(n^4). -- Dana S. Nau Computer Science Dept. Internet: nau@cs.umd.edu University of Maryland UUCP: uunet!mimsy!nau College Park, MD 20742 Telephone: (301) 405-2684 ------------------------------------------------------------------------- >From: mgv@cs.scarolina.edu (Marco Valtorta) Newsgroups: comp.ai Subject: Re: How do I solve the 8/15... Puzzle (was (Is it connected)) Date: 9 Sep 92 15:51:17 GMT Organization: USC Department of Computer Science nau@frabjous.cs.umd.edu (Dana Nau) writes: > From: matthew@psych.psy.uq.oz.au (Matthew McDonald) > Newsgroups: comp.ai,rec.puzzles > Date: 8 Sep 92 04:10:03 GMT > Organization: Psychology Department, University of Queensland > I believe there's a very simple algorithm for these puzzles > that will reach the solution in a reasonable number of moves. > Could anybody tell me what algorithm is? (Most puzzle books > seem to only use Loyd's 15 puzzle to illustrate parity, saying that > actually solving the puzzle is trivial...) >It *is* trivial, provided that you are satisfied with a >less-than-optimal solution (i.e., one that takes more than the least >possible number of moves). When I was a kid, I could solve the >15-puzzle in a few seconds, using the following simple-minded >algorithm: > for i = 1 to n (where n is the total number of tiles) > put tile i into its proper place, > while preserving the locations of tiles 1 through i-1 >The only place there's any problem is that you have to temporarily >disturb the tiles in the second-to-last row in order to get the tiles >in the last row into their proper order. But there's a simple >procedure for that, too. Try it a few times and you'll probably >figure it out. >I haven't taken the time to do a proper complexity analysis, but I >believe the total number of moves for this algorithm is no worse than >O(n^4). >-- > Dana S. Nau > Computer Science Dept. Internet: nau@cs.umd.edu > (I do have a serious reason for wanting to know...) > University of Maryland UUCP: uunet!mimsy!nau > College Park, MD 20742 Telephone: (301) 405-2684 Since there is interest in this, maybe it helps to repost a recent message. Marco Valtorta, Assistant Professor usenet: ...!ncrcae!usceast!mgv Department of Computer Science internet: mgv@usceast.cs.scarolina.edu University of South Carolina tel.: (1)(803)777-4641 Columbia, SC 29208 tlx: 805038 USC U.S.A. fax: (1)(803)777-3767 usenet from Europe: ...!mcvax!uunet!ncrlnk!ncrcae!usceast!mgv >From: nagle@netcom.com (John Nagle) Newsgroups: comp.ai Subject: Re: generalized 15-puzzle is NP-hard (NOT!) Date: 1 Aug 92 20:22:15 GMT Organization: Netcom - Online Communication Services (408 241-9760 guest) chan@tutics.tut.ac.jp (Chan Namkiu) writes: >In the paper titled _Finding a shortest solution for the nxn extension >of the 15-puzzle is intractable_ appeared in AAAI-86, D. Ratner and >M. Warmuth have argued that finding an optimal solution for general >nxn board puzzle is NP-hard. Specifically, they have shown that >the following decision problem (nPUZ) is NP-complete. > Instance: Two nxn boards and a bound k. > Question: Is there a solution for transforming the first board > to the second board requiring less than k moves? This does not indicate that SOLVING a generalized 15-puzzle is NP-hard (it's far easier than that). It indicates that finding the OPTIMAL SOLUTION is NP-hard, which is something else again, and not suprising. An approach to solving such puzzles is as follows: 1) Solve the top row. Never modify the top row again. 2) Solve the left column (less the top element). Never modify the left column again. 3) The puzzle has now been reduced from nxn to (n-1) x (n-1). If n>1, recurse, solving the remaining puzzle. Proving that this works is left to the reader. John Nagle ------------------------------------------------------------------------- >From: bws@ccs.carleton.ca (Brian Sullivan) Newsgroups: comp.ai Subject: Re: How do I solve the 8/15... Puzzle (was (Is it connected)) Date: 10 Sep 92 13:03:05 GMT Organization: Carleton University > This does not indicate that SOLVING a generalized 15-puzzle >is NP-hard (it's far easier than that). It indicates that finding the >OPTIMAL SOLUTION is NP-hard, which is something else again, and not >suprising. > An approach to solving such puzzles is as follows: > 1) Solve the top row. Never modify the top row again. > 2) Solve the left column (less the top element). Never > modify the left column again. > 3) The puzzle has now been reduced from nxn to (n-1) x (n-1). > If n>1, recurse, solving the remaining puzzle. >Proving that this works is left to the reader. > John Nagle This works fine when n > 2 (the last recursion). It is very probable that the last 3 tiles will be out of order. The only way to deal with this would be to disturb one of the other rows or columns. Sorry John, I've had a bad morning and am being picky. ------------------------------------------------------------------------- >From: allis@cs.rulimburg.nl (Victor Allis) Newsgroups: comp.ai Subject: Re: 8 Puzzle (Is it connected) Date: 10 Sep 92 08:23:50 GMT Organization: University of Limburg >The proof goes like this: >1) A single move is an exchange between the empty space and one other > piece. >2) The empty space will, in a single move, change from a black square > to a white or vice versa. >3) Thus any sequence of moves that leaves the empty space on the same > colour will have to be even. >4) An even number of moves corresponds to an even number of exchanges > of pieces (including the empty space). >5) This can be seen from a result about permutations, stating that if > the permutation can be achieved by an even number of exchanges, no > odd number of exhanges will achieve the same permutation (and vice > versa). The permotation is said to have even or odd parity. >Thus, a solution exist if the empty space starts and ends on the same >colour and an even number of exchanges is required or the empty space >starts and ends on opposite colours and an odd number of exchanges is >required. The five steps shown above just state that there are AT LEAST two classes of positions which are closed to the operation of making moves, not that there are EXACTLY two classes. The conclusion thus is premature. Note that a similar argument applies to Rubik's Cube, where there are not two but twelve classes. Or look at a variation of the 8-puzzle, where we have 4 squares on a line, with one of them empty. Clearly, we can only achieve four positions, while there are 24 possible permutations, thus there are six classes. I remember once proving that if the board has a form such that it can be fully covered by 2x2 squares, with each of these small squares covering exactly four squares of the original puzzle (thus not extending over the edge of the puzzle), then there are EXACTLY two classes of positions. Victor Allis. ------------------------------------------------------------------------- >From: peter@icce.rug.nl () Subject: Heuristic search and the 8 puzzle Organization: The ICCE Experience Date: Wed, 29 Sep 1993 13:21:10 GMT I'm currently implementing some search algorithms in C++. For testing purposes I use the 8 puzzle. The problem is what heuristic to use for best search. The standard heuristic used in the 8 puzzle problem as described in e.g. 'Nilsson, Problem-solving methods in artificial intelligence' is the following: h(n) = P(n) + 3S(n) Where P(n) is the sum of distances that each tile is from "home" and S(n) is a 'sequence score': every noncentral tile gets 2 points when it's not followed by its proper successor and 0 if it is, a piece in the centre scores 1. So far so good. When I implemented this I got far different results than Nilsson writes. Next I checked Bratko, who also uses the same heuristic, but again I didn't get the same result. The problem is not just that nodes get different values, but (as a consequence of that) a different path is followed (in one case according to Nilsson and Bratko a solution is found in 18 steps while my program needs 22). I think the problem is in S(n), what exactly does it mean that a tile is followed by another tile, does this also apply to edges? and what about the last tile? (Bratko solves this apparently by pretending that the last tile is 'followed' by the first, but even when I followed his scheme I didn't get the same result). So...my question is, has anyone worked on this before, if so, how did you compute the sequence score? Or if you never of a better heuristic (this one isn't admissible) let me know! Thanks in advance! Peter Bouthoorn ------------------------------------------------------------------------- >From: mgv@cs.scarolina.edu (Marco Valtorta) Subject: Re: Heuristic search and the 8 puzzle Organization: USC Department of Computer Science Date: 29 Sep 93 18:02:56 GMT peter@icce.rug.nl () writes: >Hi, >I'm currently implementing some search algorithms in C++. For testing >purposes I use the 8 puzzle. The problem is what heuristic to >use for best search. The standard heuristic used in the 8 puzzle problem > Or if you never of a better heuristic (this >one isn't admissible) let me know! >Thanks in advance! >Peter Bouthoorn Two very good admissible heuristics are the Linear Conflict heuristic of O.~Hansson, A.~Mayer, and M.~Yung. \newblock Relaxed Models Yield Powerful Admissible Heuristics. \newblock {\it Information Sciences}, to appear. [This has appeared, but I do not have the exact reference handy--apologies!] and the X-Y heuristic described in A.~Prieditis. \newblock {\it Machine Discovery of Effective Admissible Heuristics}. \newblock In {\it Proceedings of the Twelfth International Joint Conference on Artificial Intelligence}, Sidney, 1991, 720--725. I hope this helps. Good luck! Marco Valtorta, Assistant Professor and Undergraduate Director Department of Computer Science internet: mgv@usceast.cs.scarolina.edu University of South Carolina tel.: (1)(803)777-4641 Columbia, SC 29208, U.S.A. fax: 777-3767 tlx: 805038 USC ------------------------------------------------------------------------- >From: schmid@bastille.berkeley.edu (Scott Schmidler) Newsgroups: comp.ai Subject: Re: Heuristic search and the 8 puzzle Date: 1 Oct 1993 03:54:37 GMT Organization: University of California, Berkeley In article , Marco Valtorta wrote: >Two very good admissible heuristics are the Linear Conflict heuristic of >O.~Hansson, A.~Mayer, and M.~Yung. >\newblock Relaxed Models Yield Powerful Admissible Heuristics. >\newblock {\it Information Sciences}, to appear. >[This has appeared, but I do not have the exact reference >handy--apologies!] The reference for this is: O. Hansson, A.Mayer, and M. M. Yung. Criticizing Solutions to Relaxed Models Yields Powerful Admissible Heuristics. Information Sciences, 63:3, 1992 scott. Article 27136 of comp.ai: Xref: acsu.buffalo.edu comp.ai:27136 sci.math:93568 Newsgroups: comp.ai,sci.math Path: acsu.buffalo.edu!ub!news.kei.com!news.mathworks.com!udel!gatech!howland.reston.ans.net!math.ohio-state.edu!jussieu.fr!pasteur.fr!news2.EUnet.fr!julienas!fozzie!phil From: phil@eurocontrol.fr (Philip Gibbs) Subject: Re: How many eight puzzle states? Sender: news@fozzie.eurocontrol.fr (News Distribution System) Message-ID: <1995Feb14.141038.18372@fozzie.eurocontrol.fr> Date: Tue, 14 Feb 1995 14:10:38 GMT Reply-To: phil@galilee.eurocontrol.fr References: <3hmhuv$803@tribune.usask.ca> <3hnrgt$o3d@taco.cc.ncsu.edu> Nntp-Posting-Host: galilee.eurocontrol.fr Organization: Eurocontrol Lines: 27 In article , nagle@netcom.com (John Nagle) writes: > > Half the possible states are legal, but I don't have a cite for that. > > Incidentally, the way to solve the 2^N-1 puzzle generally is as you mean N^2-1 > follows: > > 1. Solve the top row. Never touch it again. > 2. Solve the left column. Never touch it again. > 3. Recurse to solve the remaining subpuzzle. > If you know about signatures of permutations you can solve this problem. In the case where N is even the signature of the permutation of the pieces is an invariant of the group of transformations. That is the permutation defined by reading of the numbers left-to-right and top-to-bottom and ignoring the space. Therefore only even permutations can be legal. To show that all even permutations are legal you just have to prove that the solution John described works for those cases. Sorry that's a bit brief I'm in a rush. Article 27148 of comp.ai: Xref: acsu.buffalo.edu comp.ai:27148 sci.math:93630 Path: acsu.buffalo.edu!ub!news.kei.com!news.mathworks.com!udel!news.sprintlink.net!howland.reston.ans.net!EU.net!nova.puug.pt!news.rccn.net!news.ist.utl.pt!poirot.ist.utl.pt!aml From: aml@poirot.ist.utl.pt (Antonio Leitao) Newsgroups: comp.ai,sci.math Subject: Re: How many eight puzzle states? Date: 14 Feb 1995 19:29:36 GMT Organization: Grupo de Inteligencia Artificial, Instituto Superior Tecnico Lines: 91 Distribution: world Message-ID: References: <3hmhuv$803@tribune.usask.ca> <3hnrgt$o3d@taco.cc.ncsu.edu> NNTP-Posting-Host: sol.ist.utl.pt In-reply-to: cswellin@eos.ncsu.edu's message of 13 Feb 1995 14:49:01 GMT In article <3hnrgt$o3d@taco.cc.ncsu.edu> cswellin@eos.ncsu.edu (Carol Smith Wellington) writes: > >In article <3hmhuv$803@tribune.usask.ca>, Henry_Choy@engr.usask.ca (Henry Choy) writes: >> >> How do you find the number of states in the eight puzzle? >> >> -- >> >> Henry Choy >> choy@cs.usask.ca >> > >There are 9! states if you do not consider the fact that some states >cannot be reached from a legal starting state without picking up some of the >tiles. The problem is how to enumerate those illegal states. While I believe >proofs are available, unfortunately, I have not proven my intuition about the >number of illegal states. > >I have discovered picking up and switching an odd number of pairs of tiles >from a legal state gives an illegal state. In addition, rotating any 4 tiles >of a legal state gives an illegal state. Unfortunately, not all operations >which can cause illegal states always do. For instance, rotating 5 tiles from >a legal state may cause an illegal state, but might lead to another legal state. > >In general, for every legal state I can give at least one illegal state without >worrying about duplicates from modifying other legal states. For instance, for >every legal state, the state generated by switching the first two tiles will be >illegal and specific to this state. Therefore, the number of legal states >cannot be greater than 9!/2, but I cannot prove that is the exact number of >legal states. > You are absolutely right and 9!/2 is indeed the number of 'legal' states, but there are no such thing as 'illegal' states. The state space of the 8-puzzle can be divided in two halves, where any state in one half can reach any other state in the same half but not in the other half. There is a proof of this property but I forgot it...sorry :-) To check if two states are in the same half there is an algorithm: 1) Concatenate all rows of the puzzle in a single row. For instance 3 4 5 6 2 1 8 b 7 becomes 3 4 5 6 2 1 8 b 7 (b is the empty tile) 2) Define a reference state (for instance 1 2 3 4 5 6 7 8 b) 3) Count the number of misplaced pieces that are in front of each piece (relative to the reference state) and sum this for every piece. Do this for the two states of the problem. 4) If both count are odd or even, the states are in the same half, otherwise they are in different halves and you can't reach one from the other. Ex: 1 2 3 1 2 3 4 5 6 -> 5 4 6 7 8 b 7 8 b 1 2 3 4 5 6 7 8 b has zero misplaced pieces relative to the reference state 1 2 3 5 4 6 7 8 b has one misplaced pieces relative to the reference state(5 is before 4) So we can conclude that this example is impossible. The same thing is true for the 15-puzzle (15!/2 states in each half) and so on. Finally, let's answer the initial question: >> How do you find the number of states in the eight puzzle? Consider an empty puzzle (no pieces). You can put a 1 in the first position or in the second or in the third... or in the ninth, that is 9 hypotheses. For each one, you can put a 2 in any other of the remaining 8 free positions, that is 8 hypotheses for each of the previous 9 hypotheses. Do this to all pieces, including the empty one, and you will get 9*8*7*6*5*4*3*2*1 hypotheses, that is 9!. Aml Article 27179 of comp.ai: Xref: acsu.buffalo.edu comp.ai:27179 sci.math:93735 Path: acsu.buffalo.edu!ub!dsinc!spool.mu.edu!howland.reston.ans.net!gatech!taco.cc.ncsu.edu!cswellin From: cswellin@eos.ncsu.edu (Carol Smith Wellington) Newsgroups: comp.ai,sci.math Subject: Re: How many eight puzzle states? Date: 13 Feb 1995 14:49:01 GMT Organization: North Carolina State University, Project Eos Lines: 33 Distribution: world Message-ID: <3hnrgt$o3d@taco.cc.ncsu.edu> References: <3hmhuv$803@tribune.usask.ca> Reply-To: cswellin@eos.ncsu.edu (Carol Smith Wellington) NNTP-Posting-Host: c00746-400wi.eos.ncsu.edu Originator: cswellin@c00746-400wi.eos.ncsu.edu In article <3hmhuv$803@tribune.usask.ca>, Henry_Choy@engr.usask.ca (Henry Choy) writes: > > How do you find the number of states in the eight puzzle? > > -- > > Henry Choy > choy@cs.usask.ca > > Anything worth doing is worth overdoing. - R. Heinlein > is worth doing well. - Philip Dormer Stanhope, Earl of Chesterfield > There are 9! states if you do not consider the fact that some states cannot be reached from a legal starting state without picking up some of the tiles. The problem is how to enumerate those illegal states. While I believe proofs are available, unfortunately, I have not proven my intuition about the number of illegal states. I have discovered picking up and switching an odd number of pairs of tiles from a legal state gives an illegal state. In addition, rotating any 4 tiles of a legal state gives an illegal state. Unfortunately, not all operations which can cause illegal states always do. For instance, rotating 5 tiles from a legal state may cause an illegal state, but might lead to another legal state. In general, for every legal state I can give at least one illegal state without worrying about duplicates from modifying other legal states. For instance, for every legal state, the state generated by switching the first two tiles will be illegal and specific to this state. Therefore, the number of legal states cannot be greater than 9!/2, but I cannot prove that is the exact number of legal states. Article 27202 of comp.ai: Xref: acsu.buffalo.edu comp.ai:27202 sci.math:93801 Path: acsu.buffalo.edu!ub!news.kei.com!news.mathworks.com!noc.near.net!root From: alan@cit.state.vt.us (Alan Williams) Newsgroups: comp.ai,sci.math Subject: Re: How many eight puzzle states? Date: 15 Feb 1995 13:59:06 GMT Organization: State of Vermont Lines: 40 Message-ID: <3ht1ba$c3b@vtsis05.cit.state.vt.us> References: <3hmhuv$803@tribune.usask.ca> <1995Feb13.181516.19455@zh014.ubs.ubs.ch> NNTP-Posting-Host: cit11.cit.state.vt.us X-Newsreader: WinVN 0.92.6+ In article <1995Feb13.181516.19455@zh014.ubs.ubs.ch>, bit@svusenet.ubs.ch says: > >Henry Choy (Henry_Choy@engr.usask.ca) wrote: >: How do you find the number of states in the eight puzzle? > >What is the eight puzzle ? > I think the origial posting referred to the sliding block puzzle: +---+---+---+ | 1 | 2 | 3 | +---+---+---+ | 4 | 5 | 6 | <=== Impressive ASCII art huh? +---+---+---+ | 7 | 8 | | +---+---+---+ There are 9! ways of putting the 8 tiles in place. Since the puzzle has a parity of 2 any initial configuration can be transformed (by sliding) into exactly 9!/2 - 1 of the other configurations. For instance, the configuration shown above cannot be transformed into: +---+---+---+ | 1 | 2 | 3 | +---+---+---+ | 4 | 5 | 6 | <=== Even More Impressive ASCII art. +---+---+---+ | 8 | 7 | | +---+---+---+ See the rec.puzzles FAQ, probably under The Fifteen Puzzle. Alan "Flame me *real* hard if I goofed" Williams State of Vermont alan@cit.state.vt.us Article 27229 of comp.ai: Xref: acsu.buffalo.edu comp.ai:27229 sci.math:93928 Newsgroups: comp.ai,sci.math Path: acsu.buffalo.edu!ub!news.kei.com!news.mathworks.com!hookup!swrinde!howland.reston.ans.net!ix.netcom.com!netcom.com!nagle From: nagle@netcom.com (John Nagle) Subject: Re: How many eight puzzle states? Message-ID: Organization: NETCOM On-line Communication Services (408 261-4700 guest) References: <3hmhuv$803@tribune.usask.ca> <3hnrgt$o3d@taco.cc.ncsu.edu> Date: Tue, 14 Feb 1995 01:12:48 GMT Lines: 27 Sender: nagle@netcom19.netcom.com cswellin@eos.ncsu.edu (Carol Smith Wellington) writes: >I have discovered picking up and switching an odd number of pairs of tiles >from a legal state gives an illegal state. In addition, rotating any 4 tiles >of a legal state gives an illegal state. Unfortunately, not all operations >which can cause illegal states always do. For instance, rotating 5 tiles from >a legal state may cause an illegal state, but might lead to another legal state. >In general, for every legal state I can give at least one illegal state without >worrying about duplicates from modifying other legal states. For instance, for >every legal state, the state generated by switching the first two tiles will be >illegal and specific to this state. Therefore, the number of legal states >cannot be greater than 9!/2, but I cannot prove that is the exact number of >legal states. Half the possible states are legal, but I don't have a cite for that. Incidentally, the way to solve the 2^N-1 puzzle generally is as follows: 1. Solve the top row. Never touch it again. 2. Solve the left column. Never touch it again. 3. Recurse to solve the remaining subpuzzle. Once you know this, all the fun goes out of doing it by hand. You also realize it's really a rather lame puzzle. John Nagle Article 27296 of comp.ai: Xref: acsu.buffalo.edu comp.ai:27296 sci.math:94211 Path: acsu.buffalo.edu!ub!news.kei.com!news.mathworks.com!newshost.marcam.com!charnel.ecst.csuchico.edu!nic-nac.CSU.net!usc!howland.reston.ans.net!pipex!sunsite.doc.ic.ac.uk!susx.ac.uk!mattst From: mattst@cogs.susx.ac.uk (Matthew Stanfield) Newsgroups: comp.ai,sci.math Subject: Re: How many eight puzzle states? Followup-To: comp.ai,sci.math Date: 20 Feb 1995 20:00:44 GMT Organization: University of Sussex Lines: 272 Distribution: world Message-ID: <3iasdc$srd@infa.central.susx.ac.uk> References: <3hmhuv$803@tribune.usask.ca> <3hnrgt$o3d@taco.cc.ncsu.edu> NNTP-Posting-Host: tsunb-gw.susx.ac.uk X-Newsreader: TIN [version 1.2 PL2] : > How do you find the number of states in the eight puzzle? : > Henry Choy : > choy@cs.usask.ca : > : > Anything worth doing is worth overdoing. - R. Heinlein Henry, Well if that's your signing off quotation, here's a POP11 program written by me to solve the 8 puzzle. It uses blind search so it's fairly inefficient - but quite quick anyway. Enjoy it. Matthew 'Anything worth doing is worth overdoing' Stanfield mattst@cogs.susx.ac.uk (No big sigs = No mess!) ;;; The 8 puzzle solution. ;;; By Matthew Stanfield ;;; Start takes the 'completed' puzzle & makes a jumbled puzzle, which ;;; guarantees that the puzzle is solvable. Then it gives this solvable ;;; puzzle to search, initiating the whole solving process. define start(); [[1 2 3][4 5 6][7 8 9]] -> state; repeat 9 times oneof(nextfrom(state)) -> state; endrepeat; state => pr(newline); search(state); enddefine; define search(state); vars alternatives considered templist; [^state] -> alternatives; ;;;initially the start state is the only alternative to search from [] -> considered; until alternatives==[] do ;;;Keep searching until nor more alternatives dest(alternatives)->alternatives->state; ;;; pick first state in alternatives ;;; equivalent to hd(alternatives)->state; ;;; tl(alternatives)->alternatives; [^state ^^considered] -> considered; ;;;add chosen state to considered list print(state); if isgoal(state) then ;;; if it solves the problem then return return(state) endif; nextfrom(state) -> templist; ;;;generate list of daughter states for state in templist do ;;;unless these have been seen before insert them into ;;;alternatives list unless isoneof(state,alternatives) or isoneof(state,considered) then insert(state, alternatives) -> alternatives endunless; endfor; enduntil; return(false); ;;;return false if run out of alternatives enddefine; define isoneof(state,list); ;;;checks if a state is already in a list (criterion of equality given by ;;;samestate vars prevstate; for prevstate in list do if samestate(state, prevstate) then return(true); endif; endfor; return(false) enddefine; define insert(newstate, list) -> result; ;;;inserts a state into a list ordered by isbetter vars state, rest; if list matches [?state ??rest] and isbetter(state, newstate) then insert(newstate, rest) -> result; [^state ^^result] -> result; else [^newstate ^^list] -> result; endif; enddefine; ;;; Nextfrom takes state and returns output which is a list of lists. ;;; Each of these lists is a possible move for the blank piece. Find_blank ;;; finds the position of the blank piece. Change_pos then does the swaping ;;; if appropriate leaving the new list on the stack for the '[% %]' ;;; notation to pick up. The result is the list of daughter states. define nextfrom(state) -> output; vars r c t; copytree(state) -> t; find_blank(state) -> c -> r; [% if r > 1 then change_pos(r-1, c, r, c, t); endif; copytree(state) -> t; if r < 3 then change_pos(r+1, c, r, c, t); endif; copytree(state) -> t; if c > 1 then change_pos(r, c-1, r, c, t); endif; copytree(state) -> t; if c < 3 then change_pos(r, c+1, r, c, t); endif; %] -> output; enddefine; ;;; Change_pos swaps the blank piece and the piece it is going to replace. ;;; The variables are : r & c the row & column (within the list) of the ;;; piece where the blank is going to move and br & bc which is the position ;;; of the blank piece. define change_pos(r, c, br, bc, list) -> new; vars temp; copytree(list) -> new; new(r)(c) -> temp; 9 -> new(r)(c); temp -> new(br)(bc); enddefine; ;;; Find_blank finds the position of the blank piece. It returns r & c which ;;; is the blanks position in the list. '9' denotes the blank. define find_blank(list) -> c -> r; 1 -> r; 1 -> c; until list(r)(c) = 9 do c + 1 -> c; if c = 4 then 1 -> c, r + 1 -> r; endif; enduntil; enddefine; ;;; Isbetter takes 2 states & decides which is nearer the solution. It gets the ;;; Manhatan distance for each state and returns true or false. [Nb: True if ;;; they are equal - it must make a decision!] define isbetter(state1, state2); vars score1 score2; get_md(state1) -> score1; get_md(state2) -> score2; if score1 <= score2 then return(true); else return(false); endif; enddefine; ;;; Get_md returns the Manhatan distance which is the total of the distances ;;; that each piece has to travel before it is in the correct place. This ;;; includes the position of the blank. define get_md(list) -> total; vars r1 r2 num pos act; 0 -> total; for r1 from 1 to 3 do for r2 from 1 to 3 do list(r1)(r2) -> pos; cords_total(pos) -> num; r1 + r2 -> act; abs(act - num) + total -> total; endfor; endfor; enddefine; ;;; Coords_total returns the sum of row + column for any particuar position of ;;; a piece in the state, this is necessary for the calculation of the Manhatan ;;; distance. define cords_total(num) -> total; vars row col; if num = 1 then 1 -> row, 1 -> col; elseif num = 2 then 1 -> row, 2 -> col; elseif num = 3 then 1 -> row, 3 -> col; elseif num = 4 then 2 -> row, 1 -> col; elseif num = 5 then 2 -> row, 2 -> col; elseif num = 6 then 2 -> row, 3 -> col; elseif num = 7 then 3 -> row, 1 -> col; elseif num = 8 then 3 -> row, 2 -> col; elseif num = 9 then 3 -> row, 3 -> col; endif; row + col -> total; enddefine; ;;; Isgoal returns true or false as to whether its input state is the final ;;; solution or not. define isgoal(state); if state = [ [1 2 3] [4 5 6] [7 8 9] ] then return(true); else return(false); endif; enddefine; ;;; Samestate returns true or false as to whether its 2 states of input are the ;;; same or not, that is equal rather than identical. define samestate(state1, state2); if state1 = state2 then return(true); else return(false); endif; enddefine; ;;; Print prints state in the shape of the puzzle. define print(state); vars i item; for i from 1 to 3 do for item from 1 to 3 do pr(tab); pr(state(i)(item)); endfor; pr(newline); endfor; pr(newline); enddefine; start(); ;;; Initiates the program. /* Sample output... ** [[2 9 3] [1 5 6] [4 7 8]] 2 9 3 1 5 6 4 7 8 2 5 3 1 9 6 4 7 8 2 5 3 1 7 6 4 9 8 2 5 3 1 7 6 4 8 9 2 5 3 1 7 9 4 8 6 9 2 3 1 5 6 4 7 8 1 2 3 9 5 6 4 7 8 1 2 3 4 5 6 9 7 8 1 2 3 4 5 6 7 9 8 1 2 3 4 5 6 7 8 9 */ Article 50004 of comp.ai: Newsgroups: comp.ai Path: acsu.buffalo.edu!news.acsu.buffalo.edu!news.sunydutchess.edu!zombie.ncsc.mil!newsgate.duke.edu!nntprelay.mathworks.com!newsfeed.internetmci.com!4.1.16.34!cpk-news-hub1.bbnplanet.com!news.bbnplanet.com!ix.netcom.com!nagle From: nagle@netcom.com (John Nagle) Subject: Re: The Eight Pazzle Message-ID: Organization: Netcom On-Line Services X-Newsreader: NN version 6.5.0 CURRENT #9 References: <19971201202101.PAA20392@ladder01.news.aol.com> <65v97h$8ke$1@pith.uoregon.edu> Date: Tue, 2 Dec 1997 02:45:09 GMT Lines: 24 Sender: nagle@netcom6.netcom.com Xref: acsu.buffalo.edu comp.ai:50004 ginsberg@dt.cirl.uoregon.edu (Matthew L. Ginsberg) writes: >In article <19971201202101.PAA20392@ladder01.news.aol.com>, >SHANHON wrote: >>Hello, everyone. I have some trouble in this problem, "The Eight Pazzle". I >>have tried to search information about this from Internet, but I cannot find >>anything useful for this problem. Can anyone explain it for me? >Any good AI text should have a reasonable description of this >problem. >You might consider starting with the text in the AI class that >you are currently taking. It's a classic AI problem, although algorithmic solutions are available. The general 2^N-1 puzzle can be solved as follows: - Solve the top row. Never touch it again. - Solve the remainder of the left column. Never touch it again. - You have now reduced the order of the puzzle by 1. Recurse as necessary. John Nagle