I added another answer for an alternative explanation of the problem. You can think of this problem as Motion Planning in the Configuration Space of the tetris piece.
The Configuration Space
Define the configuration of a Tetris piece to be an (x, y) location and a rotation (t). The configuration of a Tetris piece is therefore three dimensional. We can define a 3D space that the Tetris piece lives in called its configuration space.
Now, configurations are either possible or impossible. A possible configuration has the Tetris piece completely inside empty parts of the tetris board. Impossible configurations either have the Tetris piece off of the board or colliding with occupied parts of the board.
Configuration Space Planning
The goal is to find a sequence of configurations
S =(c_0, ..., c_N), where
c_0 is the start configuration of the piece, and
c_N is the goal configuration, where
S is of minimum length, and all of the configurations in S are possible.
action as a function that takes one configuration and turns it into another. In Tetris, the actions are
Turn (which only modifies
Move Right and
Do Nothing. Depending on the way "gravity" is implemented, every action may also move the Tetris piece down as well.
If an action would result in an impossible configuration, that action is itself impossible.
The problem can be solved using AStar. In this case, the nodes in Astar are 3D configurations of the piece
(x, y, t). The links are actions which change from one configuration to another such that the resulting configuration is possible. The distance metric and heuristic is a simple 2D euclidean measure on the position of the piece, and a simple comparison on
t. All of the actions have weight
AStar is guaranteed to find the optimal set of actions needed to put the piece in the correct place.