I love this example so much. I used a similar kind of problem a year or so ago when playing with some kind of logic/linear programming/optimization system: given a set of shelves (width and length), find the set of guillotine cuts (cuts across the entire sheet) that minimizes how many sheets of plywood are needed. If I recall the general problem is actually in NP but by formulating it as a problem of finding a list of operations (new sheet, cut sheet X horizontally, cut sheet X vertically) the solver was able to come up with high quality solutions in seconds.

I then took it and added a second level: once it has found a minimal number of sheets, minimize the number of cuts. Super handy little tool! Once I had the solver part figured out and added a little tweak for handling kerf, it was quite simple to have it spit out an SVG that showed all of the pieces and cuts.

And now… I want to go find that code and play with it again. Super fun stuff outside of the daily grind.