Most efficient implementation for a Sokoban board?

Question

I am making a Sokoban solver in C++ and I was wondering what would be the most efficient implementation for the board, as to say the least memory consuming possible and the quickest operations possible.

I have heard about bit boards but I'm not sure it would be better than a classic 2D array. This is what a Sokoban grid look like :

The player is the greend sqaure, walls are red and static, boxes are blue and goals are the empty blue squares.

EDIT : The purpose is too be as efficient as possible when creating/storing the tree of possibilites for a sokoban level.

EDIT 2 : What I am looking to store is sokoban boards, as to say a grid that has multiple elements : one player, multiple static walls, moveable boxes, static goals (cell to put the box in). I run out of RAM - I have 8Go - on reasonable size levels (+50 moves). The sequence of moves the player has made is also stored with basic integers, like 1 for up, 2 for right etc.

Answer 1

Sokoban is NP-complete (Dor and Zwick 1999), see e.g. this survey.

Thus, you will not find a "quick" solver, the bottleneck is simply complexity. The only way to solve Sokoban is to use BFS (breadth first search) search, or, if memory is a problem, iterated DFS (depth-first search).

There are a few optimizations you can do:

• Implement a heuristic, to estimate number of steps needed to solve the puzzle. This allows you to change the BFS to A*, which searches the space in a more efficient manner, while still guaranteeing an optimal solution.
• Only do moves on boxes (that is, you only consider moving to, and pushing a box, a valid move), instead of considering moving the avatar one step in one of the 4 directions. This will save you a lot of space, the number of game positions is reduced by roughly a factor n, where n is the number of squares on the board.
• You might want some conditions that easily detect if you reach an unsolvable position, such as a box in a corner, and thus disallowing such moves.

Answer 2

I'm not an expert in Sokoban solving, so I can't claim this is "the" most efficient method, these are just some possible efficiencies that suggest themselves.

First, let's reduce our problem space.

Storing the whole 19x11 map as an array of bytes would take 209 bytes.

Storing it as a bitboard of block positions would take 209 bits, or 27 bytes, plus an index for the unique pusher position which in this case we could fit in one additional byte for a total of 28. Already more than 7 times smaller.

We only care about passable tiles, since a tile representing a wall will never have a block in it and will always hold a boring value of 0. So that brings us down to 55 bits for the blocks, or 8 bytes in total. We're now 26 times smaller than the initial array.

But not all passable tiles are created equal. Some, like the non-goal corners, will never hold a block in any solution or intermediate state, since the block would be trapped there and couldn't be pushed away. So, we can do a pre-process to identify only the viable tiles - this will help us later in our search, since we can immediately prune any move that takes a block outside this set. If we use breadth-first search for this fill, we can also note down the generation number of each viable tile we find, and re-use that later as a distance heuristic if using an A*-type search like Per Alexandersson suggests in another answer.

We start with only the goal tiles in our viable set's frontier, then flood-fill out from there, adding a passable tile to our viable frontier if it's a neighbour of one of our frontier tiles AND has a passable tile on the far side of it. This gives us this yellow region here, 41 tiles, taking us down to 7 bytes total.

Note that if any block starting positions are outside of the yellow viable zone, you can terminate early and conclude that the puzzle has no solution.

Now within this set, we only care about the tiles our blocks could actually reach. We can find this set by a similar flood fill starting from our initial block positions, and only adding a neighbouring viable tile to our frontier if there's a passable tile behind us from which we could be pushed into that viable neighbour.

If any of the goal tiles aren't covered by this new search, then we can again early-out with a "not solvable" conclusion, before we've done any of the hard work. :)

That gives us this green region, of only 33 tiles the blocks could ever occupy in a solution intermediate step, so we can store the state in just 6 bytes (or even 5 if we don't mind getting fiddly with our bit-packing, since we only need the bottom bit of the last byte in our bitboard, and can store the pusher position in 6 bits while still being able to express every pathable location).

So we've reduced the size of each state by about a factor of 30, while still retaining the ability to express any solution & intermediate step, and along the way building a few tools we can use to filter and prioritize possible moves.:)

Since our board states fit in a long in this case, we can compare two states for equality in a single operation, which is a nice perk too.

Another method to consider is to store just the index of each block within the viable-reachable set, sorting them to keep your representation order-independent, followed by the index of your pusher in its reachable set. Here that's 6 bits each for 7 items, or 42 bits - still about 6 bytes, unless we want to get fancy with bit packing to save the fractional bits and end up with 37 bits / 5 bytes. (Even though this number may look tiny, it's still 71 billion potential board states we might need to search, which could take something on the order of 30 GB of storage for our cache even with minimal overhead)

In this case the two options come out to within a 4-byte alignment padding anyway so it won't make a difference in terms of real storage used, but a big board with few boxes, or a small board with many boxes will shift the advantage one way or the other.

One last possible space saving: you said you store the sequence of moves the player has taken - but we don't really need to store all that (and some Sokoban solutions or attempts can get quite long indeed). Instead, we just need to know what was the last move we made, which can be expressed in 2 or 3 bits.

To reconstruct our full solution, we start from the goal state our search found, and undo the last move to get the intermediate state immediately before. Then we look up that state and undo its last move to get the state before, etc.

If you're using just 2 bits to store the last move, then when you're standing next to a block there's 2 possible preceding states: one where the block was where you're now standing, and you pushed it, and one where it was already in place and you walked up to it. So, it's probably safest to store a third bit for "push/no-push," but if you're being really frugal you can try both and abandon a branch if it tries to look up a prior state that you never generated.

Answer 3

To answer your literal question, first note that a Sokoban board contains both fixed state (the positions of the walls and the goal squares) and mutable state (the positions of the player and the boxes). For a solver, you should have only one copy of the fixed state. Thus, no matter how inefficiently you store it, the space cost of the fixed state is negligible. All you really need to worry about is compactly storing the mutable state.

A simple solution is to sequentially number the passable tiles (including the goals) on the board, and store the numbers of the tiles containing the player and each of the boxes. For example, your example board state above could be represented as (46;3,8,11,13,28,31), where the first number is the tile number of the player and the remaining numbers are the tile numbers of the boxes, with the tiles numbered in top-down, left-to-right order starting from zero.

Note that, to make comparing board positions simple, you'll want to always sort the positions of the boxes in some consistent (e.g. ascending) order. That way, you won't need to worry about the same example position sometimes getting represented as, say, (46;28,3,11,31,8,13) instead.

If you use a single byte for each position, you can handle boards of up to 256 tiles, and only need N+1 bytes for a board with N boxes. Using two bytes per position would let you have a board with up to 65536 passable tiles. In general, unless you're really strapped for storage space, I'd recommend this format as the likely "sweet spot" between compactness and ease of access.

---

If you really need more space, you could always use a smaller number of bits per position. For example, your example board only has 56 passable tiles, so six bits would be enough to encode each tile number, allowing you to squeeze the board state into 7 × 6 = 42 bits, or 5.25 bytes. But this extra space saving will come at the cost of slower encoding and decoding.

An even more compact representation would be to interpret the list of player and box positions as an integer written in base B, where B is the number of passable tiles on the board, and store that integer. For example, the number:

1,420,417,900,415 = (46 × 56⁶) + (28 × 56⁵) + (3 × 56⁴) + (11 × 56³) + (31 × 56²) + (8 × 56) + 13

encodes the board state (46;3,8,11,13,28,31) in base 56. Using this encoding, no state of your example board can exceed the number 56⁷−1 = 1,727,094,849,535, which can be stored in just 41 bits, saving a whole bit over the 6-bits-per-tile encoding. Of course, it also slows down encoding and (especially) decoding even more.

This representation is still not quite the most compact one possible, since some numbers in the range from 0 to B^N+1−1 correspond to invalid board states (with two boxes, or a box and the player, on the same tile) and others to non-canonical encodings (i.e. where the box positions are not listed in increasing order). If you really wanted to squeeze things as tight as they'll get, you could encode the box and player positions using the combinatorial number system, and then also encode which of the N+1 positions is the player. In principle, this would let you encode each board state using a number between 0 and (B choose N+1) × (N+1) − 1 inclusive, with each number in the range corresponding to a distinct valid (although not necessarily reachable) board state. For your example board, with B = 56 and N = 6, the maximum possible state number using this optimal encoding works out to just 1,623,421,799, which fits in only 31 bits!* But, of course, the encoding and the decoding would be even slower than with any of the other methods above.

Of course, as noted in the other answers, in practice it's probably much more efficient to rewrite your solver algorithm to avoid the need to store quite so many versions of the board state to begin with.

^{*) The fact that the combinatorial encoding saves about 10 bits over the simple base 56 encoding isn't really that surprising, since there are 6! = 720 possible ways to shuffle the 6 boxes, and this number is pretty close to 210 = 1024. So, compared to the optimal encoding, the base 56 system wastes about 10 bits redundantly encoding the order of the boxes.}

Answer 4

The board access and memory usage during normal gameplay is unlikely to be your bottleneck. You will only need to check movement every few frames and check sliding once every second at most. At a 16 ms per frame that's not worth optimizing beyond not being an idiot with it.

The real bottleneck related to the board will be rendering it. That requires looping over all tiles and switching over the contents every frame. So any structure that allows a fast iteration of the state will be enough.

---

For a solver implementation you care most about the "push points" and wether you can path to them from the last move.

So store all push points in a separate array and update them on each push. Then when going to select the next move you floodfill from the current location and filter the accessible push points as the next set of moves. This reduces the amount of steps you need to backtrack over.

The most efficient data structure for the floodfill would be a bit board.

1. clear the board and mark the starting position
2. shift the board 1 position in a direction
3. AND the shifted board with a board where only the walkable tiles are set.
4. OR the ANDed board with the current board
5. go to step 2 with a new direction.
6. if the new board after doing all directions is different from the previous board (tested using XOR and a reduce) you are done

This assumes that there isn't anything that happens while you move. Like an enemy that patrols a region.