Find a sequence from 1..n where each adjacent pair adds up to a perfect square.

parker.go

package main

import (
	"fmt"
	"os"
	"strconv"
)

// PerfectSquaresIn builds a list of perfect squares smaller or equal than n.
func PerfectSquaresIn(n int) []int {
	squares := make([]int, 0)
	sum := 1
	for i := 3; sum <= n; i += 2 {
		squares = append(squares, sum)
		sum += i
	}
	return squares
}

// PerfectSquareGraph builds a edge hashmap of a graph,
// where each node is connected to another node if they
// both add up to a perfect square number.
func PerfectSquareGraph(n int) map[int][]int {
	squares := PerfectSquaresIn(2*n - 1)
	edges := make(map[int][]int)
	for i := 1; i <= n; i++ {
		to := make([]int, 0)
		for _, s := range squares {
			if s <= i || s-i > n {
				continue
			}
			to = append(to, s-i)
		}
		edges[i] = to
	}
	return edges
}

// FindHamiltonianPath looks for a hamiltonian path in the graph.
// Returns nil, if none is found.
func FindHamiltonianPath(n int, graph map[int][]int, path []int) []int {
	if path != nil {
		l := len(path)
		if l == n {
			return path
		}
		head := path[l-1]
		for _, edge := range graph[head] {
			alreadyVisited := false
			for _, visited := range path {
				if edge == visited {
					alreadyVisited = true
					break
				}
			}
			if !alreadyVisited {
				pathCopy := make([]int, l+1)
				copy(pathCopy, path)
				pathCopy[l] = edge
				finished := FindHamiltonianPath(n, graph, pathCopy)
				if finished != nil {
					return finished
				}
			}
		}
	} else {
		for i := 1; i <= n; i++ {
			path := FindHamiltonianPath(n, graph, []int{i})
			if path != nil {
				return path
			}
		}
	}
	return nil
}

func main() {
	if len(os.Args) != 2 {
		fmt.Println("USAGE: parker [n]")
		return
	}
	n, err := strconv.Atoi(os.Args[1])
	if err != nil {
		fmt.Println("USAGE: parker[n]")
		return
	}
	if n <= 0 {
		fmt.Println("n must be greater than zero.")
		return
	}
	graph := PerfectSquareGraph(n)
	path := FindHamiltonianPath(n, graph, nil)
	fmt.Println(path)
}