Puzzle: A path through pairs making squares

[This article was first published on Revolutions, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Ted Harding posed an interesting puzzle challenge on the r-help mailing list recently. Here's the puzzle:

Take the numbers 1, 2, 3, etc. up to 17.

Can you write out all seventeen numbers in a line so that every pair of numbers that are next to each other, adds up to give a square number?

You can figure out the solution from first principles fairly easily (hint: what neighbours must 17 have?), but Ted's challenge was to write a "neat" R function to solve this puzzle programmatically. The r-help thread generated several solutions (including an elegant one based on recursion, and a generalization to larger sets of numbers), but I wanted to highlight this solution from Vincent Zoonekynd on StackOverflow:

# Allowable pairs form a graph
p <- outer(
  1:17, 1:17, 
  function(u,v) round(sqrt(u + v),6) == floor(sqrt(u+v)) ) 
)
rownames(p) <- colnames(p) <- 1:17
image(p, col=c(0,1)) 
 
# Read the solution on the plot
library(igraph)
g <- graph.adjacency(p, "undirected")
V(g)$label <- V(g)$name 
plot(g, layout=layout.fruchterman.reingold)

It's a clever use of the graph theory. Consider the numbers 1-17 as vertices in a graph, with connections between pairs defined by whether they sum to a square. The call to outer defines the T/F adjacency matrix (which the code displays as an image), and then the plot.igraph function displays the graph as an R chart:

AdjacencyAll you need to do is to trace a path that passes through each number once, and you have your solution to the puzzle. A neat and unexpected use of the igraph package for handling graphs in R.

StackOverflow: Ordering 1:17 by perfect square pairs

To leave a comment for the author, please follow the link and comment on their blog: Revolutions.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)