Strategic Shapeshifting

The patterns that you shall be introduced to are as follows

1) Direct Solution strategies

2) Backtracking strategies

3) Top-Down Solution strategies

Without much ado, let us begin.

1) Direct Solution strategies

The direct solution strategies are classified into two types

a) Brute Force strategy

b) Greedy strategy

a) Brute Force strategy

A Brute Force strategy solves the problem in the most direct or obvious way. Thus, you may end up doing more work than while using any other strategy. On the other hand, this strategy is much easier to implement because of its simplicity. The following steps explain how this strategy is applied to a Shapeshifter problem.

Pick the first shape. There are several possible positions for the first shape. Apply the shape to all these positions and generate the corresponding new boards. Pick the second shape (which obviously has several possible positions on the board) and apply it to each of the boards that were obtained as a result of applying the first shape. As an example, if the first shape has four possible positions, then you have four new boards as a result of applying this shape on the four positions. Next, on applying the second shape (assuming it has four positions as well) on each of the four new boards we now have sixteen new boards. Repeat this procedure until all shapes are exhausted. You should now have a tree like structure that defines the entire solution. Now, examine the final list of obtained boards (which is quite large) and look for the right board. Tracing backwards from this board will give us the solution.

b) Greedy strategy

A Greedy strategy is one whose choice of decisions is such that once a given decision has been made, the decision is never reconsidered. The Greedy strategy can run reasonably faster than the Brute Force strategy and is also less frustrating. Unfortunately, the greedy strategy doesn’t guarantee a solution in a fixed number of attempts. The following steps explain how this strategy is applied to a Shapeshifter problem.

Pick the first shape and choose one of the several possible positions that exist for that shape. Apply the shape in that position and generate the new board. Now, pick the next shape and once again, choose one of its possible positions and apply it to the board previously generated. Repeat this procedure until all shapes are exhausted. Examine the final board. If it is the right board, we have found our solution; otherwise follow the same series of steps all the way from the first shape to the last. What we can perceive by looking at the way this strategy progresses is that we may find the solution at the first attempt itself. However, in the worst case we could end up being sorry for our greediness.

2) Backtracking strategies

A Backtracking strategy suggests decisions similar to that of the Brute force strategy, that is, reconsideration. The difference is that when you take a set of decisions and they fail, instead of starting all over again, the strategy suggests backtracking by a step and taking a different decision at the last step. If this fails as well, backtrack by another step and repeat this procedure.

The following steps explain how this strategy is applied to a Shapeshifter problem.

Pick the first shape and apply it to the board at any one of the possible positions. Repeat this procedure for all remaining shapes. If the final board obtained is not the required board, backtrack by one step and choose a different alternative for the last shape. Repeat this for all possibilities of the last shape; if the correct board is still not obtained, backtrack by two steps and choose a different position for the second-last shape.

Apply this shape to the board and try possible positions of the last shape. Up to several levels of backtracking may be necessary before arriving at the solution.

3) Top-Down strategy: Divide and Conquer

This is the best strategy out there to solve a Shapeshifter problem. This method involves breaking up the problem into two parts. Analyze the given set of shapes. Shapes that cover one/two blocks tend to have more number of possible positions than any other. Thus, these shapes require the maximum effort during the course of the problem. The main idea in the divide and conquer strategy is to avoid applying these shapes. To explain how this is done, let us consider a problem where we require applying ten shapes to get the solution.

Let us say one of the shapes is a single block that occurs at the sixth position. First, start with the given board and apply any of the above strategies to go up to the fifth shape. Next, take the completed board (all same symbols) and apply in reverse order, shapes seven through ten. You now have two boards, the first is a result of shapes one through five and the second is the result of shapes seven through ten (in the reverse order). Compare these two boards. They must differ by exactly one block. This block can easily be identified. The same can be done with a two block shape. In addition, we could skip applying two shapes; that is the fifth and the sixth and observe the result of one through four and seven through ten (in the reverse order) or skip sixth and seventh and observe the result of one through five and eight through ten (in the reverse order). Thus, dividing and conquering is one of the best solutions out there to solve a Shapeshifter problem.

I hope this article has brought an altogether different approach towards Shapeshifter. Do neomail me if you liked it.