4 ms·

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.

by 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. # . . . . # . . . . # . . . # . . . . # . . . . . . . . # . . . . # . . . # . . . . # . . . . # . . . # . . . . # . . . # . . . . # . . . . # . . . # . . . . # . . . . . . . . # . . . . # . . . # . . . . # . . . . # . . . # . . . . # . . . # . . . . # . . . . # . . . # . . . . # . . . .

by vitus 6y ago

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. # . . . . # . . . . # . . . # . . . . # . . . . . . . . # . . . . # . . . # . . . . # . . . . # . . . # . . . . # . . . # . . . . # . . . . # . . . # . . . . # . . . . . . . . # . . . . # . . . # . . . . # . . . . # . . . # . . . . # . . . # . . . . # . . . . # . . . # . . . . # . . . .