A command line program to solve polyomino puzzle with multithreading. Currently it only uses CPU, but I plan to add GPU acceleration support.
This program utilizes many C++11 features, so you need a C++11 compiler. If you are using GCC, type the command to compile:
g++ -O3 -std=c++11 -fopenmp -o polysolve -I include src/*.cpp
You need MinGW-w64 build of GCC to compile with GCC on Windows.
Or if you are using Visual Studio 2015,
cl /O2 /EHsc /openmp /Fepolysolve -I include src/*.cpp
Compile with makefile:
- GCC:
make CXX=g++
- Clang:
make CXX=clang++
Clang with GPU:make CXX=clang++ USE_GPU=yes
- MSVC:
make cl CLL=cl
NVCC:make nvcc NVCC=nvcc CUDA_PATH=<cuda path>
./polysolve [options] puzzlefile
Options:
-
--help
(-h
)Display available options
-
--version
(-v
)Display version information
-
--info
(-i
)Display performance measurements
-
--percent
Display running progress in percentage
-
--parallel-level <value>
(-pl
)Set the number of pieces to place when generating subproblems. A setting of 0 will disable multithreading. By default, it is set to 1.
-
--num-threads <value>
(-nt
)Set the number of threads for multi-thread solving. A setting of 1 disables multithreading, and a setting of 0 will use all CPU cores in this computer. The default value is 1.
-
--discard-solution
Use this option to discard all solutions and just count them. By default, the program saves all solutions in memory and output a random solution.
-
--reduction
Enable reduction pass. Will remove placements that make other pieces unable to place.
Puzzle file is a JSON format file. The top level is an object with the following keys.
- description: A string. Description of a puzzle. Optional.
- grid: Grid type of the puzzle. Can be one of the following:
square
,cube
,triangle
,hexagon
,tan
andoctagon
. Required. - board: A shape object describing board shape. Required.
- shapes: An array of puzzle pieces. Requires at least one item.
- name: A string. Name of a piece. Optional.
- mobility: Allowed movements of this piece. Can be one of the following:
mirror
,rotate
,translate
andstationary
. Default torotate
.mirror
: The piece can be flipped and rotated.rotate
: The piece can be rotated, but cannot be flipped.translate
: The piece can be moved, but cannot be rotated.stationary
: The piece cannot be moved at all.
- amount: An integer or an object.
Default value is
1
. When it is an object, it has two keys:- min: Minimum amount
- max: Maximum amount
- morphs: An array of shape objects describing possible shapes of a piece. Requires at least one item.
- notes: A string. Notes of a puzzle. Optional.
Shape object is a JSON object with either of the two keys: coords
and tiles
.
- coords: An array of coordinate tuples.
- tiles: A multi-dimensional array of 0/1 describing the tiles of grid. 0 means absent, 1 means present. The innermost dimension is x axis.
Coordinate tuple is an array of 1 to 4 integers, and the format is [x, y, z, w].
Example puzzle files are in test/
folder.
factorial.json
: Find all permutations of 11 objects. It has 11! solutions. Warning! This will use around 3 GB of RAM.langford.json
: Compute the number of Langford pairings for N=12.lonpos.json
: Lonpos 303 puzzle, 2D versionminimum.json
: Smallest valid puzzle file.pento.json
: Fill 6x10 rectangle with pentominoes.pento2.json
: Fill 18x5 rectangle with one-sided pentominoes.pentosymm.json
: Subproblem ofpento.json
to eliminate symmetric solutions ofpento.json
.soma.json
: Soma cubetangram.json
: Tangram puzzleY_pento_in_15x15.json
: Pack 45 Y pentominoes in 15x15 square.pento.psv
,tangram.psv
: PolyForm Puzzle Solver files used to generatepento.json
andtangram.json
.
You can convert puzzle file created with PolyForm Puzzle Solver or Polycube Puzzle Solver.
To convert PolyForm Puzzle Solver format, use the following command:
python3 converter/polysolver.py -i $IN_FILE -o $OUT_FILE
Currently only the following grid types are supported: Square, Cube, Triangle, Hexagon, Tan and Octagon.
To convert Polycube format, use the following command:
python3 converter/polycube.py -i $IN_FILE -o $OUT_FILE
- Place some pieces on the board before solving, to set up a puzzle problem, or to solve a puzzle partially.
- Add tiles to fill the board, when the pieces cannot cover the whole board.
- Support more grid types from other puzzle solvers.
- Using bit mask to accelerate solving.
- GPU acceleration with CUDA/ROCm