Skip to main content

CLI to solve combinatoric chess puzzles.

Project description

CLI to solve combinatoric chess puzzles.

Stable release: Last release Python versions Software license Requirements freshness

Development: Unit-tests status Documentation Status Coverage Status Code Quality

Motivation

This project started its life as a coding challenge I was asked to solve while interviewing in 2015 for a software engineering position at Uber.

After the interview proccess ended, I kept toying with the code, as a playground to test some optimization strategies in Python. It is now a boilerplate that I use to:

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

In case it is not available on your system, see pip installation instructions.

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
Solver profiling graph

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:

N-queens problem solving time.

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

Changes for v1.5.3 (2016-11-30)

  • Fix rendering of changelog link in RST.

Full changelog.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

chessboard-1.5.3.tar.gz (36.8 kB view hashes)

Uploaded Source

Built Distributions

chessboard-1.5.3-py2.py3-none-any.whl (30.9 kB view hashes)

Uploaded Python 2 Python 3

chessboard-1.5.3-py2.7.egg (25.8 kB view hashes)

Uploaded Source

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page