CLI to solve combinatoric chess puzzles.
Project description
Chessboard
CLI to solve combinatoric chess puzzles.
Motivation
This project is a playground to test some optimization strategies in Python, but is essentially an example of a real-life Python package, and serve me as a boilerplate project for future CLI.
Install
This package is available on PyPi, so you can install the latest stable release and its dependencies with a simple pip call:
$ pip install chessboard
Usage
List global options and commands:
$ chessboard --help
Usage: chessboard [OPTIONS] COMMAND [ARGS]...
CLI to solve combinatoric chess puzzles.
Options:
--version Show the version and exit.
-v, --verbose Print much more debug statements.
--help Show this message and exit.
Commands:
benchmark Benchmark the solver.
graph Plot solver performances.
solve Solve a chess puzzle.
Solver specific options:
$ chessboard solve --help
Usage: chessboard solve [OPTIONS]
Solve a puzzle constrained by board dimensions and pieces.
Options:
-l, --length INTEGER Length of the board. [required]
-h, --height INTEGER Height of the board. [required]
-s, --silent Do not render result boards in ASCII-art.
-p, --profile Produce a profiling graph.
--queen INTEGER Number of queens.
--king INTEGER Number of kings.
--rook INTEGER Number of rooks.
--bishop INTEGER Number of bishops.
--knight INTEGER Number of knights.
--help Show this message and exit.
Benchmark specific options:
$ chessboard benchmark --help
Usage: chessboard benchmark [OPTIONS]
Run a benchmarking suite and measure time taken by the solver.
Each scenario is run in an isolated process, and results are appended to
CSV file.
Options:
--help Show this message and exit.
Plotting specific options:
$ chessboard plot --help
Usage: chessboard graph [OPTIONS]
Update all kind of performance graphs from the benchmark data.
All data come from CSV database.
Options:
--help Show this message and exit.
Examples
Simple 3x3 board with 2 kings and a rook:
$ chessboard solve --length=3 --height=3 --king=2 --rook=1
<SolverContext: length=3, height=3, pieces={'rook': 1, 'king': 2, 'queen': 0, 'bishop': 0, 'knight': 0}>
Searching positions...
┌───┬───┬───┐
│ ♚ │ │ │
├───┼───┼───┤
│ │ │ ♜ │
├───┼───┼───┤
│ ♚ │ │ │
└───┴───┴───┘
┌───┬───┬───┐
│ │ │ ♚ │
├───┼───┼───┤
│ ♜ │ │ │
├───┼───┼───┤
│ │ │ ♚ │
└───┴───┴───┘
┌───┬───┬───┐
│ ♚ │ │ ♚ │
├───┼───┼───┤
│ │ │ │
├───┼───┼───┤
│ │ ♜ │ │
└───┴───┴───┘
┌───┬───┬───┐
│ │ ♜ │ │
├───┼───┼───┤
│ │ │ │
├───┼───┼───┤
│ ♚ │ │ ♚ │
└───┴───┴───┘
4 results found in 0.03 seconds.
Famous eight queens puzzle, without printing the solutions to speed things up:
$ chessboard solve --length=8 --height=8 --queen=8 --silent
<SolverContext: length=8, height=8, pieces={'rook': 0, 'king': 0, 'queen': 8, 'bishop': 0, 'knight': 0}>
Searching positions...
92 results found in 119.87 seconds.
Huge combinatoric problem can take some time to solve:
$ chessboard solve --length=7 --height=7 --king=2 --queen=2 --bishop=2 --knight=1 --silent
<SolverContext: length=7, height=7, pieces={'rook': 0, 'king': 2, 'queen': 2, 'bishop': 2, 'knight': 1}>
Searching positions...
3063828 results found in 9328.33 seconds.
The CLI allow the production of a profiling graph, to identify code hot spots and bottleneck:.
$ chessboard solve --length=6 --height=6 --king=2 --queen=2 --bishop=2 --knight=1 --silent --profile
<SolverContext: length=6, height=6, pieces={'rook': 0, 'king': 2, 'queen': 2, 'bishop': 2, 'knight': 1}>
Searching positions...
23752 results found in 207.25 seconds.
Execution profile saved at /home/kevin/chessboard/solver-profile.png
Performances
Results below are given in seconds, and were run with the --silent option.
Pieces |
Size |
Solutions |
MacBook Air [1] |
C1 instance [2] |
---|---|---|---|---|
2 kings, 1 rook |
3x3 |
4 |
0.01 |
0.04 |
2 rooks, 4 knights |
4x4 |
8 |
0.12 |
0.91 |
1 queen |
1x1 |
1 |
0 |
0 |
2 queens |
2x2 |
0 |
0 |
0 |
3 queens |
3x3 |
0 |
0 |
0.02 |
4 queens |
4x4 |
2 |
0.02 |
0.10 |
5 queens |
5x5 |
10 |
0.10 |
0.80 |
6 queens |
6x6 |
4 |
0.90 |
7.10 |
7 queens |
7x7 |
40 |
8.53 |
65.55 |
8 queens |
8x8 |
92 |
85.80 |
673.28 |
9 queens |
9x9 |
352 |
900.20 |
7 282.56 |
2 kings, 2 queens, 2 bishops, 1 knight |
5x5 |
8 |
3.29 |
23.79 |
6x6 |
23 752 |
187.40 |
1 483.31 |
|
7x7 |
3 063 828 |
8 150.86 |
62 704.99 |
To run the standard benchmark suite and add results to the database, run the benchmark in a detached background process:
$ nohup chessboard benchmark > /dev/null 2>&1 &
N-queens problem solving time:
Stability policy
Here is a bunch of rules we’re trying to follow regarding stability:
Patch releases (0.x.n → 0.x.(n+1) upgrades) are bug-fix only. These releases must not break anything and keeps backward-compatibility with 0.x.* and 0.(x-1).* series.
Minor releases (0.n.* → 0.(n+1).0 upgrades) includes any non-bugfix changes. These releases must be backward-compatible with any 0.n.* version but are allowed to drop compatibility with the 0.(n-1).* series and below.
Major releases (n.*.* → (n+1).0.0 upgrades) are not planned yet, unless we introduce huge changes to the project.
Third-party
This project package’s boilerplate is sourced from the code I wrote for Scaleway’s postal-address module, which is published under a GPLv2+ License.
The CLI code is based on the one I wrote for the kdenlive-tools module, published under a BSD license.
Other resources
License
This software is licensed under the GNU General Public License v2 or later (GPLv2+).
ChangeLog
1.5.0 (2016-07-01)
Note
This version is not yet released and is under active development.
Add default isort configuration.
Add more trove classifiers.
Add proper support of logging. Closes #2.
Use Miniconda to install numpy, scipy, matplotlib and pandas in Travis builds.
Activate unittests in Python 3.3, 3.4 and 3.5. Closes #9.
Activate unittests on OSX.
Get detailed CPU info for each benckmark.
Add sphinx-based documentation.
Use pip to install package and other extra dependencies.
Add a git mailmap template.
1.4.0 (2015-11-23)
Make the solver into a CLI sub-command.
Pythonize benchmarking and include it as a CLI sub-command.
Plot n-queens graph from benchmark data.
Switch from coveralls.io to codecov.io.
1.3.0 (2015-09-06)
Only compute 2D coordinates of each piece instance when needed, so we can reach immediately the cache if we’re only interested by the territory. Adds a 1.21x speedup.
Add custom PEP8 configuration.
Add custom Pylint configuration.
1.2.0 (2015-09-03)
Pre-compute some Board properties. Adds a 1.12x speedup.
Reuse Board object. Adds a 1.06x speedup.
Use list of boolean instead of bytearray for states in Board. Adds a 1.11x speedup.
Add a little benchmark suite.
1.1.0 (2015-08-28)
Use bytearray to represent board states. Closes #4.
Cache piece territories to speed solver up to 3x on board with big population of pieces.
1.0.0 (2015-08-27)
Do not spend time converting back and forth linear position to 2D position. Provides a 1.16x speedup.
Proceed permutation exploration with pieces of biggest territory coverage first. Adds 16x speed-up. Closes #5.
Add support for bumpversion.
Add new --profile option to produce an execution profile of the solver.
0.9.1 (2015-08-25)
Fix rendering of unicode string in terminal.
Document stability policy and release process.
Add PyPi-based badges.
0.9.0 (2015-08-25)
Validate CLI user inputs and provides hints.
Abandon branches of the search space as soon as possible. Closes #3.
Deduplicate per-kind piece group permutations early. Closes #7.
Add --silent option to skip displaying of all board results in ASCII art.
0.8.0 (2015-08-15)
Refactor solver to deduplicate positions by kind (combination) before iterating the search space by brute force (cartesian product).
0.7.0 (2015-08-14)
Display results in unicode-art.
0.6.0 (2015-08-14)
Add Knight model.
0.5.0 (2015-08-13)
Add Rook and Bishop models.
Allow overlapping but non-threatening territory of pieces to co-exists.
0.4.0 (2015-08-13)
Add project status badges.
Enable continuous integration metrics: build status, coverage and code quality.
Fix index to position computation in non-square boards.
Remove restriction on board dimensions.
Unit-tests result sets produced by the solver.
0.3.0 (2015-08-12)
Add Queen piece.
Fix displaying of piece representation.
Fix persistence of square occupancy between each piece addition.
0.2.1 (2015-08-11)
Fix King displacement map.
0.2.0 (2015-08-11)
Allow initialization of board pieces.
Implement brute-force solver.
0.1.1 (2015-08-08)
Package re-release to fix bad version number.
0.1.0 (2015-08-08)
First public release.
Implements a CLI to inititalize the chessboard.
0.0.0 (2015-08-08)
First commit.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for chessboard-1.5.0-py2-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 61cca81f0ad9be64f956bae843bb3af76aa0f221c793a39ea3060867905c61be |
|
MD5 | 8f035792a58cbd761dea0f98130bb04e |
|
BLAKE2b-256 | d1524a3eb276e9d6a4c4ea6167b942a5af6fe0e6e917238888e58b2af60fdba2 |