I will soon install wooden parquet floor in my home. And just for fun, I am thinking of writing an algorithm for making efficient use of the wooden planks I have.
Here’s the problem:
I have planks of different lengths enough to cover the surface.
The room is rectangular (Later I would like to expand algorithm to take into account objects/walls in the room)
- Planks in adjacent rows should have their seams/joints staggered (atleast 20cm between adjacent joints)
How to stagger wood floor planks
- Every new row should be started with the remainder of the cut-off of the previous row. I would prefer not to start new rows with a remainder smaller than 20cm
- The goal: I want the seams/joints pattern to look as random as possible and at the same time minimize cutting planks and have as little loss as possible of course.
- I am a .NET C# developer with some knowledge of F# and would like to use these to solve the problem.
My question is were do I start looking for inspiration on which base algorithms would fit my problem best?
Is this box stacking, bin stacking, linear stacking,…? Or better, has someone already solved this :-)?
I can give you a very general algorithm useful for these types of problems. This algorithm is mainly useful for your specific problem because you have a relatively small search space. If your search space was huge, you would need some complex optimizations.
Select a fixed number of random choices for the next plank to be laid down. For all those choices, make another set of random choices, etc. This is similar to a chess algorithm. At some point, you will be concerned about memory or CPU usage, since your tree is expanding. You can perform a search to a certain depth, then select the best branch among those, then continue the tree search from there.