Skip to main content
3 of 3
Much simpler proof
Victor Stafusa
  • 9.4k
  • 2
  • 33
  • 62

I got a solution with:

42 cells as hallways.

Here it is:

enter image description here


Proof of optimality

Start with 0 hallways. Add the entrance in some edge. This will make 4 rooms accessible. If you start in a corner instead, this will give you 1 less accessible room and will only make your solution less optimal.

Starting add new hallways connected to an existing hallway. Every time you do that, the previous hallway will give access to 1 less room than it used to do. Every time you add a new hallway, at most 3 new rooms become accessible, but if that new hallway will not be a dead-end, one of those new rooms will be turned to the next hallway, so, with the exception of the entrance, each hallway section gives access to at most 2 rooms. Also, to get a new dead-end that gives access to 3 new rooms, you will also need to make a bifurcation that gives you 1 less room, so you still get 2 new reachable rooms per hallway in the best case.

This means that the best you can get is 2 new accessible rooms per hallway, and 1 more than that because the entrance started giving 4. So the number of cells is one more than the triple of the number of hallways. Or put in the other way around, the number of hallways is a third of the number of cells minus one. Hence, $(127 - 1) \div 3 = 42$. So this is the best solution possible.

Thanks to Kruga for the sketch of the proof in a comment and also for Daniel Wagner that also gave something similar in another comment.

Victor Stafusa
  • 9.4k
  • 2
  • 33
  • 62