Handmade Hero»Forums»Code
17 posts
Hi, I'm bewwys I'm a student at the 42 codingschool . I'm glad to be here. I'm a noob so please take care of me :)
What algorithm can I use ?
Edited by bewwys on Reason: Initial post
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.
Mārtiņš Možeiko
2559 posts / 2 projects
What algorithm can I use ?
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
17 posts
Hi, I'm bewwys I'm a student at the 42 codingschool . I'm glad to be here. I'm a noob so please take care of me :)
What algorithm can I use ?
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.
511 posts
What algorithm can I use ?
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