Hence, a natural data structure for storing the board is a two-dimensional array. The board is a two-dimensional area containing the objects of a Sokoban level. The boxes and walls on the board can split the board into several areas.Īn area of the board which the player cannot reach, surrounded by a barrier made of one or more boxes, and any number of walls is called “corral”. The player reachable area consists of all squares on the board currently reachable for the player. Other terms for a state are: game position, game state and game position. States can be stored in a transposition table so duplicate game positions can be detected, for instance. The search tree consists of states being generated during the search.

The term State is used when additional data are stored together with a Board Position.įor instance, a solver may store: pushes needed to reach the board position or the information of which box has been pushed last. The positions of all boxes and the player position constitute a Board Position. The positions of all boxes on the board form a specific Box Configuration. The objects on the board which the player can push around.Ī level is solved when all boxes have been pushed to a goal. The board is a 2 dimensional area containing the objects of a Sokoban level (walls, boxes, goals, player and empty squares).

4 Calculation of player reachable positionsĪ level contains a board and usually additional data like title, author name and solutions.2.3.1.1 Limit the transposition table size.

Sokoban solver online