8queens

Introduction to 8-Queens chess problem

• 8 queens on wikipedia

Tweet Sized 8queens + Plot

• Assumptions: library(tidyverse) has been called

#8queen #rstats
library(permute)
Q=allPerms(8,how(max=9E9))
p=combn(1:8,2,s=F)
f=function(q){all(map_lgl(p,~abs(q[.x[1]]-q[.x[2]])!=abs(.x[1]-.x[2])))}
s=data.frame(Q[apply(Q,1,f),])
s$x=1:nrow(s)
s=gather(s,r,c,-x)
s$r=sub('X','',s$r)
ggplot(s)+geom_tile(aes(r,c))+facet_wrap(~x)

Expanded code for 8 queens solutions in #rstats

#-----------------------------------------------------------------------------
# Generate all possibly layouts of queens on an 8x8 board
# such that there is one queen per row and column.
#
# An example row of Q is "2, 8, 7, 3, 5, 6, 1, 4"
#  - the number itself represents the column in which the Queen is placed
#  - the index of the number represents the row.
#  - i.e. the coordinates for the queens are:
#    (1, 2), (2, 8), (3, 7), (4, 3), (5, 5), (6, 6), (7, 1), (8, 4)
#
# The example row above represents the chess board:
#    
#    1 2 3 4 5 6 7 8
#    . Q . . . . . . 1 
#    . . . . . . . Q 2
#    . . . . . . Q . 3
#    . . Q . . . . . 4
#    . . . . Q . . . 5
#    . . . . . Q . . 6
#    Q . . . . . . . 7
#    . . . Q . . . . 8
#
# Note: This example can't be a solution to the 8 queens problem as the Queens
#       on rows 2 and 3 can see each other diagonally
#-----------------------------------------------------------------------------
Q <- permute::allPerms(8, how(maxperm=99999)) %>% as.data.frame() %>% as.tbl()


#-----------------------------------------------------------------------------
# For each possible solution, we need to look at each pair of queens and check
# if they can see each other diagonally.
# We don't need to check if they can see each other horizontally, as we only
# generate one queen per row.
# We don't need to check if they can see each other vertically, as we only
# place one queen per column.
#
# All the possible pairs of 8 queens to compare
#-----------------------------------------------------------------------------
pairs <- combn(1:8, 2, simplify = FALSE)


#-----------------------------------------------------------------------------
#' Check that every possible pair of queens cannot see each other along diagonal
#'
#' @param q a row of the Q data.frame
#' @return TRUE if this row is a solution to the 8queens problem 
#'         i.e. no 2 queens can see each other diagonally
#-----------------------------------------------------------------------------
f <- function(q) {
  all(purrr::map_lgl(pairs, ~abs(q[.x[1]] - q[.x[2]]) != abs(.x[1] - .x[2])))
}


#-----------------------------------------------------------------------------
# Filter the data.frame of all possible layouts of 8 queens, and keep just
# the ones which are actual solutions. Note: There are 92 solutions.
#-----------------------------------------------------------------------------
solutions <- Q[apply(Q, 1, f), ]


#-----------------------------------------------------------------------------
# Arrange the solution into tidy data for ggplot
#-----------------------------------------------------------------------------
solutions %<>% 
  mutate(game = row_number()) %>%
  tidyr::gather(row, col, -game) %>%
  mutate(row = readr::parse_number(row)) %>%
  arrange(game, row, col) %>%
  mutate(
    row = as.factor(row),
    col = as.factor(col)
  )


#-----------------------------------------------------------------------------
# Plot each chessboard as a facet
#-----------------------------------------------------------------------------
ggplot(solutions) + 
  geom_raster(aes(row, col)) + 
  facet_wrap(~game) + 
  theme_bw() +
  coord_equal() 

ggsave('8queens.png', width=10, height=10)