Solving 9-puzzle with GNU R

January 4, 2013

(This article was first published on R snippets, and kindly contributed to R-bloggers)

During holiday break I have decided to solve 9-puzzle, which is 3×3 variant of a well known 15-puzzle. The solution has proven to be a nice application of igraph package. Warning: this time the code takes a bit more tame than usual in my posts to execute.
9-puzzle is a problem where numbers from 1 to 8 are placed on a board that has size 3×3 tiles. One spot is left empty. We can slide numbers to empty tile. Starting from an arbitrary setup we want to put the numbers in order: 1, 2, 3 in the first row, 4, 5, 6 in the second row and 7,8 and empty in third row.

To solve it I represent each positioning of the numbers as vertex in the graph. Two vertexes are connected by an edge (undirected) if one of them can be reached from the other using only one move.

In order to encode the number setups I use 9 for empty space. Then each position can be encoded as permutation of numbers from 1 to 9. The encoding is row wise, so target setup has 123456789 encoding. Here is the code that writes to a file all edges in the graph:

moves <- list(c(2, 4), c(3, 5), 6, c(5, 7), c(6, 8), 9, 8, 9)
cat(“Initializing permutations\n\n”)
positions <- permutations(9, 9)
pos9 <- apply(positions, 1, function(x) { which(x == 9) } )
max.val <- length(which(pos9 != 9))
edge.write <- function(i) {
    percentage <- i / max.val
    setTxtProgressBar(, percentage)
    pos9i <- pos9[i]
    if (pos9i == 9) {
        stop(“Should not happen”)
    from <- positions[i,]
    to <- matrix(from, nrow = length(moves[[pos9i]]),
                 ncol = 9, byrow = T)
    for (j in 1:nrow(to)) {
        to[j, pos9i] <- to[j, moves[[pos9i]][j]]
        to[j, moves[[pos9i]][j]] <- 9
        cat(paste(from, collapse=“”), “,”,
            paste(to[j,],collapse=“”), “\n”, file = out.file)
} <- tempfile()
cat(“Writing edge file to: “,, “\n”,
    rep(“.”, 50), “\n”, sep=“”) <- txtProgressBar(0, 1, 0, width = 50)
out.file <- file(, “w”)
cat(“from, to\n”, file = out.file)
for (i in which(pos9 != 9)) {


Notice that the graph is undirected so we save only moves of empty tile “right” or “down”. This is encoded in moves variable. For example if position 2 is empty it can be moved to position 1, 3 or 5, but only 3 and 5 are encoded as move to 1 is “left”. In order to optimize the algorithm we remove all setups that have empty tile at position 9 as there are no moves “right” or “down” from such a setup.

Once the file is written it can be processed using igraph package as follows:

cat(“\nReading edge file to iGraph\n”)
edgelist <- read.csv(
puzzle9.graph <-, directed = TRUE)
cat(“Number of clusers in the graph:”,
    clusters(puzzle9.graph)$no, “\n\n”)
v.names <-get.vertex.attribute(puzzle9.graph,“name”)
v.start <- which(v.names==“123456789”)
sp <- shortest.paths(puzzle9.graph,v.start)
v.tough <- which(sp==max(sp[sp<Inf]))
formatted.tough <- character(2)
for (i in 1:length(v.tough)) {
    split.tough <- strsplit(v.names[v.tough[i]],split=“”)[[1]]
    split.tough[which(split.tough==“9”)] <- “.”
    split.tough <- matrix(split.tough, nrow = 3)
    formatted.tough[i] <- paste(apply(split.tough, 2, paste,
par(mar=c(4.5, 4.5, 0.5, 0.5))
plot(prop.table(table(sp, exclude=Inf)),
     xlab = “Steps needed”, ylab = “Probability”)
text(2, 0.12,“Tough cases:”, family = “mono”, pos = 4)
text(2, 0.1, formatted.tough[1], family = “mono”, pos = 4)
text(9, 0.1, formatted.tough[2], family = “mono”, pos = 4)


What we learn is that the graph has 2 clusters and only half of the possible setups can lead us to desired orderings (in fact we know that it is directly related to parity of the permutation). The code produces the graph given below. We see that most of the times 22-24 moves are needed to solve the puzzle if it is possible and in worst case 31 moves are needed. We find that there exactly 2 such tough cases and they are printed out on a graph:

To leave a comment for the author, please follow the link and comment on their blog: R snippets. offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...

If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.


Mango solutions

RStudio homepage

Zero Inflated Models and Generalized Linear Mixed Models with R

Dommino data lab

Quantide: statistical consulting and training



CRC R books series

Six Sigma Online Training

Contact us if you wish to help support R-bloggers, and place your banner here.

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)