Polyomino puzzle solver

Polyomino solver for polyomino puzzle implemented in TypeScript with configurable pieces and board size. This was done for fun to better understand this interesting problem related to "exact cover" problem. In order to solve the "exact cover" problem here, I used dlxlibjs library from taylorjg, as he did in his example.

See the demo

If you're more interested in the exact cover/dancing links, here are some resources that I found interesting:

• Stanford Lecture: Don Knuth—"Dancing Links" (2018)
• Nice writeup on dancing links and algorithm X
• Exact cover writeup (examples with python)
• Solve the Pentomino puzzle with C++ and dancing links

How to get set up

# Clone the repository
git clone https://github.com/dmarchuk/polyomino-puzzle-solver

# Go to the folder
cd polyomino-puzzle-solver

# Install all the dependencies
yarn install

# Start the development server
yarn start

Now you should have a webpack development server running on http://localhost:8080.

Usage

To see the solver in action, either go to demo page or start the development server locally.

Run example solution

To run the example solution, either click on the "Try example solution" button or open up a console and run this command:

Solver.generateExampleSolution();

Running with custom pieces and board size

To run the solver with your custom pieces and board size, you must first configure your pieces. This can be done by calling a Solver.addPiece() method with the coordinates and optional color:

Solver.addPiece([{ x: 0, y: 0 }, { x: 0, y: 1 }], 'green');
Solver.addPiece([{ x: 0, y: 0 }, { x: 1, y: 0 }, { x: 2, y: 0 }, { x: 2, y: 1 }], 'grey');

This will add green piece:

##

And a grey piece:

###
  #

Once you have the desired pieces set up, create solver board by calling Solver.createSolver(); with an array where first element is the board width and second is board height, like so:

Solver.createSolver([2, 3]);

After that, you can either click on "Solve" button to generate a solution or run Solver.solve(); command in the console. In this particular example, you should see a generated solution. If you click on the "Solve" button again or run the Solve.solve(); command again, you should see another generated solution.

API

When you have the solver opened up in your browser (either locally or on demo page), PolyominoSolver property will be added to window object. Below you'll find a list of what's available on this object.

Solver.pieces

This will get you the list of the current pieces that are set up in the solver.

Solver.addPieces(coordinates: Coordinates[], color?: string)

This will add the piece with given coordinates and color to the Solver.piece list.

coordinates - array of Coordinate objects, which is an object with properties x and y, both are numbers. Example:

[{ x: 0, y: 0 }, { x: 0, y: 1 }, { x: 0, y: 2 }, { x: 0, y: 3 }, { x: 1, y: 3 }]

This generates a piece with an L-like shape:

# 
# 
# 
##

color - string, for example violet or #F0F0F0. This is optional, if not provided, random color will be generated.

Solver.createSolver(size: [number, number])

This will create a solver object with defined pieces and given board size.

size - array with two numbers, first number is the board width and second number is board height. Example:

// Create a board with width 4 and height 5 with total number of 20 tiles.
Solver.createSolver([4, 5]);

Solver.solve()

This method will try to find a solution for the given board size and given pieces, if there is a solution, it will be drawn on the canvas. Every consecutive call will try to find the next solution.

Solver.loadExamplePieces()

This method will load up some example pieces to Solver.pieces se we can use them later. You can see these piece definitions here.

Solver.generateExampleSolution()

This method will generate an example solution with pieces loaded by Solver.loadExamplePieces() and board size 8x8 and draw this solution on the canvas.

Commands

Install dependencies

yarn install

Start a development server

yarn start

This will start a development server on http://localhost:8080.

Integrate - should be called for example in case of CI (runs linter, tests and build the bundle)

yarn integrate

Build the bundle

yarn build

Run tests

yarn test

Check test coverage

yarn test:coverage

Run linter

yarn lint

Some things that should be finished:

• Tests for PolyominoSolver.ts - most crucial parts are tested, but some things are not, especially the correct drawing on canvas should be tested.
• Display the current pieces in a sidebar.
• Application.ts should have an option to delete a piece by given index.
• User should be able to delete a piece from the pieces sidebar.
• Some more intuitive way of adding pieces.

Author

Daniel Marchuk

• Github: @dmarchuk
• LinkedIn: @danielmarchuk

License

Copyright © 2020 Daniel Marchuk.

This project is MIT licensed.