elderly dons | Python Fiddle

import itertools
from sets import Set

# ------- Variables -------

n = 7
lower_boundary = 8
# min_calls = upper_boundary

# ------- Variables -------

def delete_line ():
    print '\033[1A[\033[2K\033[A'

dons = range(n)
lower_boundary = max(lower_boundary - 1, 0)

pairings = list(itertools.combinations(dons, 2))

def try_minimum (minimum):
    strategies = itertools.product(pairings, repeat=minimum)

num_strategies = (n*(n-1)/2)**minimum
    print 'Trying %s different strategies with %s calls ...' % (num_strategies, minimum + 1)
    print '0.0000%'

strategies_tried = 0
    percentage = 0

for strategy in strategies:
        strategies_tried += 1
        if percentage < strategies_tried*1000000/num_strategies:
            percentage = strategies_tried*1000000/num_strategies
            delete_line()
            print '%s.%s%%' % (percentage/10000, str((percentage - percentage/10000*10000)).zfill(4))
        gossip_lists = {}
        for don in dons:
            gossip_lists[don] = Set([don])
        gossip_lists[0] = Set([0,1])
        gossip_lists[1] = Set([0,1])
        for call in strategy:
            gossip_lists[call[0]] = gossip_lists[call[0]] | gossip_lists[call[1]]
            gossip_lists[call[1]] = gossip_lists[call[0]]
        done = True
        for don in dons:
            if len(gossip_lists[don]) != n:
                done = False
        if done:
            return strategy
    return False

minimum = lower_boundary

while True:
    result = try_minimum(minimum)
    delete_line()
    if result != False:
        print 'Minimum found!'
        print 'A minimium of %s calls is necessary. One of the optimal strategies is:' % (minimum + 1)
        print ((0,1),) + result
        break
    minimum += 1

Python Fiddle

Python Cloud IDE