Hacker News Reader

Comment by pansa2 | Hacker News Reader

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 fits directly to one of the skeleton pieces?

For an 9x4 puzzle I came up with the following pattern - a skeleton that uses 15 of 36 pieces:

    -X—-X—-X-
    -X—-X—-X-
    XXXXXXXXX
    —————————

It would be interesting to see if that’s optimal, and if the optimal solution is different for different puzzle sizes.

View on HN

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

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

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

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

[1] https://en.wikipedia.org/wiki/Optimized_Link_State_Routing_P...

In the limit of very large puzzles, N/5 is right.

  # . . . . # . . . . # .
  . . # . . . . # . . . .
  . . . . # . . . . # . .
  . # . . . . # . . . . #
  . . . # . . . . # . . .
  # . . . . # . . . . # .
  . . # . . . . # . . . .
  . . . . # . . . . # . .
  . # . . . . # . . . . #
  . . . # . . . . # . . .
  # . . . . # . . . . # .
  . . # . . . . # . . . .

I don't think nine is possible, only 10.

https://gist.github.com/cipherboy/dc14769830d74a0f783c7ae29b...

Reply on news.ycombinator.com