Comment

Comment by vitus

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
parent vitus 6 years ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton