# The Queen’s Gambit - Post 2

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 Knight’s Tour problem

The knight’s tour is a sequence of moves of a single knight such that it visits every square on the board once only.

This post contains:

• A recursive function for finding a solution given a starting move: move_knight()
• A solution to the knight’s tour that fits in a tweet

# Recursive solution in R for the Knight’s Tour Problem

The following code finds an 8x8 knight’s tour in less than a second.

library(purrr)
library(dplyr)

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Knight offsets i.e. the possible movements of a knight from the current location
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knight_offsets <- matrix(c(
1,    2,
2,    1,
-2,    1,
-1,    2,
2,   -1,
1,   -2,
-1,   -2,
-2,   -1
), ncol = 2, byrow = TRUE)

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#' Recurisvely calculate moves for a knight to complete a tour
#'
#' @param this_move proposed next move. 2 element numeric vector of (row, col)
#'        position at which to place the knight next
#' @param moves list of vectors. Each vector is length=2 and indicates the
#'        row/column locations of the knight's tour so far
#' @param visited 8x8 logical matrix which indicates whether or not a square has been
#'        visited by the knight already. When called by the user, this matrix
#'        must only contain FALSE
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
move_knight <- function(this_move, moves, visited) {

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Mark the move as visited
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
moves <- append(moves, list(this_move))
visited[this_move[1] + (this_move[2] - 1)*8] <- TRUE

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# termination if all visited
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
if (all(visited)) {
return(moves)
}

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Find all possible moves from this position
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
next_move <- cbind(knight_offsets[,1] + this_move[1], knight_offsets[,2] + this_move[2])

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# keep only moves that remain on the board
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
on_board  <- next_move[,1] %in% 1:8 & next_move[,2] %in% 1:8
next_move <- next_move[on_board,,drop=FALSE]

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Keep only moves that target a location that has not yet been visited
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
not_yet_visited <- !visited[next_move]
next_move <- next_move[not_yet_visited,, drop = FALSE]

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Recurse over every possible next move
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
for (i in seq_len(nrow(next_move))) {
res <- move_knight(next_move[i,, drop = FALSE], moves, visited)
if (!is.null(res)) {
return(res)
}
}

NULL
}

# Find a knight’s tour and plot it

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Find a tour from the given starting position
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
system.time({
moves <- move_knight(c(4, 8), moves = list(), visited = matrix(FALSE, 8, 8))
})
##    user  system elapsed
##   0.192   0.012   0.204
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#' Convert results to a data.frame for ggplot
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
moves_df <- as.data.frame(do.call(rbind, moves))
moves_df <- set_names(moves_df, c('x', 'y'))
moves_df\$idx <- 1:nrow(moves_df)

#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Plot the knight's tour
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ggplot(moves_df, aes(x, y)) +
geom_tile(aes(fill=as.logical((x+y)%%2)), colour = 'black') +
geom_path(alpha = 0.7, linetype = 1, size = 0.25) +
geom_text(aes(label = idx)) +
scale_fill_manual(values = c('grey70', 'white')) +
theme_void() +
theme(legend.position = 'none') +
coord_equal() +
labs(
title = "A knight's tour in #RStats"
)

# Tweet-length Knight’s Tour

The following tweet-able code generates a knight’s tour on an 8x8 chess board.

The list of values returned is a list of

#RStats
s=1:2;t=2:1;A=matrix;R=return
f=function(m,M,v){M=rbind(M,m)
v[m]=T
if(all(v))R(M)
N=cbind(c(s,-t,t,-s)+m[1],c(t,s,-s,-t)+m[2])
N=N[N[,1]%in%1:8&N[,2]%in%1:8,,drop=F]
N=N[!v[N],,drop=F]
for(i in row(N)[,1])if(length((r=f(N[i,,drop=F],M,v))))R(r)}
f(A(s*4,1),c(),A(F,8,8))

Running this code produces a set of 64 locations which are a knight’s tour of an 8x8 chess board.

Click to reveal/hide the solution matrix of knight locations
      [,1] [,2]
[1,]    4    8
[2,]    6    7
[3,]    8    8
[4,]    7    6
[5,]    5    7
[6,]    7    8
[7,]    8    6
[8,]    7    4
[9,]    5    5
[10,]    3    6
[11,]    1    7
[12,]    3    8
[13,]    4    6
[14,]    5    8
[15,]    7    7
[16,]    8    5
[17,]    6    6
[18,]    8    7
[19,]    6    8
[20,]    5    6
[21,]    3    7
[22,]    1    8
[23,]    2    6
[24,]    4    7
[25,]    2    8
[26,]    1    6
[27,]    3    5
[28,]    2    7
[29,]    1    5
[30,]    3    4
[31,]    5    3
[32,]    6    5
[33,]    8    4
[34,]    7    2
[35,]    6    4
[36,]    4    5
[37,]    3    3
[38,]    5    4
[39,]    7    5
[40,]    8    3
[41,]    7    1
[42,]    5    2
[43,]    4    4
[44,]    2    5
[45,]    1    3
[46,]    2    1
[47,]    4    2
[48,]    2    3
[49,]    1    1
[50,]    3    2
[51,]    2    4
[52,]    1    2
[53,]    3    1
[54,]    4    3
[55,]    5    1
[56,]    6    3
[57,]    8    2
[58,]    6    1
[59,]    7    3
[60,]    8    1
[61,]    6    2
[62,]    4    1
[63,]    2    2
[64,]    1    4