gordon@meaddata.com (Gordon Edwards) (10/02/90)
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. I am taking the first course in a year-long graduate AI sequence and I would like to do some fairly exhaustive research before I try and solve the problem. I am particularly interested in various search algorithms and heuristics that have been applied to the 15 puzzle. Thanks, -- Gordon (gordon@meaddata.com)
gerhard@vmars.tuwien.ac.at (Gerhard Fohler) (10/02/90)
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
pmm@acsu.buffalo.edu (patrick m mullhaupt) (10/03/90)
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
nagle@well.sf.ca.us (John Nagle) (10/04/90)
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
lindsay@comp.vuw.ac.nz (Lindsay Groves) (10/05/90)
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
coleman@moby.cs.ucla.edu (Michael Coleman) (10/05/90)
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
houpt@svax.cs.cornell.edu (Charles E. Houpt) (10/05/90)
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.
druby@ics.uci.edu (David Ruby) (10/06/90)
>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 -- David Ruby
kudu@.ucalgary.ca (Gopi Kuduvalli, The Gemini) (10/06/90)
In article <coleman.655098336@moby> 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 <std.disclaimer> * - Bert Russell in 'Marriage and morals'
mmh@cs.qmw.ac.uk (Matthew Huntbach) (10/10/90)
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
nagle@well.sf.ca.us (John Nagle) (10/13/90)
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