[math-fun] Slightly harder 15 puzzle
If you happen to have a 15 puzzle lying around with a removable piece, you can make a harder puzzle by bandaging the pieces as follows: + - - - - + | A A E b | | F c E E | | F D g | | D h i | + - - - - + Puzzle: Move AA from the upper-left corner to lower-right. If a move is counted as moving 1 piece any direction (including L-shaped paths)any number of squares, 131 moves are minimum. Second puzzle: Is this the hardest 4x4 Sliding Block Puzzle there is? --Neil Bickford
In partial answer to the second question, see the top of p.878 in Vol.4 of the 2nd edition of Winning Ways. I believe that this is also discussed in a recent book by Robert Hearne & Erik Demaine, but three copies of this have succesively disappeared from my possession. R. On Thu, 20 Jan 2011, Neil Bickford wrote:
If you happen to have a 15 puzzle lying around with a removable piece, you can make a harder puzzle by bandaging the pieces as follows: + - - - - + | A A E b | | F c E E | | F D g | | D h i | + - - - - +
Puzzle: Move AA from the upper-left corner to lower-right. If a move is counted as moving 1 piece any direction (including L-shaped paths)any number of squares, 131 moves are minimum.
Second puzzle: Is this the hardest 4x4 Sliding Block Puzzle there is? --Neil Bickford
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The book Richard is citing seems to be "Games, Puzzles and Computation" (2009, A K Peters Ltd) by Robert Hearn (not Hearne) and Erik Demaine, ISBN 978-1-56881-322-6 (or 1-56881-322-8). Neil: They do seem to discuss 15 puzzle and generalize it somewhat, but Google Books doesn't let me see the relevant pages (pages 166-168 seem the most important, maybe also 115-118) to determine if it addresses your questions. (I reformatted your diagram by replacing the letters with numbers so the columns line up in most email readers). - Robert Munafo Richard Guy wrote:
In partial answer to the second question, see the top of p.878 in Vol.4 of the 2nd edition of Winning Ways.
I believe that this is also discussed in a recent book by Robert Hearne & Erik Demaine, but three copies of this have succesively disappeared from my possession. R.
Neil Bickford wrote:
If you happen to have a 15 puzzle lying around with a removable piece, you can make a harder puzzle by bandaging the pieces as follows:
+ - - - - + | 1 1 5 2 | | 6 3 5 5 | | 6 4 7 | | 4 8 9 | + - - - - +
Puzzle: Move piece 1 from the upper-left corner to lower-right. If a move is counted as moving a piece any direction (including L-shaped paths) any number of squares, 131 moves are minimum.
Second puzzle: Is this the hardest 4x4 Sliding Block Puzzle there is? --Neil Bickford
-- Robert Munafo -- mrob.com Follow me at: mrob27.wordpress.com - twitter.com/mrob_27 - youtube.com/user/mrob143 - rilybot.blogspot.com
NB>Second puzzle: Is this the hardest 4x4 Sliding Block Puzzle there is? No, because you can raise the level to 132 by moving the "9" up one space! (Sorry!) Alternatively, by specifying the end condition of all pieces, + - - - - + | 5 3 9 | | 2 5 5 7 | | 4 7 6 | | 4 1 1 6 | + - - - - + you can increase the "depth" to 163! I'd very much like to know whether there is a harder 4x4 of either type. 132 beats Conway's Century, Jim Stephens' Quzzle, and Gil Dogon's Quzzle-Killer, and they're 4x5! (Bob Henderson, though, has a 4x5 of depth 235: http://puzzles.net23.net/gauntlet1.htm) --Neil Bickford On Fri, Jan 21, 2011 at 1:35 PM, Robert Munafo <mrob27@gmail.com> wrote:
The book Richard is citing seems to be "Games, Puzzles and Computation" (2009, A K Peters Ltd) by Robert Hearn (not Hearne) and Erik Demaine, ISBN 978-1-56881-322-6 (or 1-56881-322-8).
Neil: They do seem to discuss 15 puzzle and generalize it somewhat, but Google Books doesn't let me see the relevant pages (pages 166-168 seem the most important, maybe also 115-118) to determine if it addresses your questions. (I reformatted your diagram by replacing the letters with numbers so the columns line up in most email readers).
- Robert Munafo
Richard Guy wrote:
In partial answer to the second question, see the top of p.878 in Vol.4 of the 2nd edition of Winning Ways.
I believe that this is also discussed in a recent book by Robert Hearne & Erik Demaine, but three copies of this have succesively disappeared from my possession. R.
Neil Bickford wrote:
If you happen to have a 15 puzzle lying around with a removable piece, you can make a harder puzzle by bandaging the pieces as follows:
+ - - - - + | 1 1 5 2 | | 6 3 5 5 | | 6 4 7 | | 4 8 9 | + - - - - +
Puzzle: Move piece 1 from the upper-left corner to lower-right. If a move is counted as moving a piece any direction (including L-shaped paths) any number of squares, 131 moves are minimum.
Second puzzle: Is this the hardest 4x4 Sliding Block Puzzle there is? --Neil Bickford
-- Robert Munafo -- mrob.com Follow me at: mrob27.wordpress.com - twitter.com/mrob_27 - youtube.com/user/mrob143 - rilybot.blogspot.com _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I'd very much like to know whether there is a harder 4x4 of either type.
surely a brute force search could answer this for 4x4 and smaller puzzles. though i bet 5x5 puzzles are going to be computationally expensive. not necessarily in solving a given puzzle, but in enumerating the possible puzzles! erich friedman
participants (4)
-
Erich Friedman -
Neil Bickford -
Richard Guy -
Robert Munafo