# Enigmatic Code

Programming Enigma Puzzles

## Tantalizer 445: Key problem

From New Scientist #996, 15th April 1976 [link]

Uncle Tom’s bungalow is well endowed with doors, as you can see. He locks them each night, to keep out things that go bump. He would dearly love to do it by passing through each door just once and locking it behind him, so as to finish safely locked up in his bedroom. Alas, it cannot be done. Ah, but wait a minute. It could be done, if he had one of the doors bricked up. By Jove, that’s it.

Precisely which door would he be better without?

[tantalizer445]

### One response to “Tantalizer 445: Key problem”

1. Jim Randell 19 September 2018 at 8:01 am

This Python 3 program runs in 284ms.

Run: [ @repl.it ]

```from collections import defaultdict
from enigma import join, printf

# the doors and the rooms they link
doors = (
'A13', 'B14', 'C12', 'D24', 'E02', 'F34', 'G34',
'H46', 'I35', 'J04', 'K05', 'L05', 'M06', 'N06',
)

# construct the graph: room -> door -> room
graph = defaultdict(dict)
for (d, r1, r2) in doors:
graph[r1][d] = r2
graph[r2][d] = r1

# from room r go through (and lock) k more doors
def solve(r, k, ds=[]):
# are we done?
if k == 0:
yield (ds, r)
else:
# choose an unlocked door
for (d, t) in graph[r].items():
if d in ds: continue
yield from solve(t, k - 1, ds + [d])

# choose a starting room (inside the house)
for r in '123456':
# try to lock 13 of the doors
for (ds, t) in solve(r, 13):
# which door is missing
missing = list(d[0] for d in doors if d[0] not in ds)[0]
printf("missing = {missing} [{r} -> {ds} -> {t}]", ds=join(ds))
break
```

Solution: He would be better without door “C”.

Labelling the rooms 1, 2, 3, 4, 5, 6 and “outside” 0 we can construct a graph with the rooms as nodes and the doors as edges.

A Eulerian path (a path that visits all the nodes using each edge once), can only exist if the start and end node have odd degree and the remaining nodes have even degree.

The nodes in our graph have degrees (= number of doors):

room 0: 6 doors
room 1: 3 doors
room 2: 3 doors
room 3: 4 doors
room 4: 6 doors
room 5: 3 doors
room 6: 3 doors

So we have too many nodes with odd degree. Removing an edge will reduce the degree of the connected nodes by 1, and we can only remove one edge. So we need to remove the edge from two nodes of odd degree that are connected together.

The only two nodes of odd degree that are connected together are 1 and 2. The door between rooms 1 and 2 is C. So eliminating door C gives us a graph where rooms 5 and 6 have odd degree and the remaining rooms have even degree, so we can make a path between room 5 and room 6 that passes through each of the remaining doors. So if one of these rooms is Tom’s bedroom he can start in the other one and finish in his bedroom with all the doors locked.

Here is a diagram of path between rooms 5 and 6 that passes through each door (except C) once.

It might be easier just to keep door C permanently locked, rather than brick it up.

Note that to lock all the doors he will have to leave and re-enter the house 3 times through different doors.

This site uses Akismet to reduce spam. Learn how your comment data is processed.