brute-force count of the number of Hamiltonian paths on the surface of a cube from a given starting vertex

cube.rb

require 'set'

class Hash
  def dig(key, *rest)
    if value = (self[key] rescue nil)
      if rest.empty?
        value
      elsif value.respond_to?(:dig)
        value.dig(*rest)
      end
    end
  end
end

# adjacency matrix
adj = {
  1 => Set.new([2,3,4]),
  2 => Set.new([1,5,7]),
  3 => Set.new([1,5,6]),
  4 => Set.new([1,6,7]),
  5 => Set.new([2,3,8]),
  6 => Set.new([3,4,8]),
  7 => Set.new([2,4,8]),
  8 => Set.new([5,6,7])
}

n_paths = 0

# all hops except for the last one
hops = (0..5)

# brute force, try all 7! possibilities and count the Hamiltonian paths among them
[2,3,4,5,6,7,8].permutation do |path|
  if adj[path[0]].include?(1) && hops.find{|n| !adj[path[n]].include?(path[n+1])}.nil?
    puts path.to_s
    n_paths += 1
  end
end

puts "number of paths: #{n_paths}"