Task 1: Hamiltonian Cycle
Given an integer $n > 0, find a sequence of numbers from 1 to $n such that every adjacent pair (including the first and last) sums to a perfect square.
Example Output
Input: $n = 15
Output: (1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25) (e.g.)
Logic
Build an adjacency graph of numbers 1..n where edges represent pairs summing to a perfect square. Use Depth-First Search with backtracking to find a full Hamiltonian cycle starting and ending at connected square sums.
Perl Solution
ch-1.pl
sub hamiltonian_cycle ($n) {
return [] if $n < 1;
my %squares;
for ( my $i = 2 ; $i * $i <= 2 * $n ; $i++ ) {
$squares{ $i * $i } = 1;
}
my %adj;
for my $i ( 1 .. $n ) {
for my $j ( $i + 1 .. $n ) {
if ( $squares{ $i + $j } ) {
push @{ $adj{$i} }, $j;
push @{ $adj{$j} }, $i;
}
}
}
my @path = (1);
my %visited = ( 1 => 1 );
return _dfs( $n, 1, \%adj, \%squares, \@path, \%visited );
}
Python Solution
ch-1.py
def hamiltonian_cycle(n: int) -> list[int]:
"""Find a Hamiltonian cycle of numbers 1..n where adjacent sum to square."""
if n < 1:
return []
squares = {i * i for i in range(2, int((2 * n) ** 0.5) + 2)}
adj: dict[int, list[int]] = {i: [] for i in range(1, n + 1)}
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
if (i + j) in squares:
adj[i].append(j)
adj[j].append(i)
path = [1]
visited = {1}
def dfs(u: int) -> list[int] | None:
if len(path) == n:
if (path[0] + path[-1]) in squares:
return list(path)
return None
for v in adj[u]:
if v not in visited:
visited.add(v)
path.append(v)
res = dfs(v)
if res is not None:
return res
path.pop()
visited.remove(v)
return None
res = dfs(1)
return res if res is not None else []
Task 2: Replace Question Mark
Given a string containing only digits and '?', replace every '?' with a digit (0-9) such that no two adjacent characters are identical. Return all possible valid strings.
Example Output
Input: $str = "?"
Output: ("0", "1", "2", "3", "4", "5", "6", "7", "8", "9")
Input: $str = "1?1"
Output: ("101", "121", "131", "141", "151", "161", "171", "181", "191")
Logic
Using backtracking, find each '?' position and try all digits from '0' to '9' that do not match the character immediately before or after it.
Perl Solution
ch-2.pl
sub replace_question_marks ($str) {
my @results;
_helper( $str, 0, \@results );
return \@results;
}
sub _helper ( $str, $idx, $results ) {
my $len = length($str);
while ( $idx < $len && substr( $str, $idx, 1 ) ne '?' ) {
$idx++;
}
if ( $idx == $len ) {
push @$results, $str;
return;
}
my $prev = ( $idx > 0 ) ? substr( $str, $idx - 1, 1 ) : '';
my $next = ( $idx < $len - 1 ) ? substr( $str, $idx + 1, 1 ) : '';
for my $d ( 0 .. 9 ) {
my $char = "$d";
next if $char eq $prev || $char eq $next;
my $new_str = $str;
substr( $new_str, $idx, 1, $char );
_helper( $new_str, $idx + 1, $results );
}
}
Python Solution
ch-2.py
def replace_question_marks(str_val: str) -> list[str]:
"""Replace all '?' with digits such that no adjacent digits are equal."""
results: list[str] = []
chars = list(str_val)
n = len(chars)
def helper(idx: int) -> None:
while idx < n and chars[idx] != "?":
idx += 1
if idx == n:
results.append("".join(chars))
return
prev_char = chars[idx - 1] if idx > 0 else ""
next_char = chars[idx + 1] if idx < n - 1 else ""
for d in range(10):
char_d = str(d)
if char_d == prev_char or char_d == next_char:
continue
chars[idx] = char_d
helper(idx + 1)
chars[idx] = "?"
helper(0)
return results