You are given a board 5x5 and 24 square pieces (1x1), one of them with a cross (+) and all the others 23 with a straight line on it (25 such pieces would cover the entire board).

                   (1)              (23) 
                +-------+         +-------+  
                |  _|_  |         | _____ |
                |   |   |         |       |
                +-------+         +-------+

Place the cross-piece in the upper left corner of the board.

Your task is to find "how to put the others 23 pieces," leaving the bottom right corner free, so that once this is made, by only sliding the pieces, you can bring the cross-piece from the upper left corner to the right bottom corner (that is "free" initially).

"How to put the other 23 pieces" means what must be the orientation of the line on each one, horizontal or vertical, since those placed with the line horizontal-oriented can only slide horizontally - to the right and to the left,- and those placed with the line vertical-oriented can only slide vertically - up and down. Obviously, sliding is limited by the edges of the board.

The cross-piece is the only one that can slide horizontally and vertically.

As I said in my previous comment, the theoretical minimum (29 moves) can only be achieved if the + alternates between moving down and right.

I assumed (without loss of generality) that the + moves to the right first.  Ignoring all the moves that lead the empty space to the right of the +, I found that the board must look like this at the beginning:

+ -??
|-|-?
?|-|-
??|-|
???|-

Unfortunately, there must be at least 10 moves that lead up to this point.  This means that the theoretical minimum (which would have 8 moves up to this point) is impossible.  This solution takes 31 moves:

+-|??
|--|?
?|--|
??||-
???-

Even though this does not reach the theoretical minimum, we know that 31 is the real minimum.  My only assumption was that the + alternated moving right and down.  If this were not true, then the minimum would be 31 rather than 29, since moving in the same direction twice in a row has a penalty of two moves.  Therefore 31 is the minimum, though this is not the only solution that reaches this minimum.

Posted by Tristan on 2005-10-03 05:27:22