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

*To*: cse471-f06@parichaalak.eas.asu.edu*Subject*: On sliding tile problems--history and math (and a question)*From*: Subbarao Kambhampati <rao@asu.edu>*Date*: Tue, 5 Sep 2006 22:13:49 -0700*Reply-to*: rao@asu.edu

****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'sCube: 10^19 68,000 years 24Puzzle: 10^25 12 billion years As I mentioned in the class, Manhattan distance heuristic is enough to bring 15 puzzle down to solvability. 24 puzzle however is a different beast all together. We are only now able to start cracking 24-puzzle problems (with pattern database heuristics). ***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? (Answer by adding comments on the blog). ********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 particular 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 below). 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. ****The theory behind disconnectedness of the state-space of tile-puzzles 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. cheers Rao ---------- Subbarao Kambhampati Professor, Department of Computer Science and Engineering Ira A. Fulton School of Engineering Arizona State University P.O. Box 878809 Tempe, AZ 85287 - 8809 rao@asu.edu (email) 480-965-0113 (Phone) 480-965-2751 (FAX) WWW: http://rakaposhi.eas.asu.edu/rao.html

- Prev by Date:
**Project 1 assigned. Due 9/22** - Next by Date:
**slides for lisp recitation** - Previous by thread:
**Project 1 assigned. Due 9/22** - Next by thread:
**slides for lisp recitation** - Index(es):