# The Queen’s Gambit - Post 1

Inspired by The Queen’s Gambit on Netflix, I’m doing a few posts on Chess in R.

This screenshot from the show explains everything:

# Introduction to the 8 queens puzzle

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other.

This post contains:

• A recursive function for finding all solutions: place_queen()
• A manually minified version that fits in a tweet - this code also generates a plot of all solutions.

# Recursive solution in R

library(tidyverse)

#-----------------------------------------------------------------------------
#' Try and place a Queen given a vector of positions of the current Queens
#'
#' This function calls itself recursively for every valid placement of the
#' next queen.
#'
#' @param queens A vector of integers representing the column placement
#'               of queens so far. The index within this list
#'               is the row, and the value is the column.
#'               To generate all solutions, pass in an empty vector (the default)
#'
#'  e.g. queens = c(1, 4, 7) corresponds to queens placed at c(1, 1), c(2, 4) and
#'  c(3, 7)
#'
#'
#'  ---------------------------------
#'  |   |   |   |   |   |   |   |   |
#'  ---------------------------------
#'  |   |   |   |   |   |   |   |   |
#'  ---------------------------------
#'  |   |   |   |   |   |   |   |   |
#'  ---------------------------------
#'  |   |   |   |   |   |   |   |   |
#'  ---------------------------------
#'  |   |   |   |   |   |   | Q |   |    3rd row, 7th column
#'  ---------------------------------
#'  |   |   |   | Q |   |   |   |   |    2nd row, 4th column
#'  ---------------------------------
#'  | Q |   |   |   |   |   |   |   |    1st row, 1st column
#'  ---------------------------------
#'
#'
#'
#'
#' @return a list where each element is a vector of 8 integers
#'         i.e. a solution to the 8 queens problem
#-----------------------------------------------------------------------------
place_queen <- function(queens=c()) {

#---------------------------------------------------------------------------
# If there are 8 queens placed, then this must be a solution.
#---------------------------------------------------------------------------
if (length(queens) == 8) {
return(list(queens))
}

#---------------------------------------------------------------------------
# Figure out where a queen can be placed 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.int(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
#---------------------------------------------------------------------------
possible_placements %>%
map(~place_queen(c(queens, .x))) %>%
keep(~length(.x) > 0) %>%
flatten()
}

#-----------------------------------------------------------------------------
#' Plot a single solution
#' @param queens a vector of 8 integers giving the column positions of 8 queens
#-----------------------------------------------------------------------------
plot_single_8queens <- function(queens, title = NULL) {
queens_df <- tibble(cols = queens, rows=1:8)
board_df <- expand.grid(cols = 1:8, rows = 1:8) %>%
mutate(check = (cols + rows) %%2 == 1)

p <- ggplot(queens_df, aes(rows, cols)) +
geom_tile(data=board_df, aes(fill=check), colour='black') +
geom_text(label='\u2655', family="Arial Unicode MS", size = 8) +
theme_void() +
coord_equal() +
scale_fill_manual(values = c('TRUE'='white', 'FALSE'='grey70')) +
theme(
legend.position = 'none'
)

if (is.null(title)) {
p <- p + labs(title = paste("Queens:", deparse(as.numeric(queens))))
} else {
p <- p + labs(title = title)
}
}

#-----------------------------------------------------------------------------
#-----------------------------------------------------------------------------
solutions <- place_queen()
Table 1: First 10 solutions. Each row of this table is a solution i.e. a vector of 8 numbers where the values are the row position on the chessboard. The table column indicates which column on the chess board.
V1 V2 V3 V4 V5 V6 V7 V8
1 5 8 6 3 7 2 4
1 6 8 3 7 4 2 5
1 7 4 6 8 2 5 3
1 7 5 8 2 4 6 3
2 4 6 8 3 1 7 5
2 5 7 1 3 8 6 4
2 5 7 4 1 8 6 3
2 6 1 7 4 8 3 5
2 6 8 3 1 4 7 5
2 7 3 6 8 5 1 4
#-----------------------------------------------------------------------------
#  Plot the first 2 solutions
#-----------------------------------------------------------------------------
plot_single_8queens(solutions[[1]])
plot_single_8queens(solutions[[2]])

## 8Queens solution in Rstats Compacted into a tweet

This tweet calculates all 92 solutions and plots them on a checkered board - the bright blue squares on the board represent the locations of the queens.

This solution fits in a tweet!

library(tidyverse)
v=1:8
f=function(q){L=length(q)
if(L==8){q}else{flatten(map(setdiff(v,c(q,q+L:1,q-L:1)),~f(c(q,.))))}}
s=data.frame(c=unlist(f(c())),r=v,x=rep(1:92,e=8),z=3)
b=mutate(crossing(c=v,r=v),z=(c+r)%%2)
g=geom_tile
ggplot(s,aes(r,c,fill=z))+g(d=b)+g()+facet_wrap(~x)

## Extension

Nothing else I want to do :)