Algorithm for computing the amount of steps needed for all pieces on board to leave

Question

I have a problem:

On a 6x6 board you receive maximum of 6 pieces.
A piece is defined by its position, and which direction it moves without changing direction (Directions: Up, Down, Left, Right).
Every iteration any number of pieces can move, but only one can occupy one square at the end of the iteration. If two pieces are going into opposite directions they can pass each other once they are touching (They swap places). If one piece ends up on a square from which a piece will leave in the same iteration it's also allowed. In how many iterations (shortest time) will all of the pieces be outside the board.

I have tried doing it in this way:

1. Receive locations of every piece
2. Create every possible move that is available for every move in first list into a list of new moves, i.e move one piece,...,move all pieces
3. Remove old moves since those will not repeat.
4. Check every move created whether we can finish and add it back to the move pool.
5. Repeat from step 2.

Problem with this solution is that it is very time intensive, and therefore it won't work. I currently have no ideas how to solve the issue.

Answer 1

Step two will check 2⁶ combinations of moves per iteration (if there are 6 pieces on the board), i.e. a yes/no decision for each piece whether it will move or not.

Often many of those combinations will be invalid as they would let two pieces occupy the same square. Also, some combinations will not move a piece, while that piece is really not an obstruction to any other piece and thus there cannot be any benefit in not moving it. Putting such constellations in your list will slow down the process without benefit.

The algorithm would improve if it would recognise a few patterns:

1. If some pieces are positioned in a cycle, i.e. in a way where they all move to the position of the "next" piece in the cycle, then they should all move immediately.

   Examples:

   ┌───┬───┐
   │ → | ← |
   └───┴───┘
   

   Or:

   ┌───┬───┬───┐
   │ ↓ | ← | ← |
   ├───┼───┼───┤
   │ → | → | ↑ |
   └───┴───┴───┘
   

   There is no use in trying to only move a subset of these moves: only moving them all in the same iteration is valid. Furthermore, since they don't take up a square that was free before (and could possibly obstruct another piece), there is absolutely no reason to delay that combined move. So if this pattern is detected, all involved pieces should move.

2. If a piece would move to a square where no other piece currently is or could move to, there is no reason not to make that move. It should be made.

3. When a piece can move to a square where also other piece(s) can move to, then it is worth it to consider each of these possibilities, i.e. consider iteration alternatives where one of those pieces moves to that square and the other(s) don't move.

4. For each of the alternatives of step 3 (each combined with the moves of rule 1 and 2), rule 2 should be applied again for those pieces that can only move depending on the decisions taken in step 3.

With these "rules" you greatly limit the number of states you have to investigate, i.e. the size of your list will be much more limited. The only branching into alternative paths happens with rule 3.

Of course, implementing this will require some effort.

Other Optimisations

Although it will not improve the time complexity, you can gain a factor of execution time by using an efficient data structure.

Instead of working with x, y coordinates, use a one-dimensional position identification, for instance one that maps to the 6x6 board like this:

 0  1  2  3  4  5
 8  9 10 11 12 13
16 17 18 19 20 21
24 25 26 27 28 29
32 33 34 35 36 37
40 41 42 43 44 45

And, in line with that, don't store the letters of the directions, but instead store the relative position change in reference to the above numbering system:

Left = -1
Right = +1
Up = -8
Down = +8

So for one piece you would have two numeric attributes: one number for its position and another for its direction.

A move runs off the board when the resulting position is not in any of the above listed numbers. Note that the numbering has a gap between the rows, so that also horizontal overflow is easily detected.

Furthermore, with positions consisting of one number instead of a pair of coordinates it is easier and faster to test whether two pieces occupy the same position.