unblock-me-solver
TypeScript icon, indicating that this package has built-in type declarations

1.0.5 • Public • Published

Unblock me solver

This is a solver for the classic game Unblock me

Interface

The package exposes a solve function which takes in a board state and returns the optimal solution as an array of Move objects.

Object structure:

Block: { id: number, x: number, y: number, width: number, height: number }

Move: { blockId: number, amount: number, dir: 'x' | 'y' }

Solver interface

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

Implementation

The solver is implemented using a Breadth-first-search (BFS) algorithm. For each board state, all legal moves are calculated and added to the search queue. The queue is expanded in a FIFO-manner, 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.

Usage

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 'unblock-me-solver';

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' }
]

Notes

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.

Readme

Keywords

Package Sidebar

Install

npm i unblock-me-solver

Weekly Downloads

3

Version

1.0.5

License

ISC

Unpacked Size

46.7 kB

Total Files

26

Last publish

Collaborators

  • peter-siket-szasz