Strategic Shapeshifting by autoc007

MERIDELL  Is Shapeshifter really the toughest game in Neopia? So far even the
game geniuses of Neopia have been stumped by this game, allowing us to safely
assume that it is the toughest. Have you given up already? I don’t think so. I
have assumed the position of an algorithm analyzer to introduce you to the patterns
that exist in solving Sinsi’s problems.
The patterns that you shall be introduced to are as follows
1) Direct Solution strategies
2) Backtracking strategies
3) TopDown 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 secondlast 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) TopDown 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.
