Problem 1978. Sokoban: Puzzle 10.45
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.
Solution Stats
Solution Comments
Show commentsProblem Recent Solvers7
Suggested Problems
-
4234 Solvers
-
1594 Solvers
-
3083 Solvers
-
Project Euler: Problem 1, Multiples of 3 and 5
3142 Solvers
-
Backslang, odds are you used it at some point in time...
70 Solvers
More from this Author308
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!