'Circle of Squares' programming challenge
 

In his Amazing Circle thread, igadoter presented us with a circle of data consisting of the numbers 1 thru 32. The amazing part was that each adjacent pair of numbers when summed yielded a perfect square. He asked for a programmatic way to verify that the conditions were met for the particular sequence of 32 numbers that he supplied, which program was offered by danielbmartin. Others, including myself, have wondered about the possibility of programmatically generating such an amazing circle of numbers, so I hereby issue the programming challenge. Here are the rules:

1. The data must be a logical circle or ring of data, in which there is no defined first and last element, and no defined direction or flow (can be clockwise or counter-clockwise);

2. Each element in the ring must be within the defined limits. In this case, between 1 and 32, with each number occurring exactly once (in any order).

3. Each adjacent pair of numbers must sum to a perfect square. [1, 4, 9, etc] 'Adjacent pair' is defined per rule #1 above. That is, if you define the ring as a linear array, the array must 'wrap around' so that the first and last elements are considered logically adjacent.

Let's have a little fun with this, and, as others have suggested, maybe carry it further than limits of 1 to 32.

To start things off, I offer the following data ring class definition, FWIW. This has probably been done before and better, but it's where I'm beginning, as a C++ header, to help me to define and work with a specific ring of data.

I would define a check like function which will return true if the sum of the given adjacent pair of numbers is square. But we can have different conditions, later....
https://www.includehelp.com/c-progra...re-or-not.aspx

First creates a linklist of all possible pair combinations, then recursively finds the next value in the sequence backtracking if it dead-ends.

P.S. I left the result in an array. It would be trivial to create a linklist from it and then point the last entry back to the first to make it circular, but it seemed kind of pointless, and I was more interested in doing the sequence generation functions.

update:
attached program now takes start value as first arg .

I created my list of pairs manually. Otherwise, this is precisely what i've been trying since early yesterday. But so far, it dead ends every time.

If i suspend randomness, it seems to make a big difference what digit i start with, which intuitively should not be. In at least two cases, i've gotten as far as a 31 byte array:
which, as you can see, does indeed wrap around to form a ring of squares, and is a different order than the original amazing circle. But there are only 31, not 32 digits. The missing digit is 2, which does not fit into any point in the 31 byte circle. There are a number of other circles of fewer than 32 digits; that doesn't meet the challenge.

I haven't yet figured out why i can't get the above sequence if i start with, say, '21' or some other digit. Perhaps my backtracking logic need some tweaking. Or perhaps a completely different approach. If you get a full 32 byte circle, I'd love to see your code.

Attached to post #4 (now updated to take a start arg).

This may not be all possible sequences, my code just returns the first complete valid sequence it finds for each start point.

I'll look forward to seeing other approaches.

I did not check all of them, but they look identical (just the first number is different, but the order is the same).

I have not yet had a chance to write any code, or even decide what I want to write! But I did write on paper a list of all the possible pairings which sum to perfect squares and thinking about what I see in that list leads to a set of constraints for generating a complete ordering, as well as placing limits on the number of integers in the ring (32 may represent a limit!).

I'll defer posting my own observations but offer the following helpful hints:

* There aren't really a great number of choices - the possible pairs are tightly constrained in "families" of number of choices
* Each choice, where there is a choice, further constrains the next choice
* Using the clues suggested by the above list, think in terms of segments (arcs) of one or more pairs, then join the segments

On paper I was able to find (generate) a 32 number solution quickly (or perhaps accidentally!)

My routine is deterministic with no random element, so one should expect to see common sequences of varying length reoccurring when it is possible. It will only diverge when an already used number forces a different path. Look closer and you'll see this to be true.

I have written a C routine which implements my thoughts on building the circle from segments (refined pencil and paper method). Instead of trying all possible combinations as Gazl has done, I successively pair everything that is fully deterministic and then test for any left overs.

The segments are doubly linked lists and the strategy is:

1. Connect all deterministic pairings into segments (those integers with only two possible pairing partners)
2. Connect all deterministic segment end pairs (segment ends with only one possible partner)
3. If the result is a ring then there is only one solution and its mirror, it is fully deterministic.

When run it produces the result below. The numbers in parenthesis are the sum of leading and trailing pairs. I set the circle entry to 4 only to orient the result with the original post's example, but it is a doubly linked ring of integers.

Code to follow after sleep!

those are all identical:
http://paste.ubuntu.com/p/SPtYcSByZd/

I disabled pairs printing. Just here what I got
Above 32 it doesn't work. So all sequences by your program are
so there are only up to 32 all of them? Program is deterministic.

edit: but they are essentially the same - it's circle - if sequences differ only by left/right shift.

edit: so the question is about two sequences being the same - say 1,2,3,1,2,3,1,...should be considered the same as 2,3,1,2,3,1,...

oh men look at this
they are mirrors! Read forward, read backward gives the same.

not identical. there is reversal on some sequences. I never claimed it would find multiple sequences, only that it would generate a valid result given any start point.

Look carefully. All these above sequences are in fact the same up to mirror. It is not difficult to create up to test that the above sequences are the same up to mirroring. The first starts with 1 reaches 2 - now read backward from this point and compare with sequence starting with 2 - they are the same.

Edit: For me it looks like all these sequences are the same - and the same as original sequence. So seems tha GazL showed us - computer proof - there is only one such sequence. If there are no other possibilities. Congrats! But if it is true - challenge is finished.

Edit: here what is more challenging #n - number of different sequences with the property as amazing circle for given n - seems that #32 = 1 - only one sequence. What about #123? Reasonable sequence is when there is algorithm to compute it - say Fibonacci - there is page on internet with "all" up to date known sequences - if you will find new one - fame awaits you.

Have to credit Gazl with first meeting the challenge of generating a valid 32 element circle of squares. But, with his own caveat:
I will try to study Gazl's code to understand why my (similar) approach didn't work. Meanwhile will try to employ something more like Astrogeek's:

This approach sounds more likely to generate multiple sequences, if such multiple sequences exist, or to definitively prove that there is only one valid 32 element Ring. Keeping in mind that every valid Ring can be expressed as an array of 64 permutations, for 32 head points * 2 directions.

Yes, please let us see your code!