Ahmad Fattahi


Blog Post created by Ahmad Fattahi Employee on May 10, 2012

As geeks we all love puzzles! How about attacking a cool one using R and solving it in an elegant way? (Even if you don't know R you will probably enjoy it! I found the problem and solution here; I just tweaked it a little bit.) The syntax and code efficiency is really impressive. Here is the description:


We are given integers between 1 and n. We would like to order them in a line, when possible, so that every adjacent pair adds up to a square number. For example, for n=15 a solution would be:


9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8


There are multiple ways to model the solution; an elegant way is to model this as a graph. Each number corresponds to a vertex. If two integers add up to a square number there will be an edge between the corresponding vertices. We have a solution if there is a Hamiltonian path in the graph (a path that traverses all the vertices once and only once).


Now let's implement this in R. The comments in the code should explain each line.

#We consider numbers between 1 and n
n <- 15

#Creating the graph adjacency matrix and giving rows and columns names
d <- outer(1:n, 1:n, function(u,v) (round(sqrt(u+v), digits=6)==sqrt(u+v)))
rownames(d) <- colnames(d) <- 1:n

#Defining the graph object based on the adjacency matrix
g <- graph.adjacency(d, "undirected")

#Labeling each vertex with the actual integer it represents in the graph
V(g)$label <- V(g)$name

#Plotting the graph with a readable layout
plot(g, layout=layout.fruchterman.reingold)

 And here is the result for n=15, n=10 (no solution), and n=20 (no solution).