chessboard package

Submodules

chessboard.benchmark module

Benchmarking tools.

chessboard.benchmark.run_scenario(params)[source]

Run one scenario and returns execution time and number of solutions.

Also returns initial parameters in the response to keep the results associated with the initial context.

class chessboard.benchmark.Benchmark[source]

Bases: object

Defines benchmark suite and utility to save and render the results.

scenarii = [{u'king': 2, u'length': 3, u'rook': 1, u'height': 3}, {u'knight': 4, u'length': 4, u'rook': 2, u'height': 4}, {u'length': 1, u'queen': 1, u'height': 1}, {u'length': 2, u'queen': 2, u'height': 2}, {u'length': 3, u'queen': 3, u'height': 3}, {u'length': 4, u'queen': 4, u'height': 4}, {u'length': 5, u'queen': 5, u'height': 5}, {u'length': 6, u'queen': 6, u'height': 6}, {u'length': 7, u'queen': 7, u'height': 7}, {u'length': 8, u'queen': 8, u'height': 8}, {u'king': 2, u'knight': 1, u'queen': 2, u'height': 5, u'length': 5, u'bishop': 2}, {u'king': 2, u'knight': 1, u'queen': 2, u'height': 6, u'length': 6, u'bishop': 2}]
csv_filepath = u'/home/docs/checkouts/readthedocs.org/user_builds/chessboard/conda/develop/lib/python2.7/site-packages/chessboard/benchmark.csv'
cpu_info = {'arch': 'X86_64', 'bits': 64, 'brand': 'Intel(R) Xeon(R) CPU E5-2670 0 @ 2.60GHz', 'count': 4, 'cpuinfo_version': (4, 0, 0), 'extended_model': 2L, 'family': 6, 'flags': ['aes', 'apic', 'clflush', 'cmov', 'constant_tsc', 'cx16', 'cx8', 'de', 'fpu', 'fxsr', 'hypervisor', 'kaiser', 'lahf_lm', 'lm', 'mca', 'mce', 'mmx', 'msr', 'mtrr', 'nopl', 'nx', 'pae', 'pat', 'pclmulqdq', 'pge', 'pni', 'popcnt', 'pse', 'rdtscp', 'rep_good', 'retpoline', 'sep', 'sse', 'sse2', 'sse4_1', 'sse4_2', 'ssse3', 'syscall', 'tsc', 'tsc_deadline_timer', 'tscdeadline', 'vme', 'x2apic'], 'hz_actual': '2.5936 GHz', 'hz_actual_raw': (2593566000, 0), 'hz_advertised': '2.6000 GHz', 'hz_advertised_raw': (2600000000, 0), 'l1_data_cache_size': '32 KB', 'l1_instruction_cache_size': '32 KB', 'l2_cache_associativity': '0x100L', 'l2_cache_line_size': 6L, 'l2_cache_size': '256 KB', 'l3_cache_size': '20480 KB', 'model': 45, 'python_version': '2.7.15.final.0 (64 bit)', 'raw_arch_string': 'x86_64', 'stepping': 7, 'vendor_id': 'GenuineIntel'}
context = {u'architecture': '64bit', u'chessboard': '1.6.0', u'cpu_freq_actual': '2', u'cpu_freq_advertised': '2', u'cpu_l2_cache': '256 KB', u'cpu_model': 'Intel(R) Xeon(R) CPU E5-2670 0 @ 2.60GHz', u'cpu_vendor': 'GenuineIntel', u'implementation': 'CPython', u'java': '', u'linux': u'debian stretch/sid', u'machine': 'x86_64', u'macos': '', u'python': '2.7.15', u'system': 'Linux', u'windows': ''}
column_ids = [u'length', u'height', 'queen', 'rook', 'bishop', 'king', 'knight', u'solutions', u'execution_time', u'chessboard', u'implementation', u'python', u'system', u'macos', u'linux', u'windows', u'java', u'architecture', u'machine', u'cpu_vendor', u'cpu_model', u'cpu_freq_actual', u'cpu_freq_advertised', u'cpu_l2_cache']
load_csv()[source]

Load old benchmark results from CSV.

add(new_results)[source]

Add new benchmark results.

save_csv()[source]

Dump all results to CSV.

nqueen_graph()[source]

Graph n-queens problem for the current version and context.

chessboard.board module

Board repesentation and utilities.

class chessboard.board.Board(length, height)[source]

Bases: object

Chessboard of arbitrary dimensions with placed pieces.

This kind of chessboard only accept new pieces which are not overlapping squares:

  • occupied by another piece;
  • directly reachable by another piece.

Internal states of the board are materialized by a vector. A vector is a simple iterable for which each element represent a square.

For Piece we use a bytearray so we can pack a lot of states in memory for caching. But here for boards, we prefer a common list of bool as it seems Python is a little bit faster dealing with these.

2D positions on the board are noted (x, y):

  0 1 2 3 4 …
0 . . . . .
1 . . . . .
2 . . . . .
3 . . . . .
4 . . . . .
…
  • horizontal range x goes from 0 to m-1.
  • vertical range y goes from 0 to n-1.
  • top-left position is (0, 0).
  • top-right position is (0, m-1).
  • bottom-left position is (n-1, 0).
  • bottom-right position is (n-1, m-1).
reset()[source]

Empty board, remove all pieces and reset internal states.

positions

Generator producing all 2D positions of all squares.

new_vector()[source]

Returns a list of boolean flags of squares indexed linearly.

All states are initialized to False.

validate_index(index)[source]

Check that a linear index of a square is within board’s bounds.

validate_coordinates(x, y)[source]

Check if the piece lie within the board.

index_to_coordinates(index)[source]

Return a set of 2D (x, y) coordinates from a linear index.

coordinates_to_index(x, y, x_shift=0, y_shift=0)[source]

Return a linear index from a set of 2D coordinates.

Optionnal vertical and horizontal shifts might be applied.

add(piece_uid, index)[source]

Add a piece to the board at the provided linear position.

get(x, y)[source]

Return piece placed at the provided coordinates.

chessboard.cli module

chessboard.pieces module

Definition of chess pieces and their behavioural properties.

class chessboard.pieces.Piece(board, index)[source]

Bases: object

A generic piece.

x: horizontal position of the piece. y: vertical position of the piece.

label = None
symbol = None
uid = None
territory_cache = {}
compute_coordinates()[source]

Compute 2D coordinates of the piece.

x

Return the piece’s horizontal position.

Property is used here so we only compute position once when needed.

y

Return the piece’s vertical position.

Property is used here so we only compute position once when needed.

bottom_distance

Number of squares separating the piece from board’s bottom edge.

right_distance

Number of squares separating the piece from board’s right edge.

top_distance

Number of squares separating the piece from board’s top edge.

left_distance

Number of squares separating the piece from board’s left edge.

horizontals

All horizontal squares from the piece’s point of view.

Returns a list of relative movements up to the board’s bound.

verticals

All vertical squares from the piece’s point of view.

Returns a list of relative movements up to the board’s bound.

diagonals

All diagonal squares from the piece’s point of view.

Returns a list of relative movements up to the board’s bound.

movements

Return list of relative movements allowed.

territory

Return the cached territory occupied by the piece.

compute_territory()[source]

Compute territory reachable by the piece from its current position.

Returns a list of boolean flags of squares indexed linearly, for which a True means the square is reachable.

class chessboard.pieces.King(board, index)[source]

Bases: chessboard.pieces.Piece

King model.

symbol = u'\u265a'
movements

King moves one square in any direction.

Don’t mind out-of-bounds relative positions: forbidden ones will be silently discarded within the Piece.territory() method above.

label = 'king'
uid = 3
class chessboard.pieces.Queen(board, index)[source]

Bases: chessboard.pieces.Piece

Queen model.

symbol = u'\u265b'
movements

Queen moves unrestricted horizontally, vertically and diagonally.

label = 'queen'
uid = 0
class chessboard.pieces.Rook(board, index)[source]

Bases: chessboard.pieces.Piece

Rook model.

symbol = u'\u265c'
movements

Rook moves unrestricted horizontally and vertically.

label = 'rook'
uid = 1
class chessboard.pieces.Bishop(board, index)[source]

Bases: chessboard.pieces.Piece

Bishop model.

symbol = u'\u265d'
movements

Bishop moves unrestricted diagonally.

label = 'bishop'
uid = 2
class chessboard.pieces.Knight(board, index)[source]

Bases: chessboard.pieces.Piece

Knight model.

symbol = u'\u265e'
movements

Knight moves in L shapes in all 8 directions.

Don’t mind out-of-bounds relative positions: forbidden ones will be silently discarded within the Piece.territory() method above.

label = 'knight'
uid = 4
chessboard.pieces.klass

alias of chessboard.pieces.Knight

chessboard.solver module

Utilities to search for valid set of positions.

class chessboard.solver.Permutations(pieces, range_size=None)[source]

Bases: object

Produce permutations of pieces iteratively.

increment()[source]

Increment the last permutation we returned to the next.

next()

Return next valid permutation.

Raise iteration exception when we explored all permutations.

skip_branch(level)[source]

Abandon the branch at the provided level and skip to the next.

When we call out to skip to the next branch of the search space, we push sublevel pieces to the maximum positions of the board. So that the next time the permutation iterator is called, it can produce the vector state of the next adjacent branch. See #3.

class chessboard.solver.SolverContext(length, height, **pieces)[source]

Bases: object

Initialize a chessboard context and search for all possible positions.

The search space is constrained by board dimensions and piece population.

vector_size
solve()[source]

Solve all possible positions of pieces within the context.

Depth-first, tree-traversal of the product space.

Module contents

Expose package-wide elements.

exception chessboard.ForbiddenCoordinates[source]

Bases: exceptions.Exception

A position given as 2D coordinates are out of board’s bounds.

exception chessboard.ForbiddenIndex[source]

Bases: exceptions.Exception

A position given as an index is out of board’s bounds.

exception chessboard.OccupiedPosition[source]

Bases: exceptions.Exception

A piece is added to a position already occupied by another.

exception chessboard.VulnerablePosition[source]

Bases: exceptions.Exception

A piece is added to a position reachable by another.

exception chessboard.AttackablePiece[source]

Bases: exceptions.Exception

A piece is added to a position from which it can attack another.