[math-fun] packing polyominoes?
My family recently gave me some packing puzzles for my birthday. One is a rectangle packing puzzle, where the rectangles' edges remain parallel to the sides of the tray; there are some pretty obvious algorithms for solving that one. The other is "Stewart's Coffin", which Martin Gardner pronounced "...the finest dissection puzzle of all time. It looks easy but is fiendishly difficult." It involves four laser-cut polyominoes and a tray that is just slightly too small in either direction for easy placement of the polynomials. Clearly the puzzle involves placing the pieces at an angle, but exactly which angle and how to arrange the pieces is the hard problem. Are there algorithms for solving a puzzle like this other than brute force? -- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com
I don't think brute force is going to be of much assistance in placing one polynomial in a box, let alone four ... WFL P.S. Are their roots shaped like g*ns? On 2/27/18, Mike Stay <metaweta@gmail.com> wrote:
My family recently gave me some packing puzzles for my birthday. One is a rectangle packing puzzle, where the rectangles' edges remain parallel to the sides of the tray; there are some pretty obvious algorithms for solving that one.
The other is "Stewart's Coffin", which Martin Gardner pronounced "...the finest dissection puzzle of all time. It looks easy but is fiendishly difficult." It involves four laser-cut polyominoes and a tray that is just slightly too small in either direction for easy placement of the polynomials. Clearly the puzzle involves placing the pieces at an angle, but exactly which angle and how to arrange the pieces is the hard problem. Are there algorithms for solving a puzzle like this other than brute force? -- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Tue, Feb 27, 2018 at 6:05 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I don't think brute force is going to be of much assistance in placing one polynomial in a box, let alone four ... WFL
Oops! hahaha! -- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com
On Feb 27, 2018, at 10:19 AM, Mike Stay <metaweta@gmail.com> wrote:
On Tue, Feb 27, 2018 at 6:05 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I don't think brute force is going to be of much assistance in placing one polynomial in a box, let alone four ... WFL
Oops! hahaha! -- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com _______________________________________________
Not so far off, actually. Suppose you have a dissection (no empty space) into translates (no rotations) of a polyomino monotile, and the n x n tray is a torus, then a solution is a factorization of (1+x+…+x^(n-1)(1+y+…+y^(n-1)) into the tile polynomial (e.g. L-tromino = 1+x+y) and some other polynomial with 0/1 coefficients (in the ring of cyclic polynomials where x^n=y^n=1). -Veit
For those who give up easily (including me!) there is a solution as a youtube video, 14 seconds long. Now I'm wondering what the dimensions of the rectangle is, given say each square of a polyomino is 1 by 1. On Tue, Feb 27, 2018 at 7:49 AM, Hans Havermann <gladhobo@bell.net> wrote:
"Stewart's Coffin" ...
Hadn't seen that name before. The puzzle started out as "Four Fit" and came to be marketed as "Martin's Menace".
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
We haven't addressed Mike Stay's question, which stymies me also: "Clearly the puzzle involves placing the pieces at an angle, but exactly which angle and how to arrange the pieces is the hard problem. Are there algorithms for solving a puzzle like this other than brute force?" For example, "Four Fit" a/k/a "Martin's Menace", Stewart Coffin's design #217, has a target area that can also be filled with various other sets of 4 pentominoes. Eliminating those that fill a grid-aligned a 4x5 (contained in the Four Fit box), there are 56; arbitrarily ignoring those that have duplicate pieces leaves 21 sets (including the original FTYZ): FLNP FNXZ LTYZ FLNT FPTU LUYZ FLPT FPVW LVYZ FNPT FPWY NPTZ FNPU FTVZ NPUZ FNPZ FTYZ NPYZ FNTZ LNPY PVYZ Four Z pentominoes make an alternate target area: A B B A A A B A C C B B D C D D D C C D The above has a tilted bounding box of side 22/sqrt(17) = ~5.33578, area 484/17 = ~28.47059 < 28.6 = Four Fit target area. Four Z's do not seem to fit in the 22/sqrt(17) box in any other way, BUT my ability to find weird packings is poor. Closely related to M Stay's question is whether any of the other 20 sets above, or the four Z's in the smaller box, have only the compact trick solution. I don't know of any way but very messy brute force. Any ideas? -- Mike Beeler
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
On Thu, Mar 1, 2018 at 4:12 PM, Mike Beeler <mikebeeler2@gmail.com> wrote:
I have sometimes wondered is there is any possible rigorous mathematical method for [solving polyomino packing problems].
I think there is. The solubility of a 2-d polygon packing problem is equivalent to a sentence in the first-order theory of the reals. That theory is decidable, so, in theory, we could submit such a sentence to a decision procedure and wait for the answer. To see how this could work, consider a simple packing problem that asks whether a square with side S can fit inside an equilateral triangle with side T. Without loss of generality, let the triangle be located in the first quadrant with the base along the horizontal axis and one corner on the origin. Let a,b,c,d be points representing the four corners of the square positioned in the plane: a--b | | d--c We are looking for four points a,b,c,d such that all of the following are true: - The four points form a square with side S. For example, the four edges of the square are correct (|a-b| = |b-c| = |c-d| = |d-a| = S) and the lengths of the two diagonals of the square are correct (|a-c| = |b-d| = Sqrt[2*S^2]). - The four points are inside the triangle. For example, each point a,b,c,d is above the X axis, to the right of the triangle's left side and to the left of the triangle's right side. (https://stackoverflow.com/questions/1560492/how-to-tell-whether-a-point-is-t...) If four such points exist, then the puzzle is solvable; otherwise not.
I note that tiling a region with polyominoes is NP-complete, even if they are all copies of the L-tromino (an old result of mine with John Michael Robson). - Cris
On Mar 1, 2018, at 3:56 PM, Josh Jordan <josh@joshjordan.name> wrote:
On Thu, Mar 1, 2018 at 4:12 PM, Mike Beeler <mikebeeler2@gmail.com> wrote:
I have sometimes wondered is there is any possible rigorous mathematical method for [solving polyomino packing problems].
I think there is.
The solubility of a 2-d polygon packing problem is equivalent to a sentence in the first-order theory of the reals. That theory is decidable, so, in theory, we could submit such a sentence to a decision procedure and wait for the answer.
To see how this could work, consider a simple packing problem that asks whether a square with side S can fit inside an equilateral triangle with side T.
Without loss of generality, let the triangle be located in the first quadrant with the base along the horizontal axis and one corner on the origin.
Let a,b,c,d be points representing the four corners of the square positioned in the plane:
a--b | | d--c
We are looking for four points a,b,c,d such that all of the following are true:
- The four points form a square with side S. For example, the four edges of the square are correct (|a-b| = |b-c| = |c-d| = |d-a| = S) and the lengths of the two diagonals of the square are correct (|a-c| = |b-d| = Sqrt[2*S^2]).
- The four points are inside the triangle. For example, each point a,b,c,d is above the X axis, to the right of the triangle's left side and to the left of the triangle's right side. (https://stackoverflow.com/questions/1560492/how-to-tell-whether-a-point-is-t...)
If four such points exist, then the puzzle is solvable; otherwise not.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Thu, Mar 1, 2018 at 8:15 PM, Cris Moore <moore@santafe.edu> wrote:
On Mar 1, 2018, at 3:56 PM, Josh Jordan <josh@joshjordan.name> wrote:
On Thu, Mar 1, 2018 at 4:12 PM, Mike Beeler <mikebeeler2@gmail.com> wrote:
I have sometimes wondered is there is any possible rigorous mathematical method for [solving polyomino packing problems].
The solubility of a 2-d polygon packing problem is equivalent to a sentence in the first-order theory of the reals. That theory is decidable, so, in theory, we could submit such a sentence to a decision procedure and wait for the answer.
I note that tiling a region with polyominoes is NP-complete, even if they are all copies of the L-tromino (an old result of mine with John Michael Robson).
And deciding even the existential theory of the reals is NP-hard [https://en.wikipedia.org/wiki/Existential_theory_of_the_reals], to say nothing of the general first-order theory. Note, though, that Mike didn't say anything about efficiency!
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
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
That's really interesting, thanks. On Thu, Mar 1, 2018 at 4:58 PM, <rcs@xmission.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com
participants (9)
-
Cris Moore -
Fred Lunnon -
Hans Havermann -
James Buddenhagen -
Josh Jordan -
Mike Beeler -
Mike Stay -
rcs＠xmission.com -
Veit Elser