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