import functools
# function which calculates and returns the set of all possible pairs of numbers
# from 1...N which satisfy the condition that their sum is in the targets set
def possible_pairings(N, targets):
result_list = []
for i in range(1, N+1):
result_list.append([])
for i in range(1, N+1):
for j in range(1, N+1):
if i != j and i + j in targets:
result_list[i-1].append(j)
return result_list
# global counter to keep track of the number of solutions found
solution_count = 0
# global counter to keep track of the number of recursive solver calls
recursion_count = 0
# recursive solver procedure
def solve(pos):
global recursion_count
recursion_count = recursion_count + 1
# if all positions in the circle have been taken,
# a solution to the puzzle has been found
if pos == N+1:
global solution_count
solution_count = solution_count + 1
log = "After " + str(recursion_count) + " total calls to 'solve()': "
log = log + "solution no " + str(solution_count) + ": "
print(log)
print(used_pairs)
# if the current position in the circle has already been taken by the second
# element of a pair placed earlier, then move on to the next position
elif pos_taken[pos-1]:
solve(pos+1)
else:
# else iterate over all possible pairs for the current position
for paired_pos in possible_pairs[pos-1]:
# if the position of the pair's second element is also available...
if not pos_taken[paired_pos-1]:
# ... then remember the currently used pair
# and tentatively mark both positions in the circle.
used_pairs.append([pos, paired_pos])
pos_taken[pos-1] = True
pos_taken[paired_pos-1] = True
# The above three lines already simulate the current move;
# check its effects before actually making the move
# and stepping one level down the tree.
# positive assumption: all future pairs reachable, i.e. for
# every position not yet taken, there exists a pair position
# not yet taken
all_future_pos_reachable = True
# for every future position, try to prove assumption wrong
for p in range(pos+1, N+1):
if not pos_taken[p-1]:
# negative assumption: no more pair position available
paired_p_reachable = False
# try to prove assumption wrong
for paired_p in possible_pairs[p-1]:
if not pos_taken[paired_p-1]:
paired_p_reachable = True
if not paired_p_reachable:
all_future_pos_reachable = False
if all_future_pos_reachable:
# move on to the next position
solve(pos+1)
# trace back by releasing the used pair
# and unmarking the two positions in the circle
used_pairs.pop()
pos_taken[pos-1] = False
pos_taken[paired_pos-1] = False
# upper bound N of the interval of numbers 1...N in the circle
N = 60
# set of target numbers for the pairs
targets = (9, 36, 49, 64, 81)
# the set of possible pairs which satisfy the target
possible_pairs = possible_pairings(N, targets)
# list of the positions 1 ... N to keep track of
# which are already taken and which are still unoccupied
pos_taken = []
for i in range(1, N+1):
pos_taken.append(False)
# list of all the pairs currently used in the backtracking algorithm
used_pairs = []
log = "Calculating Rainbow Pairs for 1 ... " + str(N)
log = log + " for target set " + str(targets) + ":"
print(log)
print()
print("Possible partner positions for each position 1 ... " + str(N) + ":")
print(possible_pairs)
print()
li = list(map(lambda li: len(li), possible_pairs))
num_pos_pairs = round(functools.reduce(lambda a, b: a+b, li)/2)
print("Number of possible pairs: " + str(num_pos_pairs))
solve(1)
print()
log = "Calculation terminated. " + str(solution_count)
log = log + " solutions found with " + str(recursion_count)
log = log + " calls to recursive solver function."
print(log)