3 ms·

A related question I once thought of: What’s the minimum number of pieces you need to assemble to form a “skeleton” of a puzzle - such that every other piece fi

• vitus 6y ago
  An (obvious?) iterative improvement on this solution is to just take the first two rows and mirror it for the bottom two, for a solution of 4x3=12 pieces. -X--X--X- -X--X--X- -X--X--X- -X--X--X- The naive lower bound on a solution is N/5, based on the maximum covering a piece might have (of course, that's not tight, due to literal corner cases). Heuristically, we might expect an optimal solution to look like E[1/K]≈8.6, where K is defined as the number of neighbors a square has. Attempting to manually reduce the overlaps, I came up with -X--X--X- ---X-X--- X-------X --X-X-X-- for 10. (Of course, the puzzle may be underspecified, since if you also require that your skeleton forms a connected component, then neither of these solutions count.) edit: And, one more manual tiling (10 again) which exhibits better periodicity: --X---X-- X---X---X --X---X-- X---X---X
  • cipherboy 6y ago
    I don't think nine is possible, only 10. https://gist.github.com/cipherboy/dc14769830d74a0f783c7ae29b8682e0 https://gist.github.com/cipherboy/dc14769830d74a0f783c7ae29b...
  • mahathu 6y ago
    That's an interesting answer! Your final layout looked oddly familiar to me, and it finally occurred to me: The problem of finding a skeleton puzzle was very similar to finding an optimal layout for a sugarcane farm in Minecraft, that my high school friends and I experimented with years ago. Each square of sugarcane needs to be connected to at least one square of water, and the most efficient farm is the one requiring the least amount of space for water. https://i.imgur.com/T5yh9.jpg https://i.imgur.com/T5yh9.jpg
  • Schoolmeister 6y ago
    That's actually an NP-complete problem, called the Dominating Set problem[0]. One application of this problem is used in OLSR[1], a routing protocol used in Mobile Ad-Hoc Networks (MANET). To see how it is useful for MANETs, you can look at the problem in a different, but equivalent, way. Namely, try to find the smallest subset D of nodes (puzzle pieces), such that every two nodes that are not in D are connected to each other through a node in D. In the case of MANETs, these nodes are wireless stations. The nodes in the Domating Set are chosen to relay broadcasting messages for their neighbours. This way congestion on the medium is reduced but every node can still send and receive broadcasts. [0] https://en.wikipedia.org/wiki/Dominating_set https://en.wikipedia.org/wiki/Dominating_set [1] https://en.wikipedia.org/wiki/Optimized_Link_State_Routing_Protocol https://en.wikipedia.org/wiki/Optimized_Link_State_Routing_P...
  • gjm11 6y ago
    In the limit of very large puzzles, N/5 is right. # . . . . # . . . . # . . . # . . . . # . . . . . . . . # . . . . # . . . # . . . . # . . . . # . . . # . . . . # . . . # . . . . # . . . . # . . . # . . . . # . . . . . . . . # . . . . # . . . # . . . . # . . . . # . . . # . . . . # . . . # . . . . # . . . . # . . . # . . . . # . . . .
• robinhouston 6y ago
  It turns out that the answer to this question is known for all sizes of grid[1], though it was found fairly recently (2011) and the answer for small grids is quite complicated. For the 9x4 grid, the optimal number is indeed 10. For large n×m grids, with n and m ≥ 16, the minimum number is: floor((n + 2)(m + 2) / 5) - 4. The linked paper has a full-page table giving the formulae for small grids. Thanks to Schoolmeister for mentioning the name of this problem, which gave me the right terms to search for. 1. https://arxiv.org/abs/1102.5206 https://arxiv.org/abs/1102.5206