Skip to main content
Alda's user avatar
Alda's user avatar
Alda's user avatar
Alda
  • Member for 10 years, 9 months
  • Last seen more than 7 years ago
comment
A combinatorial problem - counting the solutions
@ZackWolske, the cube is still too hard for my computer, it seems. It worked for 8 hours with no result. The 4x4 torus was easier, of course. Here's something interesting: the binomial estimate for the torus was 165636900. The actual number of solutions: 203520. But as it's a torus, and symmetric under shifts, the "true" number of solutions is 203520/16=12720. Well, this is eerily close to sqrt(165636900)=12870. And the sqrt of the binomial estimate of the 4x4 square is 495, also close (or at least, not very far) to the true 652 solutions.
comment
A combinatorial problem - counting the solutions
@RolandBacher, the torus is an interesting idea as well! How many generalizations!..
comment
A combinatorial problem - counting the solutions
@ZackWolske, I'm trying the 4x4x4 cube right now, solving it as a #SAT problem. The binomial estimate on it is 11464426695775296878933868168565891023 ($1.1\times10^{37}$), so I think it would be possible to get an exact answer at least on that. The estimate on the tesseract is $2.77\times10^{207}$, only slightly smaller than the original problem.
comment
A combinatorial problem - counting the solutions
@ZackWolske, good question! I'll try it out.
comment
A combinatorial problem - counting the solutions
Actually, there are only 8 choices for the upper-left corner, since the only lines permitted are Right, Down-Right and Down; the rest would touch the border and so are required to be empty. Interesting approach...
comment
A combinatorial problem - counting the solutions
@Geoffrey, yes, exactly. I tried expressing it as a SAT problem and running it through several #SAT solvers, but it was just too big.
comment
A combinatorial problem - counting the solutions
You can also have only two diagonals meeting at a corner - look at the example solution I added. My estimation went as follows: there are exactly 128 horizontal connections: pairs of tiles joined by a horizontal line. There are 240 places for such a connection, so $\binom {240} {128}$ possibilities. Same for verticals. For diagonals, again 128 for each of the two orientations, with 225 possible positions, $\binom {225} {128}$ possibilities. Multiply them all together and you get $3.29\times 10^{272}$.
awarded
revised
A combinatorial problem - counting the solutions
Added a solution for the hard case.
Loading…
comment
A combinatorial problem - counting the solutions
@Timothy, diagonals must continue to the next square. For example, a NW diagonal must meet a SE diagonal. Whether it has a SW or NE diagonal meeting it is absolutely unimportant (but the other diagonal must, of course, meet its match too).
awarded
revised
Loading…
awarded
Loading…