On Thu, Mar 1, 2018 at 2:12 PM, Mike Beeler <mikebeeler2@gmail.com> wrote:
I asked Stewart Coffin
I completely misunderstood that! I thought the "coffin" was the wooden box in which the pieces were to be placed and that the inventor's last name was Stewart.
about algorithms for solving a puzzle like his “Martin’s Menace”. He said I can share his reply:
Bill Cutler has a program for seeking solutions to designs such as my #217. It tries millions of different arrangements until it finds one or more solutions, or decides that there probably aren't any. But it falls short of mathematical certainty of either finding all or finding that none exist. I have sometimes wondered is there is any possible rigorous mathematical method for doing what Bill's program tries to do but comes up short. I have also wondered if it is possible to prove that no such method exists. I have also wondered if it is possible to prove that it is impossible to prove. Or to prove that such proof must be possible, even though not yet known. (Reminds me of Fermat's famous problem.) And so it goes. This probably sounds like nonsense, but I do sometimes wonder about such things seriously.
I should also clarify my “I don’t know of any way but very messy brute force.” I only mean that all mutually aligned globs of the given pieces can be enumerated, and for each all the bounding boxes with plausible tilts can be computed, and those compared to the puzzle’s container. That does not help with different pieces at different tilts, nor with “loose” packings where pieces don’t touch.
E.g., Erich Friedman’s paper on Packing Unit Squares in Squares — totally amazing. http://www.combinatorics.org/files/Surveys/ds7/ds7v5-2009/ds7.html <http://www.combinatorics.org/files/Surveys/ds7/ds7v5-2009/ds7.html>
Thanks! -- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com