5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ It would also be useful to know the answer for larger cubes or cuboids, but I don't know if this is like an NP problem or something that would take forever to analyze for bigger sizes. $\endgroup$ Commented Jan 4, 2021 at 23:20
  • $\begingroup$ This is closely related to but not quite a special case of the dominating set problem, which in full generality is NP-complete (nitt.edu/home/academics/departments/cse/faculty/kvi/…). But I think this special case is nice enough that it should be easier. I think your $18$ generators is best possible but I don't see a clean way to prove it other than to just work through all the possible configurations of wire blocks up to symmetry. $\endgroup$ Commented Jan 5, 2021 at 0:32

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .