4 ms·
Speaking of Tetris proofs, I've had the following problem on the back-burner for a while: is there a way to check whether an arbitrary contiguous space comprise
by archagon 12y ago
Speaking of Tetris proofs, I've had the following problem on the back-burner for a while: is there a way to check whether an arbitrary contiguous space comprised of squares can be filled in by tetrominoes? I don't have a math background so reasoning about it is difficult. Here's the question on StackOverflow: http://stackoverflow.com/questions/20083552/tetromino-space-filling-need-to-check-if-its-possible http://stackoverflow.com/questions/20083552/tetromino-space-...
- praptak 12y agoI vaguely remember someone having proved Tetris NP-hard but I think the problem wasn't filling a fixed shape but rather maximizing the number of erased lines given a board and an upcoming sequence of pieces. All this from memory, so it might be totally wrong.
- jones1618 12y agoA lot depends on your specific rules of the game. Does "filled by tetrominoes" mean you have to use every tetromino at least once? If not, then you can always fill your contiguous square space with 2x2 tetrominoes. Also, whatever your rules, it is generally a lot easier to prove it is possible (or not) to fill a space than find an actual solution.
- archagon 12y agoThe main rule I'm trying to follow is "as random a tiling as possible". So unless absolutely necessary, no picking certain pieces just because it's easier. The max area I'm having to tile is fairly small (maybe 100x100 at most) so an actual solution could be fairly easily brute-forced in the last step of the process. I just want to avoid having to backtrack as much as possible since it increases the cost substantially.