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

    See also: Enigma 25, Enigma 108, Enigma 120, Enigma 1338.

    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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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

%d bloggers like this: