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