Thanks, I think I spoke too quickly; it's been a while. I think there are good algorithms these days---LU decomposition in prime fields will probably be efficient and accurate enough for interesting results. -tom On Sat, Dec 26, 2020 at 6:55 PM Allan Wechsler <acwacw@gmail.com> wrote:
Determinant finding is expensive, but not so expensive as to make this algorithm impractical for chessboard-sized polyominoes, I suspect. The adjacency matrix, remember, is pretty darned sparse, and I think we have good determinant-finders for sparse cases.
On Sat, Dec 26, 2020 at 9:52 PM Tomas Rokicki <rokicki@gmail.com> wrote:
This would be much nicer if there was a good way to calculate the determinant.
On Sat, Dec 26, 2020 at 6:44 PM Allan Wechsler <acwacw@gmail.com> wrote:
Today I learned from a Mathologer video (Burkard Polster, who apparently knows funster Jim Propp), that there is a fairly simple formula for the number of domino tilings on an arbitrary simply-connected polyomino. (Mathologer was ambiguous about whether the formula fails when the polyomino has narrow "necks", but my guess is that these cases are fine.)
You checkerboard-color the thing. In order for there to be any tilings at all, there have to be an equal number n of black and white squares. Then, assigning columns to white and rows to black, you construct an adjacency matrix; horizontal connections are marked 1, vertical connections are marked i (!), with 0's elsewhere; and then finally you take the determinant. Magically, either the entire real part or the entire imaginary part cancels away, and the absolute coefficient of the result (either pure imaginary or pure real) is the number of tilings.
Mathologer didn't say it, but this gives a reasonably efficient way to generate a random tiling of any tilable simply-connected polyomino P. Procedure: use the magic determinant to count how many tilings of P there are; call this N, and pick a random number K between 0 and N-1. This will be the "index" of the random tiling we will select. Now, prune off all the parts that have their domino coverings forced in some way or other. In the part that's left, pick the leftmost cell of the topmost row: it can be covered in exactly two ways, horizontally, and vertically. Imagine it's horizontal, and remove that domino to get a new polyomino Ph. Count how many tilings of Ph there are; call that N'. If K < N', then that upper-left cell will be covered horizontally; if K >= N', it will be covered vertically (and the remaining polyomino we will call Pv).
Now repeat this procedure with index K and polyomino Ph, or with index K-N' and polyomino Pv, depending on the outcome of the comparison. Eventually you will have tiled all the cells.
I would like to see an app that takes a given polyomino and picks random tilings for you. I would also like to see one that colors the cells of a given polyomino by the probability that they are covered horizontally or vertically by a random tiling. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- - https://cube20.org/ <http://cube20.org/> - https://golly.sf.net/ <http://golly.sf.net/> - https://experiments.cubing.net/ - _______________________________________________ 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
-- - https://cube20.org/ <http://cube20.org/> - https://golly.sf.net/ <http://golly.sf.net/> - https://experiments.cubing.net/ -