Problem 1978. Sokoban: Puzzle 10.45
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
11111111 11111111 Moves= 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.
Solution CommentsShow comments
Problem Recent Solvers7