soln ← ##.quzzle grid                       ⍝ A hard, simple problem.

Supplied  by  David  Crossley, who says: I spotted this puzzle in the Economist,
Dec 4-10,2004, "A hard, simple problem", p82.

A  grid  of squares of unit size is represented by a text matrix. The grid cont-
ains an initial setup of non-overlapping, rectangular tiles whose sides are 1 or
more  units.  Each tile is identified by a unique character (except '∣' or '_').
Thus,  the tile marked 1 below is a 2×2 tile; 3 is a 2×1 tile. Blank squares can
be moved into.

Here is an example setup in a 5×4 grid:       1122       top left tile is 11
                                              1134                        11
The task is to move the 2×2 tile (1) in         34
the top-left corner to any other corner       5667       top right tile is 22
by sliding tiles up, down, left or right.     5889

There are just 2 initial moves:  1-down or 5-up. It´s not as simple as it looks!

Function  [quzzle] works out the shortest possible solutions for puzzles of this
class, though it may take some time for larger grids.

Example:

    ⎕←grid←5 4⍴'11221134  3456675889'
1122
1134
  34
5667
5889

    quzzle grid
 Bottom-right  Bottom-left
 in 37 moves   in 56 moves

 1↓            1↓
 2←            2←
 2←            2←
 3↑            3↑
 4↑            4↑
 7↑            7↑
 7←            7←
 4↓            4↓
 4↓            4↓
 3→            3→
 7↑            7↑
 7↑            7↑
 1→            1→
 5↑            5↑
 5↑            5↑
 6←            6←
 8←            8←
 9←            9←
 9↑            9↑
 8→            8→
 8→            8→
 6↓            6↓
 9←            9←
 9←            9←
 1↓            1↓
 7↓            7↓
 7←            7←
 3←            3←
 4↑            4↑
 4↑            4↑
 1→            1→
 9→            9→
 9↑            5↓
 6↑            7←
 8←            9↑
 8←            9↑
 1↓            1←
               4↓
               4↓
               3→
               2→
               9→
               7→
               5↑
               5↑
               1←
               4←
               3↓
               2→
               7↑
               9←
               4↑
               8↑
               6→
               6→
               1↓

Back to: contents

Back to: Workspaces