About project

This demo application was implemented to solve geometric puzzles using backtracking algorithm with additional "greedy" strategy to optimize practical computing time

Short rules & game features

• The pieces must be fully placed and can not overlap on each other
• The full game area must be covered
• Application will return solution, detect if solution is impossible or stop by timeout if max timeout reached
• Some fun predefined sets can be used or random set can be generated. Generated sets are full random so can be unsolvable

Implementation

To solve puzzle Greedy Backtracking algorithm was implemented

How it works

First, we re-order shapes from largest to smallest to try most "greedy" placement first.

Next, every shape dimensional orientation varianst are pregenerated by clockwise rotation, horizontal and vertical flipping.

Then, algorithm recursively attempts to place each shape in a position on the grid and checks if the placement allows completing the puzzle.

Pros

Generally effective for exploring possible configurations and can find all solutions if they exist. Logic is simple and easy to test.

Cons

For large grids or many shapes, this can become computationally expensive.

Computational complexity

So first we sort all shapes descending by size. This operation computational complexity is O(n log n)

Next, recursive backtracking algorithm is applied trying to place shapes into area. The computational complexity of implemented backtracking algorithm can be challenging to express precisely, as it depends on factors like the number of shapes and the layout of each shape.

But we can estimate an upper bound based on the possible placements and branches created in the recursive process.

Assuming there is P possible placements for each shape, considering recursive branching of backtracking algorithm the worst-case complexity for n shapes is O(Pn)

So total computational upper-bound complexity is O(n log n) + O(Pn)

In most scenarios initial sorting will greatly improve computational efficiency for small complexity increase.

Prerequisites

To build and run project Node.js v18.18 or later and npm are required

How to run

To get started first clone repository using terminal

git clone https://github.com/andriideren/puzzle-solver.git

Navigate to project folder and restore packages

cd puzzle-solver
npm install

Build and start web application

npm run build
npm run start

Open app in your browser

Run tests

To run Jest tests execute in terminal (after repository cloned and packages restored)

npm run test