Exercise 14:

Tetris
Solve the following exercise by means of a reduction to SAT: The input of the exercise and the output with the solution (when the input is solvable) are as follows: For instance, for input
    n = 3
    m = 10
    shapes = [6 5 4 3 2 0]
a valid solution would be:
    5 5 5 5 2 · · · 4 4
    0 0 1 1 2 2 3 · · 4
    0 0 · 1 1 2 3 3 3 4
where each dot should actually be a 1-1. Note that a board as this one:
    3 3 3 3 ·
    · 2 2 2 ·
    · · · 2 ·
    0 4 4 1 ·
    0 · 4 1 ·
    0 0 4 1 1
is valid, because the shape with index 44 does not have any shape with lower index directly above it, even though it is clear that it would be impossible to place it there. On the other hand, the situation of this other board:
    0 0 0 1 ·
    · 0 1 1 1
is not valid, as the shape with index 11 has the shape with index 00 directly above it.
Authors: Nil Mamano / Documentation:
To be able to submit you need to either log in, register or become a guest.