The Sokoban Site has many puzzles to solve. This Challenge is to solve puzzle 10.45. The link may place the Cody enthusiast at 10.55. wiki Sokoban reference.

The basic rules are to places the Blocks on the Pedestals. Blocks can only be pushed, never pulled. A connected Pair of blocks can not be moved along their long axis. A 2x2 square of blocks is immoveable. A Wall can not be moved.

Sokoban can not jump blocks or move diagonally.

The map will be double ringed by a Wall(1). Map definitions: Empty(0) Block(2) Pedestal(3) Sokoban(4) Block on Pedestal(5) Sokoban on Pedestal(7).

Sokoban Movement is a numeric vector L(-nr) U(-1) R(nr) D(+1).

Input: Map, [nr,nc] of Sokoban characters [0,1,2,3,4,5,7]

Output: Moves, Vector of [-1 +1 -nr +nr] values

Scoring: Sum of Moves and Pushes

Examples:

Map

11111111
11111111 Moves=[5]  push right for a 5 row array
11042311
11111111
11111111

Test Suite Visualization: A visualization option is provided.

Algorithms: Recursive routines that check all possible pushes can solve small Sokoban puzzles. Routines that limit their depth can find minimal Push solutions at the cost of time. Identification of Locked conditions is important to avoid being stuck in recursion. Pairs of blocks on a wall or too many blocks on a wall are unsolveable conditions to avoid.