Board#

BoardGraph#

class BoardGraph(puzzle: Puzzle)#

Board graph.

Depending on how sokoenginepy was installed, it is using either NetworkX or Boost.Graph under the hood.

Raises: ValueError – when puzzle width is greater than Config.MAX_WIDTH or or puzzle height is greater than Config.MAX_HEIGHT

__init__(puzzle: Puzzle)#

__getitem__(position: int) → BoardCell#

Raises: IndexError – position is off board

__setitem__(position: int, board_cell: Union[BoardCell, str])#

Raises: IndexError – position is off board

__contains__(position: int) → bool#

property tessellation: Tessellation#

tile_shape(position: int) → TileShape#

to_board_str(use_visible_floor=False, rle_encode=False) → str#

property size: int#

property edges_count: int#

property board_width: int#

property board_height: int#

out_edges(src: int) → List[Edge]#

Edges inspector, for debugging purposes.

Raises: IndexError – src is off board

neighbor(src: int, direction: Direction) → int#

Neighbor position in direction.

Returns: Target position or Config.NO_POS
Raises: IndexError – src is off board

wall_neighbors(src: int) → List[int]#

Raises: IndexError – src off board

wall_neighbor_directions(src: int) → List[Direction]#

all_neighbors(src: int) → List[int]#

Raises: IndexError – src off board

shortest_path(src: int, dst: int) → List[int]#

Calculates shortest path between two positions with all positions having equal weight.

Raises: IndexError – src or dst off board

dijkstra_path(src: int, dst: int) → List[int]#

Calculates shortest path between two positions not passing through board obstacles (walls, boxes, other pushers, etc…).

Raises: IndexError – src or dst off board

find_jump_path(src: int, dst: int) → List[int]#

Finds list of positions through which pusher must pass when jumping

Raises: IndexError – src or dst off board

find_move_path(src: int, dst: int) → List[int]#

Finds list of positions through which pusher must pass when moving without pushing boxes

Raises: IndexError – src or dst off board

positions_path_to_directions_path(positions: List[int]) → List[Direction]#

Converts path expressed as sequence of positions to one expressed as sequence of Direction.

Raises: IndexError – Any position in positions is off board.

mark_play_area()#: Sets flag on all BoardCell in graph that are playable: reachable by any box or any pusher.

positions_reachable_by_pusher(pusher_position: int, excluded_positions: Optional[List[int]] = None) → List[int]#

Finds all positions that are reachable by pusher standing on pusher_position.

Doesn’t require that pusher_position actually has pusher.

Raises: IndexError – when pusher_position is off board. Doesn’t raise if any position in excluded_positions is off board; it simply ignores those

normalized_pusher_position(pusher_position: int, excluded_positions: Optional[List[int]] = None) → int#

Finds top-left position reachable by pusher without pushing any boxes.

Doesn’t require that pusher_position actually has pusher.

Raises: IndexError – when pusher_position is off board. Doesn’t raise if any position in excluded_positions is off board; it simply ignores those

path_destination(src: int, directions: List[Direction]) → int#

Given movement path directions, calculates position at the end of tha movement.

If any direction in directions would’ve lead off board, stops the search and returns position reached up to that point.

BoardCell#

class BoardCell(character: str = ' ')#

Stores properties of one cell in board layout.

Note

There is no game logic encoded in this class. It is perfectly fine to put pusher on wall cell (in which case wall will be replaced by pusher). This is by design: BoardCell is a value class, not game logic class.

clear()#: Clears cell, converting it to empty floor.

put_box()#

put_goal()#

put_pusher()#

remove_box()#

remove_goal()#

remove_pusher()#

to_str(use_visible_floor: bool = False) → str#

property can_put_pusher_or_box: bool#: True if this cell allows putting box or pusher on self.

Note

This method is not used by BoardCell modifiers (ie. put_box, put_pusher, etc…). As far as BoardCell is concerned, nothing prevents clients from putting box on wall (which replaces that wall with box). This method is used by higher game logic that implement pusher movement in which case putting ie. pusher onto same cell where box is makes no sense.

property has_box: bool#

property has_goal: bool#

property has_piece: bool#: True if there is pusher, box or goal on this cell.

property has_pusher#

property is_border_element: bool#: True if this is either a wall or box on goal.

property is_empty_floor: bool#: True if there is no pieces and no wall on this cell.

is_in_playable_area: bool#

property is_wall: bool#

Edge#

class Edge(u: int, v: int, direction: Direction)#

BoardGraph edge.

direction: Direction#

u: int#

v: int#

BoardState#

class BoardState(pushers_positions: ~typing.List[int] = <factory>, boxes_positions: ~typing.List[int] = <factory>, zobrist_hash: int = 0)#

Sample of board state.

See also

BoardManager
HashedBoardManager

NO_HASH: ClassVar[int] = 0#: Integer used for situations where board hash has not been calculated.

boxes_positions: List[int]#: Positions of boxes sorted by box ID.

pushers_positions: List[int]#: Positions of pushers sorted by pusher ID.

zobrist_hash: int = 0#: Zobrist hash of state.

See also

HashedBoardManager

BoardManager#

exception BoxGoalSwitchError#

exception CellAlreadyOccupiedError#

class BoardManager(board: BoardGraph, boxorder: str = '', goalorder: str = '')#

Memoizes, tracks and updates positions of all pieces.

assigns and maintains piece IDs
manages Sokoban+ piece IDs
moves pieces while preserving their IDs
checks if board is solved

BoardManager implements efficient means to inspect positions of pushers, boxes and goals. To be able to do that, pieces must be uniquely identified. BoardManager assigns unique numerical ID to each individual piece. This ID can then be used to refer to that piece in various contexts.

How are piece IDs assigned? Start scanning game board from top left corner, going row by row, from left to the right. First encountered box will get box.id = Config.DEFAULT_ID, second one box.id = Config.DEFAULT_ID + 1, etc… Same goes for pushers and goals.

BoardManager also ensures that piece IDs remain unchanged when pieces are moved on board. This is best illustrated by example. Let’s construct a board with 2 boxes.

>>> from sokoenginepy.game import BoardGraph, BoardManager, Config
>>> from sokoenginepy.io import SokobanPuzzle
>>> data = "\n".join([
...     "######",
...     "#    #",
...     "# $  #",
...     "#  $.#",
...     "#@ . #",
...     "######",
... ])
>>> puzzle = SokobanPuzzle(board=data)
>>> board = BoardGraph(puzzle)
>>> manager = BoardManager(board)
>>> manager.boxes_positions
{1: 14, 2: 21}

We can edit the board (simulating movement of box ID 2) directly, without using the manager. If we attach manager to that board after edit, we get expected but wrong ID assigned to the box we’d just “moved”:

>>> board[21] = " "
>>> board[9] = "$"
>>> print(board.to_board_str())
######
#  $ #
# $  #
#   .#
#@ . #
######
>>> manager = BoardManager(board)
>>> manager.boxes_positions
{1: 9, 2: 14}

Moving box through manager (via BoardManager.move_box_from) would’ve preserved ID of moved box. Same goes for pushers.

Initial board	Box edited without manager	Box moved through manager

Note

Movement methods in BoardManager only implement board updates. They don’t implement full game logic. For game logic see Mover

Parameters

board – board to mange
boxorder – Sokoban+ data (see SokobanPlus)
goalorder – Sokoban+ data (see SokobanPlus)

See:

Mover
SokobanPlus
BoardState

box_id_on(position: int) → int#

Raises: KeyError – No box on position

box_plus_id(box_id: int) → int#: See also

SokobanPlus.box_plus_id()

box_position(box_id: int) → int#

Raises: KeyError – No box with ID box_id

disable_sokoban_plus()#: Disables using Sokoban+ rules for this board.

See also

SokobanPlus

enable_sokoban_plus()#

Enables using Sokoban+ rules for this board.

Enabling these, changes victory condition for given board (return value of is_solved).

See also

SokobanPlus

goal_id_on(position: int) → int#

ID of goal on position.

Raises: KeyError – No goal on position

goal_plus_id(goal_id: int) → int#: See also

SokobanPlus.goal_plus_id()

goal_position(goal_id: int) → int#

Raises: KeyError – No goal with ID goal_id

has_box(box_id: int) → bool#

has_box_on(position: int) → bool#

has_goal(goal_id: int) → bool#

has_goal_on(position: int) → bool#

has_pusher(pusher_id: int) → bool#

has_pusher_on(position: int) → bool#

move_box(box_id: int, to_new_position: int)#

Updates board state and board cells with changed box position.

Raises

KeyError – there is no box on old_position
CellAlreadyOccupiedError – there is an obstacle ( wall/box/another pusher) on to_new_position
IndexError – of board to_new_position

move_box_from(old_position: int, to_new_position: int)#

Updates board state and board cells with changed box position.

Raises

KeyError – there is no box on old_position
CellAlreadyOccupiedError – there is an obstacle ( wall/box/pusher) on to_new_position
IndexError – of board old_position or to_new_position

move_pusher(pusher_id: int, to_new_position: int)#

Updates board state and board cells with changed pusher position.

Raises

KeyError – there is no pusher with ID pusher_id
CellAlreadyOccupiedError – there is a pusher already on to_new_position
IndexError – of board to_new_position

Note

Allows placing a pusher onto position occupied by box. This is for cases when we switch box/goals positions in reverse solving mode. In this situation it is legal for pusher to end up standing on top of the box. Game rules say that for these situations, first move(s) must be jumps.

move_pusher_from(old_position: int, to_new_position: int)#

Updates board state and board cells with changed pusher position.

Raises

KeyError – there is no pusher on old_position
CellAlreadyOccupiedError – there is an obstacle ( wall/box/another pusher) on to_new_position
IndexError – of board old_position or to_new_position

pusher_id_on(position: int) → int#

Raises: KeyError – No pusher on position

pusher_position(pusher_id: int) → int#

Raises: KeyError – No pusher with ID pusher_id

solutions() → Iterable[BoardState]#: Generator for all configurations of boxes that result in solved board.

Note

Result set depends on is_sokoban_plus_enabled.

switch_boxes_and_goals()#

Switches positions of boxes and goals pairs. This is used by Mover in SolvingMode.REVERSE.

Raises: BoxGoalSwitchError – when board can’t be switched. These kinds of boards are usually also not is_playable.

property board: BoardGraph#

property boxes_count: int#

property boxes_ids: List[int]#: IDs of all boxes on board.

property boxes_positions: Dict[int, int]#

Mapping of boxes’ IDs to the corresponding board positions, ie.

{1: 42, 2: 24}

property boxorder: str#: See Also: SokobanPlus.boxorder

property goalorder: str#: See Also: SokobanPlus.goalorder

property goals_count: int#

property goals_ids: List[int]#: IDs of all goals on board.

property goals_positions: Dict[int, int]#

Mapping of boxes’ IDs to the corresponding board positions, ie.

{1: 42, 2: 24}

property is_playable: bool#: Checks minimal requirement for board to be playable.

property is_sokoban_plus_enabled: bool#

Are Sokoban+ rule enabled for current game?

See also

enable_sokoban_plus

property is_sokoban_plus_valid: bool#: Validates current set of Sokoban+ rules.

See also

SokobanPlus

property is_solved: bool#

Checks for game victory.

Classic victory is any board position in which each box is positioned on top of each goal
Sokoban+ victory is board position where each box is positioned on top of each goal with the same Sokoban+ ID as that box

Result depends on is_sokoban_plus_enabled.

property pushers_count: int#

property pushers_ids: List[int]#: IDs of all pushers on board.

property pushers_positions: Dict[int, int]#

Mapping of pushers’ IDs to the corresponding board positions, ie.

{1: 42, 2: 24}

property state: BoardState#: Snapshots current board state.

property walls_positions: List[int]#

HashedBoardManager#

class HashedBoardManager(board: BoardGraph, boxorder: str = '', goalorder: str = '')#

Bases: BoardManager

Board manager that also manages Zobrist hashing.

Adds Zobrist hashing on top of BoardManager and keeps it up to date when pieces are moved.

Zobrist hash is 64b integer hash derived from positions of all boxes and pushers on board.

This hash is “resistant” to moving board pieces. Moving one pusher and box will change board hash. Undoing that move will return hash to previous value.

This kind of hash is reliable way for identifying board positions. Sokoban solvers might need this to operate.

When hashing, boxes with same Sokoban+ ID are treated as equal meaning that if two of these boxes switch position, hash will not change. This also means that for the same board, hash is different when Sokoban+ is enabled from the one when it is disabled.

Pushers are all treated equal, meaning that if two pushers switch position, hash will not change

Notes

enabling/disabling Sokoban+ rehashes the board state
moving pieces doesn’t need to re-hash whole board, it updates hash incrementally
undoing piece movement also updates hash incrementally with additional feature that returning to previous board state will return to previous hash value

disable_sokoban_plus()#: Disables using Sokoban+ rules for this board.

See also

SokobanPlus

enable_sokoban_plus()#

Enables using Sokoban+ rules for this board.

Enabling these, changes victory condition for given board (return value of is_solved).

See also

SokobanPlus

external_state_hash(board_state) → int#

Calculates Zobrist hash of given board_state as if that board_state was applied to initial board (to board where no movement happened).

board_state must meet following requirement:

len(board_state.boxes_positions) == self.boxes_count and len(board_state.boxes_positions) == self.goals_count

Returns: Value of hash or BoardState.NO_HASH if it can’t be calculated

property boxorder: str#: See Also: SokobanPlus.boxorder

property goalorder: str#: See Also: SokobanPlus.goalorder

property initial_state_hash: int#: Zobrist hash of initial board state (before any movement happened).

property is_solved: bool#

Checks for game victory.

Classic victory is any board position in which each box is positioned on top of each goal
Sokoban+ victory is board position where each box is positioned on top of each goal with the same Sokoban+ ID as that box

Result depends on is_sokoban_plus_enabled.

property solutions_hashes: Set[int]#

property state: BoardState#: Snapshots current board state.

property state_hash: int#: Zobrist hash of current board state.

SokobanPlus#

exception SokobanPlusDataError#

class SokobanPlus(pieces_count: int, boxorder: str = '', goalorder: str = '')#

Manages Sokoban+ data for game board.

Sokoban+ rules

In this variant of game rules, each box and each goal on board get number tag (color). Game objective changes slightly: board is considered solved only when each goal is filled with box of the same tag. So, for example goal tagged with number 9 must be filled with any box tagged with number 9.

Multiple boxes and goals may share same plus id, but the number of boxes with one plus id must be equal to number of goals with that same plus id. There is also default plus id that represents non tagged boxes and goals.

Sokoban+ ids for given board are defined by two strings called goalorder and boxorder. For example, boxorder “13 24 3 122 1” would give plus_id = 13 to box id = 1, plus_id = 24 to box ID = 2, etc…

Valid Sokoban+ id sequences

Boxorder and goalorder must define ids for equal number of boxes and goals. This means that in case of boxorder assigning plus id “42” to two boxes, goalorder must also contain number 42 twice.

Sokoban+ data parser accepts any positive integer as plus id.

Parameters

boxorder – Space separated integers describing Sokoban+ IDs for boxes
goalorder – Space separated integers describing Sokoban+ IDs for goals
pieces_count – Total count of boxes/goals on board

box_plus_id(for_box_id: int) → int#

Get Sokoban+ ID for box.

Returns: If Sokoban+ is enabled returns Sokoban+ ID of a box. If not, returns DEFAULT_PLUS_ID
Raises: KeyError – No box with ID for_box_id, but only if i Sokoban+ is enabled

goal_plus_id(for_goal_id: int) → int#

Get Sokoban+ ID for goal.

Returns: If Sokoban+ is enabled returns Sokoban+ ID of a goal. If not, returns DEFAULT_PLUS_ID
Raises: KeyError – No goal with ID for_goal_id, but only if Sokoban+ is enabled

classmethod is_valid_plus_id(plus_id: int) → bool#

DEFAULT_PLUS_ID: Final[int] = 0#

Sokoban+ ID for pieces that don’t have one or when Sokoban+ is disabled.

Original Sokoban+ implementation used number 99 for default plus ID. As there can be more than 99 boxes on board, sokoenginepy changes this detail and uses DEFAULT_PLUS_ID as default plus ID. When loading older puzzles with Sokoban+, legacy default value is converted transparently.

LEGACY_DEFAULT_PLUS_ID: Final[int] = 99#

property boxorder: str#

property errors: List[str]#

property goalorder: str#

property is_enabled: bool#: Raises: SokobanPlusDataError: Trying to enable invalid Sokoban+

property is_valid: bool#

property is_validated#

property pieces_count: int#