Hello guys,

given n tetris pieces I have to find the minimum square I can fill in. (tetris pieces can't rotate)


What kind of algorithm can I use for this problem ?

I was thinking to a packing algoritm or backtracking but I'm not sure.

Thanks a lot.

I believe this is NP hard problem. There is no efficient algorithm. I would do recursive backtracking that tries all combinations.

Try googling "Polyomino solver" or something similar: https://en.wikipedia.org/wiki/Polyomino

Thank you,

yeah backtracking is the one who come first to mind but it's really inefficient I have to wait like more than hours to solve 26 tetris pieces :-(

I want to go for a NP hard algorithm but I don't know how accurate it is.

My first prioritize is to pack the tetris pieces in the min square.
Next is to do that in a reasonable mount of time.

But if I have no choice I will go for backtracking.

mmozeiko
I believe this is NP hard problem. There is no efficient algorithm. I would do recursive backtracking that tries all combinations.

Try googling "Polyomino solver" or something similar: https://en.wikipedia.org/wiki/Polyomino

actually it would be np-complete, because there is a polynomial verifier