LogFAQs > #878303702

Starting with a grid with a flat bottom, let's look at the pieces that can be dropped in.

Z/S and T: these all create illegal states and can be ignored.

L/J: After dropping an L/J, there will be an excess height of 2 on the left/right column, and 1 completed row. The only legal moves are to drop another L/J to restore the grid to a flat state with its height increased by 3 more completed rows, or drop an I to flip the column with the height differential while completing 2 rows.

I: After dropping an I, one column will have a height differential of 4. The only move is to drop one more I, increasing the height by 4 overall.

O: After dropping an O, you've simply increased the height by 2.

We see that the only legal states of the grid are to have a height differential of 0, 2, or 4. We now summarize the legal moves in each state, and the state that you advance to after playing the piece. A suffix of L or R indicates the side of a height differential and, in the case of an I block, the side the block is dropped on. The author regrets the overloading of capital L in this case but points his finger at GameFAQ's lack of Unicode support. We also leave the rotation of L/J pieces ambiguous as there is only one valid rotation for each state.

0:
O -> 0 (+2)
L -> 2L (+1)
J -> 2R (+1)
IR -> 4R (+0)
IL -> 4L (+0)

2L:
L -> 0 (+3)
IR -> 2R (+2)

2R:
J -> 0 (+3)
IL -> 2L (+2)

4L:
IR -> 0 (+4)

4R:
IL -> 0 (+4)

We have now defined all of the legal state transitions and their effect on the number of completed rows. Perform a depth-first search, terminating the branch when you hit a node that has more than 20 completed rows. Every time you encounter a 0-state node with height 20, count it and terminate the branch.

I am not doing this the combinatorics way.
---

Got questions about schoolwork? Want to share answers, or discuss your studies? Come to Homework Helpers!
http://www.gamefaqs.com/boards/1060-homework-helpers