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([i, []])
for i in range(1, N+1):
for j in range(i+1, N+1):
if i + j in targets:
result_list[j-1][1].append([j, i])
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 == 0:
global solution_count
solution_count = solution_count + 1
print("After " + str(recursion_count) + " total calls to 'solve()': solution no " + str(solution_count) + ": ")
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 p in possible_pairs[pos-1][1]:
paired_pos = p[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 mark both positions in the circle, ...
used_pairs.append(p)
pos_taken[pos-1] = True
pos_taken[paired_pos-1] = True
# ... move on to the next position and then...
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 = []
print("possible pairs, ordered by lower number of the pair = ")
print(possible_pairs)
num_pairs = list(map(lambda li: len(li[1]), possible_pairs))
print("number of pairs per lower number of the pair = ")
print(num_pairs)
total_number = functools.reduce(lambda a, b: a+b, num_pairs)
print("total number of pairs = " + str(total_number) )
solve(60)
print()
print("No more solutions")
print("recursive method called " + str(recursion_count) + " times.")