8 Queens

Recursive #rstats solution to 8 queens in a Tweet

#rstats #8queens #222characters #codegolf #tidyverse
library(tidyverse)
f=function(q){L=length(q)
if(L==8){return(q)}
flatten(map(setdiff(1:8,c(q,c(q+L:1,q-L:1))),~f(c(q,.x))))}
s=data.frame(c=unlist(f(c())),r=1:8,x=rep(1:92,e=8))
ggplot(s)+geom_tile(aes(r,c))+facet_wrap(~x)

Breakdown of Recursive solution

#-----------------------------------------------------------------------------
#' Try and place a queen given the queens we have on the board so far
#'
#' @param queens column placement of queens so far. The index within this list
#'               is the row, and the value is the column.
#' 
#-----------------------------------------------------------------------------
place_queen <- function(queens) {
  # If there are 8 queens placed, then this must be a solution.
  if (length(queens) == 8) {
    cat("Solution: ", paste(queens, collapse=", "), "\n")
    return()
  }
  
  # Need to figure out where I can place a queen in the next row.
  # Drop all columns that have already been taken - since we 
  # can't place a queen below an existing queen
  possible_placements <- setdiff(1:8, queens)
  
  # For each queen already on the board, find the diagonal 
  # positions that it can see in this row.
  diag_offsets <- seq(length(queens), 1)
  diags <- c(queens + diag_offsets, queens - diag_offsets)
  diags <- diags[diags > 0 & diags < 9]
  
  # Drop these diagonal columns from possible placements
  possible_placements <- setdiff(possible_placements, diags)
  
  # For each possible placement, try and place a queen
  walk(possible_placements, ~place_queen(c(queens, .x)))
}

# Start with no queens placed
place_queen(c())

## Solution:  1, 5, 8, 6, 3, 7, 2, 4 
## Solution:  1, 6, 8, 3, 7, 4, 2, 5 
## Solution:  1, 7, 4, 6, 8, 2, 5, 3 
## Solution:  1, 7, 5, 8, 2, 4, 6, 3 
## Solution:  2, 4, 6, 8, 3, 1, 7, 5 
## Solution:  2, 5, 7, 1, 3, 8, 6, 4 
## Solution:  2, 5, 7, 4, 1, 8, 6, 3 
## Solution:  2, 6, 1, 7, 4, 8, 3, 5 
## Solution:  2, 6, 8, 3, 1, 4, 7, 5 
## Solution:  2, 7, 3, 6, 8, 5, 1, 4 
## Solution:  2, 7, 5, 8, 1, 4, 6, 3 
## Solution:  2, 8, 6, 1, 3, 5, 7, 4 
## Solution:  3, 1, 7, 5, 8, 2, 4, 6 
## Solution:  3, 5, 2, 8, 1, 7, 4, 6 
## Solution:  3, 5, 2, 8, 6, 4, 7, 1 
## Solution:  3, 5, 7, 1, 4, 2, 8, 6 
## Solution:  3, 5, 8, 4, 1, 7, 2, 6 
## Solution:  3, 6, 2, 5, 8, 1, 7, 4 
## Solution:  3, 6, 2, 7, 1, 4, 8, 5 
## Solution:  3, 6, 2, 7, 5, 1, 8, 4 
## Solution:  3, 6, 4, 1, 8, 5, 7, 2 
## Solution:  3, 6, 4, 2, 8, 5, 7, 1 
## Solution:  3, 6, 8, 1, 4, 7, 5, 2 
## Solution:  3, 6, 8, 1, 5, 7, 2, 4 
## Solution:  3, 6, 8, 2, 4, 1, 7, 5 
## Solution:  3, 7, 2, 8, 5, 1, 4, 6 
## Solution:  3, 7, 2, 8, 6, 4, 1, 5 
## Solution:  3, 8, 4, 7, 1, 6, 2, 5 
## Solution:  4, 1, 5, 8, 2, 7, 3, 6 
## Solution:  4, 1, 5, 8, 6, 3, 7, 2 
## Solution:  4, 2, 5, 8, 6, 1, 3, 7 
## Solution:  4, 2, 7, 3, 6, 8, 1, 5 
## Solution:  4, 2, 7, 3, 6, 8, 5, 1 
## Solution:  4, 2, 7, 5, 1, 8, 6, 3 
## Solution:  4, 2, 8, 5, 7, 1, 3, 6 
## Solution:  4, 2, 8, 6, 1, 3, 5, 7 
## Solution:  4, 6, 1, 5, 2, 8, 3, 7 
## Solution:  4, 6, 8, 2, 7, 1, 3, 5 
## Solution:  4, 6, 8, 3, 1, 7, 5, 2 
## Solution:  4, 7, 1, 8, 5, 2, 6, 3 
## Solution:  4, 7, 3, 8, 2, 5, 1, 6 
## Solution:  4, 7, 5, 2, 6, 1, 3, 8 
## Solution:  4, 7, 5, 3, 1, 6, 8, 2 
## Solution:  4, 8, 1, 3, 6, 2, 7, 5 
## Solution:  4, 8, 1, 5, 7, 2, 6, 3 
## Solution:  4, 8, 5, 3, 1, 7, 2, 6 
## Solution:  5, 1, 4, 6, 8, 2, 7, 3 
## Solution:  5, 1, 8, 4, 2, 7, 3, 6 
## Solution:  5, 1, 8, 6, 3, 7, 2, 4 
## Solution:  5, 2, 4, 6, 8, 3, 1, 7 
## Solution:  5, 2, 4, 7, 3, 8, 6, 1 
## Solution:  5, 2, 6, 1, 7, 4, 8, 3 
## Solution:  5, 2, 8, 1, 4, 7, 3, 6 
## Solution:  5, 3, 1, 6, 8, 2, 4, 7 
## Solution:  5, 3, 1, 7, 2, 8, 6, 4 
## Solution:  5, 3, 8, 4, 7, 1, 6, 2 
## Solution:  5, 7, 1, 3, 8, 6, 4, 2 
## Solution:  5, 7, 1, 4, 2, 8, 6, 3 
## Solution:  5, 7, 2, 4, 8, 1, 3, 6 
## Solution:  5, 7, 2, 6, 3, 1, 4, 8 
## Solution:  5, 7, 2, 6, 3, 1, 8, 4 
## Solution:  5, 7, 4, 1, 3, 8, 6, 2 
## Solution:  5, 8, 4, 1, 3, 6, 2, 7 
## Solution:  5, 8, 4, 1, 7, 2, 6, 3 
## Solution:  6, 1, 5, 2, 8, 3, 7, 4 
## Solution:  6, 2, 7, 1, 3, 5, 8, 4 
## Solution:  6, 2, 7, 1, 4, 8, 5, 3 
## Solution:  6, 3, 1, 7, 5, 8, 2, 4 
## Solution:  6, 3, 1, 8, 4, 2, 7, 5 
## Solution:  6, 3, 1, 8, 5, 2, 4, 7 
## Solution:  6, 3, 5, 7, 1, 4, 2, 8 
## Solution:  6, 3, 5, 8, 1, 4, 2, 7 
## Solution:  6, 3, 7, 2, 4, 8, 1, 5 
## Solution:  6, 3, 7, 2, 8, 5, 1, 4 
## Solution:  6, 3, 7, 4, 1, 8, 2, 5 
## Solution:  6, 4, 1, 5, 8, 2, 7, 3 
## Solution:  6, 4, 2, 8, 5, 7, 1, 3 
## Solution:  6, 4, 7, 1, 3, 5, 2, 8 
## Solution:  6, 4, 7, 1, 8, 2, 5, 3 
## Solution:  6, 8, 2, 4, 1, 7, 5, 3 
## Solution:  7, 1, 3, 8, 6, 4, 2, 5 
## Solution:  7, 2, 4, 1, 8, 5, 3, 6 
## Solution:  7, 2, 6, 3, 1, 4, 8, 5 
## Solution:  7, 3, 1, 6, 8, 5, 2, 4 
## Solution:  7, 3, 8, 2, 5, 1, 6, 4 
## Solution:  7, 4, 2, 5, 8, 1, 3, 6 
## Solution:  7, 4, 2, 8, 6, 1, 3, 5 
## Solution:  7, 5, 3, 1, 6, 8, 2, 4 
## Solution:  8, 2, 4, 1, 7, 5, 3, 6 
## Solution:  8, 2, 5, 3, 1, 7, 4, 6 
## Solution:  8, 3, 1, 6, 2, 5, 7, 4 
## Solution:  8, 4, 1, 3, 6, 2, 7, 5