Enigmatic Code

Programming Enigma Puzzles

Tantalizer 494: Moaning at the bar

From New Scientist #1045, 31st March 1977 [link]

Burpwater’s Best is not the greatest of beers and is to be had only in the five pubs owned by the brewery. The customers are so rude about it that the landlord keeps putting in for transfers. Until four years ago these requests were always refused but there was then a change of policy, resulting in complete annual reshuffles. Now, after four such upheavals, each landlord has had a disgruntled go at running four of the pubs and it at present ensconced in the fifth.

Patrick’s first move was from the Duck to the Anchor and his next to the Cormorant. This second shuffle took Quentin to the Eagle and Roger to the pub previously run by Tony. At the third move Tony handed the Bull over to Roger, who took over from Simon at the following move.

Where is each gloomy publican to be found now?

[tantalizer494]

Advertisements

One response to “Tantalizer 494: Moaning at the bar

  1. Jim Randell 4 January 2017 at 9:15 am

    This puzzle essentially amounts to completing a Latin square [ https://en.wikipedia.org/wiki/Latin_square ]. I think it’s easier to solve this puzzle by hand, but here’s a Python 3 program that solves Latin squares – it tackles this puzzle in 71ms.

    from collections import defaultdict
    from enigma import update, join, printf
    
    # solve a latin square
    # each row column must contain all the symbols
    def solve(grid, symbols):
    
      # symbols in each row and each column
      fn = (lambda x: x is not None)
      rows = list(set(filter(fn, row)) for row in grid)
      cols = list(set(filter(fn, col)) for col in zip(*grid))
    
      # find the possibilities for each square
      ps = defaultdict(list)
      for (r, row) in enumerate(rows):
        for (c, col) in enumerate(cols):
          if grid[r][c] is None:
            p = symbols.difference(row, col)
            ps[len(p)].append((r, c, p))
    
      # is the grid solved?
      if not(ps):
        yield grid
    
      else:
        # look at the smallest number of possibilities
        m = min(ps.keys())
    
        # 0 possibilities => impossible grid
        if m == 0:
          return
    
        # we can fill out any squares with only 1 possibility
        elif m == 1:
          grid = list(list(row) for row in grid)
          for (r, c, vs) in ps[m]:
            grid[r][c] = list(vs)[0]
          # and solve for the remaining squares
          yield from solve(grid, symbols)
    
        # otherwise choose a value and try each possibility in turn
        else:
          (r, c, vs) = ps[m][0]
          for v in vs:
            row = update(grid[r], [(c, v)])
            # solve for the remaining squares
            yield from solve(update(grid, [(r, row)]), symbols)
    
    
    # labels for the publicans
    labels = (P, Q, R, S, T) = 'PQRST'
    X = None
    
    # initial grid
    # "P's first move was from D to A and his next to C"
    # "The second shuffle took Q to E"
    # "At the third move T handed B over to R"
    grid = [
      # A  B  C  D  E
      [ X, X, X, P, X ], # 0
      [ P, X, X, X, X ], # 1 (after move 1)
      [ X, T, P, X, Q ], # 2
      [ X, R, X, X, X ], # 3
      [ X, X, X, X, X ]  # 4
    ]
    
    # solve the grid
    for g in solve(grid, set(labels)):
    
      # check the remaining conditions:
      # "The second shuffle took R to the pub previously owned by T"
      if g[2].index(R) != g[1].index(T): continue
      # "R took over from S on the fourth move"
      if g[4].index(R) != g[3].index(S): continue
    
      # output a solution
      printf("   A B C D E")
      for (i, row) in enumerate(g):
        printf("{i}: {row}", row=join(row, sep=' '))
      printf()
    

    Solution: Quentin runs The Anchor; Patrick runs The Bull; Roger runs The Cormorant; Simon runs The Duck; Tony runs The Eagle.

    There is only one way the table can be filled out:

    tantalizer-494

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: