Hamiltonian cycle

You are given a target number, $N. Write a script to arrange all the whole numbers from 1 up to the given target number into a circle so that every pair of side-by-side numbers adds up to a perfect square. Please make sure that the last number and the first also add up to a square.

Examples

Example 1
Input: $n = 32
Output: 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5,
   31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15
1  + 8  = 9
8  + 28 = 36
28 + 21 = 49
21 + 4  = 25
4  + 32 = 36
32 + 17 = 49
17 + 19 = 36
19 + 30 = 49
so on, all the way through the sequence.

Example 2
Input: $n = 15
Output: ()
No valid circular list of numbers exists.

Example 3
Input: $n = 34
Output: 1, 8, 17, 32, 4, 21, 28, 11, 25, 24, 12, 13, 3, 6, 30, 19, 14,
   22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 4, 34, 15, 10, 26, 23, 2

Analysis

Sir William Hamilton
(1805-65)

Sir William Hamilton was an Irish mathematician, physicist, and astronomer who made an astonishing number of advances in all three fields. Specifically, he described what is now called a Hamiltonian Cycle, which is a path visiting a number of points each of which is connected to two or more other points, the path visiting each point exactly once and ending up at the starting point.

Today's challenge falls within that definition, as each number is 'connected' to any other number where the sum of the two numbers is a square, and I have defined a 'follower' of pont A to be any point B where the values of A and B sum to a square.

The first part of my solution finds all the integer squares which are no greater than 2 * $N - 1. For $N == 32, for example, those will be 4, 9, 16, 25, 36 and 49.

The second part finds the possible followers of each of the integers from 1 to $N. For example, 10 can be followed by 6, 15, and 26.

Now let's try to form the circle. The obvious way to proceed is to start with some number (I chose 1) and examine all the sequences of possible followers to see if we get back to 1.

The simplest way to do that is to use a recursive subroutine try($j) which finds all the followers of a given number, and then calls itself to find the followers of the followers and so on. In doing this, of course, it can eliminate paths which get back to a number already in the path.

I initially thought this would be quite slow, and indeed it is if $N is larger than 40, but it is adequate to show that there are no solutions for $N < 32 and then at least one solution for each $N up to 40. My solution gets rapidly slower beyond that but I postulate (without proof) that solutions exist for most or all larger numbers.

The circle can of course start at any point, and is equally valid if reversed.

I submitted this challenge having come across it by chance, and it was Mohammad who identified it as a Hamiltonian cycle.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge/382/1

use v5.26;    # The Weekly Challenge - 2026-07-13
use utf8;     # Week 382 - task 1 - Hamiltonian cycle
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

my ($count, @followers, $output);

for (5, 10, 20, 30 .. 36) {
    hamiltonian_cycle($_);
}

sub hamiltonian_cycle {
    
    my ($i, @squares, $s, $possible);
    
    # find squares from 2 to 2 * $count - 2
    $count = $_[0];
    for $i (2 .. 99) {
        last if $i ** 2 > 2 * $count - 1;
        push @squares, $i ** 2;
    }
    
    # find the numbers that can follow $a
    @followers = ();
    for $a (1 .. $count) {
        for $s (@squares) {
            $possible = $s - $a;
            last if $possible > $count;
            next if ($possible <= 0 or $possible == $a);
            $followers[$a] .= qq[~$possible~];
        }
    }

    # start with 1 and complete recursively
    $output = '';
    try ([1]);
    
    # report
    say qq[\nInput:  $count];
    say qq[Output: ] . ($output or 'none found');
}

sub try {   # adds a valid number to @so_far
    
    my (@so_far, $last, @trial, $this);
    
    # do we have all the numbers?
    @so_far = @{$_[0]};
    if (@so_far == $count) {
        
        # and is the first number a follower of the last?
        if ($followers[$so_far[$count - 1]] =~ m|~$so_far[0]~|) {
            $output = join(', ', @so_far);
            return;
        }
    }
    
    # else recurse by appending each of the followers of the
    # last one added
    $last = $so_far[-1];
    F: while ($followers[$last] =~ m|(\d+)|g) {
        $this = $1;
        
        # can't add one we've already added
        for (@so_far) {
            next F if $this == $_;
        }
        
        # good so far so add another number
        @trial = @so_far;
        push @trial, $this;
        try (\@trial);
        
        # found an answer!
        return if $output;
    }
}

33 lines of code

Output from script

Input:  5
Output: none found

Input:  10
Output: none found

Input:  20
Output: none found

Input:  30
Output: none found

Input:  31
Output: none found

Input:  32
Output: 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5,
   31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15

Input:  33
Output: 1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5,
   20, 29, 7, 18, 31, 33, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15

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

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

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