bewwys
19 posts
Hi, 
#16613
What algorithm can I use ? 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. 
mmozeiko
Mārtiņš Možeiko
1923 posts
/ 1 project

#16615
What algorithm can I use ? 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 
bewwys
19 posts
Hi, 
#16617
What algorithm can I use ? 6 months, 4 weeks 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
446 posts

#16619
What algorithm can I use ? 6 months, 4 weeks ago mmozeiko actually it would be npcomplete, because there is a polynomial verifier 