A very low bar: Many packing problems can be converted to problems about real variables, with only ordinary polynomial algebra and inequalities connecting the variables. (Examples: The point (x,y) is within an R pentomino with corners at (a,b), (c,d), etc.) This can be placed in a logic expression (there is an x>0 such that for all y ... <algebraic statement & another v~ another ...>). Tarski gave a decision procedure for these statements. https://www.rand.org/content/dam/rand/pubs/reports/2008/R109.pdf The first few pages explain what's covered. In general, the complexity of the algorithm makes it impractical, but it does show decidability. I don't know if anyone has tried to use it answer packing problems. I'd guess that it blows up on anything more complicated than "can three circles of size a,b,c be packed inside a circle of size d?". Rich --- Quoting Mike Beeler <mikebeeler2@gmail.com>:
I asked Stewart Coffin 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>
? Mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun