Finding an algorithm for sliding squares

[ThemePark]

I need to find an algorithm for finding the paths for moving some squares given a start map and an end map, but I'm having trouble figuring it out. Allow me to demonstrate.

Suppose I have the following start grid:

  1
234
5 6

[ThemePark]

Sorry, I accidentally hit the Submit button, and it seems that it's not possible to edit your post once it's been submitted. Anyway, I'll continue the post here.

Each of the numbers represents a square where the number is the unique ID of that square, and the spaces are simply empty. The idea is that any square can be slid into one of the four directions, but it always has to touch at least one other square, and touching corners do not count. So in the start map, 6 can only move left, not down or right because it won't touch any square then and not up because there's already a square there.

Then suppose that I have the following end grid:

2314
5 6

So I need to transform the start grid into the end grid, following the rules I set up. So I need an algorithm for figuring out which moves to make for which squares.

The start and end grid can be any size and shape whatsoever, and sliding squares is not limited to the rectangle that the squares make. For instance, the start grid is in a 3x3 rectangle, but the squares can be moved outside of that as long as the rules are followed. Although now that I think about it, I'm not sure if it would even be possible to do that.

I'm also not sure if it will always be possible to find a set of moves to transform a starting grid into an end grid. For example, I'm not sure if this

1
23

can actually be transformed into this

23
1

Oh, and another thing, there will never be added or removed any squares, the start grid and end grid will always consist of the same squares, just in different orders.

Can anyone help me to come up with an algorithm for calculating the moves needed?

[nuzzle]

Although now that I think about it, I'm not sure if it would even be possible to do that.

It's not possible to move outside the grid. A square must always touch another square so if there isn't already a square outside the grid no new square can move there.

And not every grid can be turned into another grid. Say you have

12

It cannot be moved at all so it certainly cannot be moved into this,

21

Anyway this is a combinatorial problem and I think you need to generate all grid combinations systematically. The number of possible combinations grows very quickly with grid size so you won't be able to handle very big grids.

Say you have any grid. From this original grid you can easily generate the one-move grid set. Each grid in this set has one square moved one step compared with the original grid. If you have a grid and make one move you'll end up with a grid that's in the one-move set. If you compare the original grid with a grid in the one-move set the only difference is that one square has moved one step.

Now think of a tree, the tree of one-steps. Each node holds a grid and each child holds a grid from the one-move set of its parent. Children represent all grids you can get to by moving a parent square one step. Grandchildren represent all grids you can get to by moving two steps away from the grandparent, etcetera.

Now the solution is to systematically generate the tree of one-steps. You start with the start grid at the root and generate all its one-step children. Then you repeat this recursively with each of the children. Eventually you'll find the end grid you're looking for. Or rather you may find it at several places in the tree. You select the one that's closest to the root because it has the shortest path from the start grid. Once a solution has been found it can be used to bound the recursion. There's no need to look for solutions at greater depths because they represent longer paths.

But there is one glitch - cycles. What if a grid is already present in the tree and is inserted again? Then the tree will start repeating itself. It will be infinite. The solution is to skip a grid that's already present because its recursive branch has already been pursued before. That's how you break cycles and get a nice proper finite tree. All grids present in the tree should be unique. How to implement cycle avoidance isn't altogether trivial.

Note that the one-step tree doesn't have to be explicit. You don't need to actually build the tree. The tree will be implicit in the recursion. You only need to keep track of the current path (from root to current child) and you only need to store solution paths.

This is the brute force solution. You simply generate all possible non-cyclic paths from the start grid to the end grid and pick the shortest.

Key here is to find a dense grid representation. I suggest a 64-bit long integer. With 4 bits you can represent 16 digits from 0 to 15. Say 0 means the empty square and the rest are numbered squares from 1 to 15. You can fit 16 such 4-bit digits in a 64-bit long. This means the solution will be limited to a 16 square grid and 15 numbers.

Apart from being dense another advantage of the integer grid representation is that it's very fast to check for grid equality. You just compare two longs. It also means there's a very fast implementation of the cycle avoidance test. You just hold the longs (grids) that are already present in the tree in a hash table. Then checking whether a long is present is close to just one access in the hash table.

[ThemePark]

It's not possible to move outside the grid. A square must always touch another square so if there isn't already a square outside the grid no new square can move there.

And not every grid can be turned into another grid. Say you have

12

It cannot be moved at all so it certainly cannot be moved into this,

21

Yeah, I realized this too a while after submitting the post. The problem is though that I need to be able to turn any grid into any other grid. So I'm changing the rules a bit.

I'll still start out with the start grid as mentioned before. But the end grid will just consist of the pattern of squares but not their IDs, like this.

....
. .

So I'll need to get from the start grid to the end grid, not knowing which cubes will be where in the end grid, and getting there in the least amount of moves. Each movement of a square counts as exactly one move, i.e. moving a square up then immediately left doesn't count as one move but two.

So what would be the best way of doing it then?

[nuzzle]

So what would be the best way of doing it then?

It's essentially the same combinatorial problem so you can still solve it the way I suggested. But now each square can hold 0 or 1, where 0 is the empty square and 1 is a dot. If you use the integer encoding of a grid I suggested each square now occupies only 1 bit so a 64-bit long can represent up to 64 squares at the most (a chess board if the layout is a square).

My suggestion is a brute force solution but one cannot rule out that there's some clever move strategy available that would reduce the complexity. I don't know really but I've made some observations. For example if the initial grid layout is connected, that is if all squares are initially touching, then this formation cannot split up but will stay connected. It will move within its initial rectangular boundary. So if there are several such connected formations in a grid each can be solved separately which reduces the total number of possible combinations.

Also note that your "game" has some similarities with the Game of Life.

Each movement of a square counts as exactly one move, i.e. moving a square up then immediately left doesn't count as one move but two.

That's just like before isn't it?

But it doesn't matter for the solution. Different move rules just result in different one-step sets.

[ThemePark]

It's good to have made these posts and gotten feedback on them, as it has helped me visualize the "game" more clearly and find errors more easily. And I have realized that still not every start grid can be turned into every end grid.

For example, this grid can't be turned into anything, since none of the squares can be moved in any direction.

123
456

Therefore I've had to change the rules again. Now, instead of moving squares, I'm moving groups of squares. A group can just as well consist of just one square as of several squares, as long as each square in the group is connected to the entire group, thus two groups or more is not possible, then they will be seen as two seperate groups. And all squares in a group must be able to move in the intended direction.

With that new rule it is then possible to making the end grid I started out with, like this.

  1
234
5 6

  1
234
56

  1
 234
56

  1
5234
 6

5214
 63

5214
6 3

However, I am not sure whether to go with a group counting as one move, or as how ever many squares it contains, thus four squares is equal to four moves. But I think I'll go with the first. But that of course also depends on which of the two makes for an easier solution to getting from A to B.

[nuzzle]

And I have realized that still not every start grid can be turned into every end grid.

Yes when the numbered squares in a grid form a filled rectangle they cannot move.

However, I am not sure whether to go with a group counting as one move, or as how ever many squares it contains, thus four squares is equal to four moves.

For my suggested algorithm to work you must count a group move as one move. There must be a grid in the one-move set corresponding to each possible group move. This set holds all possible grids you can arrive at when you make one valid move, be it of a single square or of a group.

Conceptually group moves don't change anything but it becomes a little harder to generate the one-step set. It turns into a combinatorial problem in its own right. In this context it may be advantageous to view a group move as a sequence of single square moves.

[nuzzle]

I realize now that your game is a generalization of the so called 15-puzzle,

http://en.wikipedia.org/wiki/Fifteen_puzzle

[ThemePark]

Yes when the numbered squares in a grid form a filled rectangle they cannot move.

Actually, that's why I introduced the rule of moving groups instead of single squares, because that means that there are valid moves available for any start grid. The exception being any start grid where one side consists of only one square. But apart from those grids, I believe that it should be possible now to turn any start grid into any end grid.

For my suggested algorithm to work you must count a group move as one move. There must be a grid in the one-move set corresponding to each possible group move. This set holds all possible grids you can arrive at when you make one valid move, be it of a single square or of a group.

Conceptually group moves don't change anything but it becomes a little harder to generate the one-step set. It turns into a combinatorial problem in its own right. In this context it may be advantageous to view a group move as a sequence of single square moves.

The problem with using that algorithm is that before the number of moves was relatively small, at most the number of squares in the grid. Now there are many many times more moves from each grid, and that makes finding the path much harder with that algorithm. Just storing the moves will require a lot of data space, and it will only be possible to make a few levels of the tree.

I realize that my game has similarities to the 15 puzzle, but it's not really a generalization of it. The game does consist of finding the move path from a start grid to an end grid like 15 puzzle, but the end grid is always known in 15 puzzle. Furthermore, it's always a 4x4 square with 15 squares, whereas mine can take any size and number of squares. And finally, you can only move one square and only to an empty space in both puzzles, but in 15 puzzle the added constraint of only moving a square if it still has neighbours in the new space is always fulfilled for any possible move, but in my game there are many more squares than two to check, and thus many more moves.

I will start working on an implementation of your algorithm soon, but I believe there must be a better algorithm that doesn't rely on brute force, and I'm hoping someone has an idea for it.

[nuzzle]

but I believe there must be a better algorithm that doesn't rely on brute force, and I'm hoping someone has an idea for it.

Well, I think you should look at solutions to the 15 puzzle for inspiration (and other combinatorial games similar to yours). This is a secondary link from the other link I gave,

https://www.aaai.org/Papers/AAAI/2000/AAAI00-212.pdf

If you restrict the squares to empty/dot as you said and allow group moves then I think your chances are better to find some clever heuristics. It becomes like herding a swarm of bees. And maybe massive parallelism is an option, say using Cuda.

Interesting, but unfortunately I don't have time to think more about this now because I have problems of my own to solve.

Good luck!