How many generator blocks can I fit inside a $3\times3\times3$ cube?

Question

In my Minecraft world I have a $3\times3\times3$ cube of space which I want to fill with $1\times1\times1$ generator and wire blocks.

I can install a single outlet as part of the room's wall; it takes up none of the $3\times3\times3$ space.

Each generator block must be connected to the outlet through wires, so for each generator there is always a path of adjacent wire blocks that goes from that generator to the outlet. Diagonal neighbors are not adjacent in this case. The outlet can only be touching one block, it can't be installed on the edge between blocks.

I can choose where to place the generators, wires, and outlet. I want to fit as many generators as I can.

I can see a way to get $18$ powered generators, if the middle layer is $9$ wire blocks and the top and bottom layers are $9$ and $9$ generator blocks. But I can't tell if this is the maximum possible.

Answer 1

You can solve the problem via integer linear programming as follows. Let $[n]=\{1,\dots,n\}$, and for each cell $(i,j,k)\in [n] \times [n] \times [n]$, let $N_{i,j,k}$ be the set of neighboring cells. Let binary decision variable $g_{i,j,k}$ indicate whether cell $(i,j,k)$ is a generator, and let binary decision variable $w_{i,j,k,d}$ indicate whether cell $(i,j,k)$ is a wire block at distance $d$ from the outlet. The problem is to maximize $\sum_{i,j,k} g_{i,j,k}$ subject to \begin{align} g_{i,j,k} + \sum_{i,j,k,d} w_{i,j,k,d} &\le 1 &&\text{for all $i,j,k$} \tag1 \\ g_{i,j,k} &\le \sum_{(\bar{i},\bar{j},\bar{k})\in N_{i,j,k}} \sum_d w_{\bar{i},\bar{j},\bar{k},d} &&\text{for all $i,j,k$} \tag2 \\ w_{i,j,k,d} &\le \sum_{(\bar{i},\bar{j},\bar{k})\in N_{i,j,k}} w_{\bar{i},\bar{j},\bar{k},d-1} &&\text{for all $i,j,k,d$} \tag3 \\ \sum_{i,j} w_{i,j,k,0} &= \begin{cases}1 &\text{if $k=1$}\\0 &\text{otherwise}\end{cases} &&\text{for all $k$}\tag4 \end{align} Constraint $(1)$ prevents a cell from simultaneously being a generator and a wire block. Constraint $(2)$ enforces a generator to be adjacent to a wire block. Constraint $(3)$ enforces a wire block at distance $d$ to be adjacent to a wire block at distance $d-1$. Constraint $(4)$ enforces the unique outlet to be along the $k=1$ wall (without loss of generality).

For $n=3$, the maximum does turn out to be $18$.