Implementation of daily programming challenge 348 Hard. Not a useable solution, because it fails to complete the challenge in an appropriate time

348h.rb

#!/usr/bin/env ruby
# Copyright © 2018 Taylor C. Richberger <taywee@gmx.com>
# This code is released under the MIT license

require 'set'

def square?(number)
  Math.sqrt(number).round ** 2  == number
end

def build(progress, available, total, &block)
  if progress.size == total
    yield progress
    return
  end
  # Valid pairs include the current tail.  These are "valid" in that they
  # contain the next valid number.
  valid = available.select do |pair|
    pair.include? progress.last
  end
  # If there is no next valid number, this path is a failure.
  return if valid.empty?
  # Nextavailable are all the pairs without the current valid set, because all
  # the "valid" pairs contain a number that is going to be masked
  nextavailable = available.reject do |pair|
    valid.include? pair
  end

  # Early exit if this route can't possibly solve it, because too few numbers
  # remain to reach the total
  amountleft = Set.new(nextavailable.flatten).size
  return if total - (progress.size + 1) > amountleft

  # Take the valid numbers and extract the number that isn't the current tail
  checknumbers = valid.map do |pair|
    pair.reject {|num| num == progress.last}.first
  end

  # Recurse
  checknumbers.each do |num|
    nextprogress = progress + [num]
    build(nextprogress, nextavailable, total, &block)
  end
end

def main!
  highest = Integer(ARGV.shift)
  pairs = Set.new
  (1..highest).each do |a|
    ((a + 1)..highest).each do |b|
      if square? a + b
        pairs << Set[a, b]
      end
    end
  end

  # early-out if any numbers are not present in valid pairs
  unless (1..highest).all?(&pairs.flatten.method(:include?))
    raise "No solution for input '#{highest}'"
  end

  # Find all numbers that are only present in a single pair
  singles = pairs.map(&:to_a).flatten.group_by(&:itself).map(&:last).select do |a|
    a.size == 1
  end.map(&:first).to_set

  occurrences = Hash.new {|hash, key| hash[key] = 0}

  # Each element that is present in only a single pair must be at the beginning
  # or end.  If more than two are present, a solution is impossible
  raise "No solution for input '#{highest}'" if singles.size > 2

  # Sort everything low edge-count to high, which typically finds a solution
  # quicker
  pairs.each do |pair|
    a, b = pair.to_a
    occurrences[a] += 1
    occurrences[b] += 1
  end
  starters = occurrences.sort_by(&:last).map(&:first)
  pairs = pairs.sort_by do |pair|
    a, b = pair.to_a
    occurrences[a] + occurrences[b]
  end

  starters.each do |starter|
    build([starter], pairs.dup, highest) do |solution|
      puts solution.join(' ')
      exit
    end
  end
  puts "No solution exists"
end

main!