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