Efficient Sorting Algorithm

 Here is a problem that I came across today. Here is the link.

Place each of the numbers from 1 to 15 into the spaces provided so that the sum of any two consecutive spaces is a square number. The following clue was provided: the number 8 must be placed on one end and the number 9 must be placed on the other end.

Without the clue, there are a staggering 1,307,674,368,000 possible permutations (that's over one trillion) but with the clue this reduces to 6,227,020,800 or a little over six billion. However, the clue is very helpful because we know that next to 8 we can only place a 1 and next to the 9 we can only place a 7. So we have: $$9, 7, x, x, x, x, x, x, x, x, x, x, x, 1, 8$$ Now next to the 7 we can only place a 2 and next to the 1 we can only place a 15, so we now have:$$9, 7, 2, x, x, x, x, x, x, x, x, x, 15, 1, 8$$Next to the 2 we can only place 14 and next to the 15 we can only place a 10. This gives $$9, 7, 2, 14, x, x, x, x, x, x, x, 10, 15, 1, 8$$ Continuing this process, we find 14 can only be paired with 11 and 10 with 6. We now have: $$9, 7, 2, 14, 11, x, x, x, x, x, 6, 10, 15, 1, 8$$ We then quickly reach our solution:

The key to solving the problem is to begin and end the sequence of numbers with 8 and 9 or vice versa because these two initial choices determine all the remaining numbers. I asked Gemini to write a Python program to solve the problem but without giving it any clues. I also asked it to explain its thinking. Figure 1 is what it came up with, in about 67 lines of code.

Figure 1: Gemini Link

Here is how Gemini described its thinking:

$\textbf{Reasoning and Strategies:}$

is_square(n) $\textbf{Function}$:

• This function efficiently checks if a number is a perfect square. It calculates the integer square root and compares its square to the original number. 

find_next(current_sequence, remaining_numbers) $\textbf{Function (Recursive Backtracking:)}$

• This function uses recursion to explore possible sequences.
• It checks if the current sequence is complete (no remaining numbers).
• For each remaining number, it checks if it forms a square sum with the last number in the current sequence.
• If a square sum is found, it adds the number to the sequence and recursively calls itself with the updated sequence and remaining numbers.
• If no valid next number is found, it backtracks. 

$\textbf{Optimization}$ 

$\textbf{Precompute Possible Pairs (Graph Representation): }$

• Instead of repeatedly checking for square sums, we precompute all possible pairs of numbers that add to a square.
• This is stored in the possible_pairs dictionary, which represents a graph where numbers are nodes, and edges exist between numbers that form a square sum.
• This optimization significantly reduces the number of square sum calculations. 

$\textbf{Optimization}$ 

$\textbf{Start with Numbers with Fewer Possible Pairs:}$

• The sorted_numbers list is created by sorting the numbers based on the number of possible pairs they have.
• Starting the search with numbers that have fewer possible pairs reduces the branching factor in the recursive search. This means the algorithm explores fewer potential paths, leading to faster results.
• This is a heuristic that helps avoid exploring large portions of the search space that are unlikely to lead to a solution. 

$\textbf{Backtracking Efficiency}:$

• The recursive backtracking algorithm is designed to efficiently explore the search space. When a dead end is encountered (no valid next number), the algorithm immediately backtracks to the previous decision point, avoiding unnecessary exploration of other paths.
• By combining the precomputation of possible pairs and the heuristic of starting with numbers with fewer options, the backtracking algorithm becomes much more efficient than a naive brute-force approach.

The algorithm (permalink) is easily adapted for longer runs of numbers. For example, let's say we want to arrange the number from 1 to 35. Here is one configuration (generated almost instantly):

[18, 7, 2, 14, 11, 5, 31, 33, 3, 22, 27, 9, 16, 20, 29, 35, 1, 8, 28, 21, 4, 32, 17, 19, 6, 30, 34, 15, 10, 26, 23, 13, 12, 24, 25] ... permalink