[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: cse471-f01@asu.edu*Subject*: On the disconnectedness of the 8-puzzle search space (or Learninglessons the hard way)+History of sliding tile puzzles*From*: Subbarao Kambhampati <rao@asu.edu>*Date*: Thu, 27 Sep 2001 14:04:26 -0700*Reply-to*: rao@asu.edu

[[apparently half the people ignore the scintillating mails I send to the class mailing list.. still for the edification of the other half, here goes one more mail,,,] Although it looks simple, the 8-puzzle is quite tricky. The most difficult puzzle requires 18 moves to solve. The 8-puzzle graph also has the nasty property that its graph has two *disconnected parts* each with 181440 nodes. If the start position is no one half, and the goal in the other half, the puzzle has no solution. Now, you think you can spot such a property quite easily... turns out that it is not that easy to tell if two random positions are in the same connected graph. Here is what happened (true (TM) story) to one hapless student today. He used what he thought was a simple initial state to check his code. The init state he used is 1 2 3 4 5 6 8 0 7 (and the goal state is the usual 1 2 3 4 5 6 7 8 0 ) Turns out that these two states are in two different components and the problem is unsolvable. Since he is using A* search without any checks to avoid repeated nodes, what this meant basically is that he will do search until all the cows come home without ever exhausting the space. Note that the very similar looking state 1 2 3 4 5 6 7 0 8 is trivially solvable... [[**See below for how you could figure this out**]] The student of course assumed that this is a problem with his code. He came for help during my office hours. After spending a futile 1 hour to check his code for errors, I finally decided to look at the actual supposedly simple init state he was using. At that point we checked the code against all the init state I provided in the class and his code works flawlessly. I tried to explain to him that he should consider himself lucky to have stumbled on a reasonably deep truth about puzzle problems, but he didn't seem to appreciate the merit of hard-earned lessons ;-) Anyways, this is why the code I gave to generate random instances of 8-puzzle problems _starts_ with goal-state and generates problems by starting with goal-state and making some sequence of moves from goal state to generate an initial state (this way we know they are in the same connected component!) The following "footnotes" point out that this poor student is not exactly alone in getting stuck with disconnected states... the very first challenge problem in 15-puzzle, 100 years back, turned out to be an unsolvable one (and indirectly lead to the invention of theory of permutation groups). Rao Footnote 1: [[ The theory behind disconnectedness has got to do with "even and odd permutations". In general if you take a state, physically lift two consecutive tiles in that state and swap their positions, then the new state will be disconnected to the old state. You can see that 1 2 3 4 5 6 8 0 7 can be got by starting with 1 2 3 4 5 6 7 8 0 physically lifting and swapping 7 and 8 to get 1 2 3 4 5 6 8 7 0 and then moving the blank to the left The swapping ensures that the goal state and the state 1 2 3 4 5 6 8 0 7 are disconnected.]] Footnote 2: History of the sliding puzzles is quite interesting.. The fifteen puzzle was invented by sam loyd in the 1870s, and appeared in the scientific literature shortly thereafter. The editor of the journal where the paper on 15-puzzle appered said at the front of the paper" "The 15 puzzle for the last few weeks has been prominently before the American public, and may safely be said to have engaged attention of nine out of ten persons of both sexes and of all ages and conditions of the community" ---In otherwords, it was the pokemon and hoolaa-hoop of the 1870s. Part of the reason for the world-wide fifteen puzle craze was that Loyd offered a $1000 cash prize to transform a particual intiial state to a particular goal state. Johnson and Story later proved that it wasn't possible, and that the entire statespace was divided into even and odd permutations and that there is no way to transform one into the other by legal moves. See http://www.cut-the-knot.com/pythagoras/fifteen.html Also see http://members.tripod.com/~dogschool/permutation.html which explains using the theory of permutations why Samuel's original puzzle could not be solved. Number of states in n-puzzle games: Below are some statistics on the sizes of the state spaces, and the time taken to solve them by brute force enumeration, under the highly optimistic assumption that you can expand 10 million (10, 000, 000 = 10^7 nodes per second.) 8 Puzzle: 10^5 .01 seconds 15 Puzzle: 10^13 6 days 3x3 Rubik's Cube: 10^19 68,000 years 24 Puzzle: 10^25 12 billion years An interesting point to ponder: Here is a question for you to think. The game of chess has about 10^40 legal positions--which is much bigger than 10^25, and yet a computer is the chess champion. How come? ;-)

- Prev by Date:
**Re: CSE-471 Project 1 submittal (fwd)** - Next by Date:
**A short paper on pattern databases.** - Prev by thread:
**Re: CSE-471 Project 1 submittal (fwd)** - Next by thread:
**A short paper on pattern databases.** - Index(es):