This is a solver for the classic game Unblock me
The package exposes a solve
function which takes in a board state and returns the optimal solution as an array of Move
objects.
Block: { id: number, x: number, y: number, width: number, height: number }
Move: { blockId: number, amount: number, dir: 'x'  'y' }
Function: solve
Param  Type  Description 

initialBlocks  Block[] 
The configuration of the blocks on the board 
maxHeight 
number default 6

The height of the board 
maxWidth 
number default 6

The width of the board 
maxWidth 
boolean default false

A flag to determine whether blocks can only move in the direction of their larger size or in both directions 
goalY 
number default 2

The row where the goal is 
Returns  Move[] 
A list the moves for the optimal solution 
The solver is implemented using a Breadthfirstsearch (BFS) algorithm. For each board state, all legal moves are calculated and added to the search queue. The queue is expanded in a FIFOmanner, hence BFS. Duplicate states are detected by comparing the stringified representations of each board. The search stops when the goal state is reached. The list of moves needed for each state is stored alongside the state in the queue. This allows us to trace back the optimal solution once the goal state is reached.
For instance, given the following board state:
..22.3
.....3
1145..
..45..
6677..
....88
The following code will return the optimal solution:
import { solve } from 'unblockmesolver';
const blocks = [
{ id: 1, x: 0, y: 2, width: 2, height: 1 },
{ id: 2, x: 2, y: 0, width: 2, height: 1 },
{ id: 3, x: 5, y: 0, width: 1, height: 2 },
{ id: 4, x: 2, y: 2, width: 1, height: 2 },
{ id: 5, x: 3, y: 2, width: 1, height: 2 },
{ id: 6, x: 0, y: 4, width: 2, height: 1 },
{ id: 7, x: 2, y: 4, width: 2, height: 1 },
{ id: 8, x: 4, y: 5, width: 2, height: 1 },
];
const solution = solve(blocks);
console.log(solution);
Output:
[
{ id: 2, amount: 2, dir: 'x' },
{ id: 4, amount: 2, dir: 'y' },
{ id: 5, amount: 2, dir: 'y' },
{ id: 1, amount: 4, dir: 'x' }
]
In the original game, the board is always 6 x 6. However, the solver can handle boards of any size. The default board size is 6 x 6, but this can be overridden by passing the maxHeight
and maxWidth
parameters to the solve
function. Additionally, blocks can only move in the direction of their larger size by default. This can be overridden by passing the bidirectional
parameter to the solve
function. The goal row is 2 by default, but this can be overridden by passing the goalY
parameter to the solve
function.