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.