Shortest path with figures on board

Question

I'm having trouble with my homework assignment(C++). I'm not asking for the complete solution, but tilt in the right direction could be helpful. :)

I have a NxN board (max N = 100) and a 1x2 figure (cube) on that board. The cube is painted red on the one side and blue on the other. Default position for the cube is left upper angle of the board, blue side up:

B B . .
. . . .
. . . .
. . . .

(4x4 example, B stands for blue)

There could be stones (obstacles) on the blackboard. Moves I can make with my figure:

• rotating it for 90/180/270 degrees clockwise
• you can flip the cube around its right/left/upper/lower edge, changing its ''upward color''

For an example, using flip right on the default position:

. . R R
. . . .
. . . .
. . . .

and then using rotate 90:

. . R .
. . R .
. . . .
. . . .

and then using flip left:

. B . .
. B . .
. . . .
. . . .

Of course, when rotating or flipping, you cannot land on the stone. So, the problem is - for any given configuration of the board (figure position and stone positions) write a program that will ''bring the cube home'' in the default position (blue side upwards!) using minimal number of moves and return 1 if that's possible or return 0 if that's impossible.

I find this problem interesting, but I have to admit I'm slightly confused with it. Especially the blue side/red side part. I can't really figure out how to ''translate'' those moves I can use in the language of usual shortest path algorithms (and I never used any of these). So, I would be grateful for every piece of advice you can give! :)

Answer 1

When dealing with this kind of problems, the first thing to do is to find a representation of the state of your problem. In this case, you need:

1. Two integers which represents the top-left position of your figure
2. One boolean which represents the color of the figure (red/blue)
3. One boolean which represents the orientation of the figure (horizontal/vertical)

If you are familiar with bitmasks, you should use just a 32 bit integer to do this (8 bits for x position, 8 bits for y position, 2 bits for the rest). In this way you don't need to implement a comparison operator. OR You define a simple struct (call it state) with these 3 information and a strict-ordering comparison on this (this is only needed to put state in std::set.

After this, you can solve this problem using a BFS.

To do that, you need:

1. An std::map<state,state> to store the position you already visited in the key, and the position you came from in the value (replace map with unordered_map if you can use c++11 and you use a bitmask to store your state)
2. A std::queue<state> in which push and pop up the states to be processed.
3. Some code to determine every possible state reachable from a given one (i.e. implements all the possible moves, taking care of the board dimension)

Pseudo code:

   map<state,state>  visited;
   queue<state> to_be_processed;

   visited.insert( initial_state,initial_state); //you are not coming from anywhere
   to_be_processed.push ( initial_state);
   
   while(!to_be_processed.empty()) {

              state cur = to_be_processed.pop();
              if ( cur == end_state) //you are done
              {
                    //to get the path from initial_state to end_state you have just to walk visited in the inverse order.
                    return 1;
              }
              for ( i = every possible state reachable from cur) {
                    if (visited.count(i) != 0) continue; //already visited
                    to_be_processed.push(i);
                    visited.insert(i,cur); //i has been visited, and you reached i from cur
              }

   }
   return 0; //if you get here, no way

The presence of obstacles make just the problem more difficult to code, but is no conceptually different.

Note that in this case BFS works because the cost you pay for going from one state to another is always the same.

Answer 2

First, since you are asked to find the exact optimal path, I would go with Dijksta's algorithm.

For this algorithm, you'll need:

1. A function which gives the next possible move.
2. A function which tell you if a position was already visited.
3. A function which tell you the total cost of each path.
4. And of course a function which tell you when you've reached the final position

Given an initial position, your cube can reach exactly 7 new positions. It's easy to pick which ones are possible.

G is simply the number of moves you've made so far + 1 for the next move :)

I would use a hashtable to keep track of the visited position. (This is probably the most difficult function to write), but you don't need to over think it right now. A simple vector and a term-by-term comparison would do. You can optimize this once your code is running.

And finally, you need to check if the cube is in its initial position blue side upwards.

Answer 3

You can interpret each possible 1x2 block and a color (red or blue) combination as a vertex and moves as edges. If it is possible to reach a particular 1x2 block and color combination (vertex) from some other combination in one move then there is a connection (edge) between those two combinations. Then you have to find shortest path between the given configuration and "home" configuration in the resulting graph (probably Breadth-first search since cost of the move is the same no matter what move you perform).

And if want to go further you can use advanced graph search algorithms that use heuristics during the graph traversal (heuristic being the minimum amount of moves needed to reach destination assuming there are no obstacles on the blackboard). For example you can use A* algorithm.