Handmade Hero » Forums » Code » What algorithm can I use ?
bewwys
14 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 :)

#16613 What algorithm can I use ?
3 weeks, 3 days ago Edited by bewwys on Oct. 27, 2018, 10:07 p.m. 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.
mmozeiko
Mārtiņš Možeiko
1826 posts / 1 project
#16615 What algorithm can I use ?
3 weeks, 3 days ago

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
bewwys
14 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 :)

#16617 What algorithm can I use ?
3 weeks, 2 days ago

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.
ratchetfreak
413 posts
#16619 What algorithm can I use ?
3 weeks, 2 days ago

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