Reinstalling a Hardwood Floor - My Solution

I've been spending quite a bit of time thinking about the hardware floor problem my father-in-law handed to me.  At first the problem seemed kind of straight-forward.  There's a pile of pieces of flooring, make sets of pieces whose total length is 184 +/- 1 inch.  As I thought it about it more, though, it became readily apparent that the problem was more complicated than I first thought.

1. No solution guaranteed - Though the total length of the pieces available sums to greater than the total length needed, there is no guarantee that the pieces come in lengths that will form 20 sets that each sum to 184 inches.
2. Unique start and end pieces - Certain pieces can only be used as start and end pieces as they have been cut and lack a tongue or groove on one side.  Additionally, there are only 13 starting and ending pieces which means that some pieces with both a tongue and groove (middle pieces) will end up acting as a starting or ending piece.
3. Cutting may be required - It may not be possible to find a solution EXCEPT if we allow middle pieces to be cut if they are at the beginning or end of a run, effectively making them starting or ending pieces.  If we don't allow for this scenario, we could end up in a situation where there are plenty of pieces left to complete the task, but they are none short enough to fit in the remaining space at the end of each run.  The flip side of the coin is that once a piece is cut, it can only act as a starting and ending piece so only want to cut pieces as a last resort.
4. Permutations, not combinations - The biggest complication: since once a piece has been used in one run it can't be used in another, this is not a simple combination (order independent) problem but rather a permutation (order dependent) problem. An exhaustive search of the problem space would test not only which groups of pieces sum to the correct length, but the order in which the pieces are tried.  This is necessary because we don't know if a given piece must be joined with specific set of other pieces (a critical set if you will).

My "solutions" to these problems:

1. No solution guaranteed - I have no actual solution to the "no solution" problem.  I worked under the assumption that there is a solution and wrote my program in such a way that it would stop looking after a predetermined number of attempts.
2. Unique start and end pieces  - To handle the fact that only certain pieces can be used as starting and end pieces I wrote the program to pick one of each of these to form the basis for each run.  The program then worked to fill in the gap between the two by working from the middle pieces list.  Since the start and end list only had 13 pieces, I padded the list with zeros to bring it up to 20, the number of runs required.  This leads me to...
3. Cutting may be required - The zero length pieces in the start and end list essentially represent middle pieces that act as end pieces. Furthermore, I allowed for longer pieces being cut down by allowing for runs longer than the strict 184 + 1 inches.  Any middle piece that ended up acting as an end piece would have to be cut down and in situations where dedicated start and end pieces were used in the run, this would make it necessary to cut those down as well.  This would not sacrifice a tongue or groove as the start and end pieces are already missing one or the other.  The larger the allowed deviation from 184 + 1 inches, the more material may have to be cut off from existing pieces.
4. Permutations, not combinations - Ahhhhh. This was the problem that kept me thinking the most.  trying to find easy ways to add and remove pieces from trial runs, keep track of which pieces were being used, had been tried, or were being tested, intelligently resetting the trial to preserve sets that had not been proven to be infeasible... In the end I decided to cheat: pieces were chosen at random and I was fairly quick to completely start over.
   
   At the beginning of forming a run a beginning and ending piece is each randomly chosen.  Next, middle pieces are randomly chosen and added to the run until the length exceeds the maximum allowable length.  If the maximum length is exceeded, the piece just added is removed from the run, placed in a "already tried these" list and another candidate from the middle-piece list is added to the run.  By keeping track of all the middle pieces being tested (moving them from the middle-piece list to the tried-piece list) the program is able to exhaustively check all middle pieces to see if any of them would work.
   
   If a middle piece did work to complete the run, all pieces used to form that run were removed from their respective pools of candidate pieces and were saved off in a separate completed-run list.  Two more starting and ending pieces were chosen at random and the process repeated.
   
   If all of the middle pieces were tried and the run was always too short or too long, then the program ruthlessly restarts the entire process.  All pieces used in all completed runs are moved back to their starting lists and we start all over.  This all or nothing approach is draconian and the program does save off the results of that attempt if it has resulted in more runs being completed than on any previous attempt.  Again, I don't know if any solution exists and I wanted to have access to the best solution in case I never found the perfect, all 20-runs solution.  The program is also limited in the number of restart attempts it is given so as to prevent it running endlessly, looking for a solution that may or may not exist.

I implemented the above algorithm in Matlab (the programming language I currently know best) and set it to running.  I found that when I kept the maximum length requirement to the strict 184" + 1" requirement, the best solution that has been found so far was 18 complete runs.  When I relax the maximum length to 184" + 2" my best result so far is 19 runs and adding another inch gets me all the way to 20.  

These numbers are a bit deceptive, though.  The 184" + 1" result took somewhere in the neighborhood of 40 million restarts, the 184" + 2" took about 20 million and the 184" + 3" less than 0.1 million.  Again, I don't know if the 184" + 1" constraint has a full 20-run solution but I'm going to continue to run the program and see if it can be found.  For the longest time, the best solution was 16 runs but just last night an 18 run solution was found.  Once pieces start to need cutting, I don't know if the amount of material needing to be removed (one inch vs two) matters that much.  Depending on the tools, it might even be easier to remove more material as the saw wouldn't be working quite so close to the end of the board. 

As I said, the program is going to continue to try to find a full solutions for the 184" + 1" case but I'm going to send these results off to my father-in-law so that he can get his floor put back together.

2012-12-13 Update: I forgot to share my Matlab code; here it is. There are still some bugs in it that I have had to hack around so as to keep the iteration train rolling.  Most of the time, it works great but somehow, sometimes, some list variables end up empty when they shouldn't be which grinds things to a halt.  This happens infrequently enough that I decided to patch over it rather than fix it properly.  In this case, it was more important to have something that works 99.999% of the time rather than waiting to use the tool until it is at 100%.