24 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 ?

1 year, 7 months 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.

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.

What algorithm can I use ?

1 year, 7 months 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

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

24 posts

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 ?

1 year, 7 months 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.

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.

What algorithm can I use ?

1 year, 7 months 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