2

The question is pretty forward: given a slot in a tetris board, how can I check if it is possible for any tetris piece to reach this slot? The pieces are allowed to rotate just like in normal tetris.

In this following example, the red piece is trying to reach the yellow slot and the gray slots are blocked. In the left case, it is not possible, while in the right case, it is possible (falling until it reaches the floor and quickly moving to the left).

enter image description here

The example shows a case with a ⅃ piece, but if any piece can reach it, the answer should be YES. The problem can be reduced to "can this specific piece reach the slot?". Then all pieces would be tested with this solution.

I had so many thoughts on this but I could come up with a counter example for everyone of them.

My last thought was: for each possible rotation, start placing the rotated piece in the target slot and trying to move it back to the place where it spawned. It might solve the problem but backtracking is not really performant to try with a bunch of pieces and possibly more than just one target slot.

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
Daniel
  • 7,357
  • 7
  • 32
  • 84
  • 1
    I would do this in reverse as you suggested start at the end position but instead of back tracking I would probably go for [raster A*](https://stackoverflow.com/a/23779490/2521214) slightly modified so you select one segment of the tetromino as "pivot" which will be also matchng the A* map but while filling/testing you test all tetromino positions but write just at the pivot position. Also for speedup its enough to reach free space (not the top). This however will not use rotations during movement which means there might be false negatives if more than one rotation is required during falling – Spektre Jan 14 '23 at 09:19
  • In the extreme cases where you might need to rotate a tetromino more than once, it matters how exactly the rotation is performed (what is the center of the rotation). This would need to be clearly specified in the question. – trincot Jan 14 '23 at 16:24

0 Answers0