% \VignetteIndexEntry{Solving the N-Queens Problem with Local Search}
% \VignetteKeyword{Local Search}
% \VignetteKeyword{Simulated Annealing}
% \VignetteKeyword{Threshold Accepting}
% \VignetteKeyword{heuristics}
% \VignetteKeyword{optimize}
\documentclass[a4paper]{article}
\usepackage[left=2.5cm,top=2cm, bottom=3cm, right=3.5cm]{geometry}
\usepackage[noae]{Sweave}
\usepackage{mathptmx}
\usepackage{amsmath,amstext}
\usepackage{ragged2e}
\usepackage{hyperref}
\usepackage{natbib}
\usepackage{units}
\usepackage{color}
\definecolor{grau2}{rgb}{.2,.2,.2}
\definecolor{grau7}{rgb}{.7,.7,.7}
% define *Sweave* layout
\DefineVerbatimEnvironment{Sinput}{Verbatim}{}
\DefineVerbatimEnvironment{Soutput}{Verbatim}{frame=single,xleftmargin=0em,%
  formatcom=\color{grau2},rulecolor=\color{grau7}}
\DefineVerbatimEnvironment{Scode}{Verbatim}{xleftmargin=2em}
\fvset{listparameters={\setlength{\topsep}{0pt}}}
\renewenvironment{Schunk}{\vspace{\topsep}}{\vspace{\topsep}}
<<echo=false>>=
options(continue = "  ", digits = 5, max.print = 1000)
pv <- packageVersion("NMOF")
pv <- gsub("(.*)[.](.*)", "\\1-\\2", pv)
@

\begin{document}
{\raggedright{\LARGE Solving the \emph{N}-Queens Problem with Local Search}}\hspace*{\fill}
{\footnotesize Package version \Sexpr{pv}}\medskip

\noindent Enrico Schumann\\
\noindent \texttt{es@enricoschumann.net}\\
\bigskip


\noindent This vignette provides example code for a
combinatorial problem: the \emph{N-Queens Problem}.%
\marginpar{\footnotesize\RaggedRight The example is inspired
  by \citet[chapter 2]{ierusalimschy2016}.} %

\nocite{Gilli2019}


\section{The problem}

The goal is to place $N$~queens on a chess-board of
size $N \times N$ in such a way that no queen is
attacked.  A queen may move vertically, horizontally
and on a diagonal. So whenever there is more than one
queen on any row, column or diagonal, the position is
invalid. To solve the problem with a Local Search (LS),
we need three components:
\begin{enumerate}
\item a way to represent a solution (i.e. a position on
  the chessboard);
\item a way to evaluate such a solution;
\item and, since we use a LS, a method to modify a
  solution.
\end{enumerate}

\noindent We start by attaching the package and fixing
a seed.
<<>>=
library("NMOF")
set.seed(134577)
@

\section{Representing a solution}

Since on any row there cannot be more than one queen, we may store a
position as a vector of columns on which the queens are placed. (In
chess, rows would be called ranks and columns would be files, but we
prefer matrix terminology.) Thus, a candidate solution \texttt{p} (p
for position) could look as follows:
<<>>=
N <- 8              ## board size
p <- sample.int(N)  ## a random solution
data.frame(row = 1:N, column = p)
@

\noindent Or (a very bad solution):
<<>>=
p <- rep(1, N)
data.frame(row = 1:N, column = p)
@


\noindent We will also want to visualise a position, for which
we write the function \texttt{print\_board}.
<<>>=
print_board <- function(p, q.char = "Q", sep = " ") {
    n <- length(p)
    row <- rep("-", n)
    for (i in seq_len(n)) {
        row_i <- row
        row_i[p[i]] <- q.char

        cat(paste(row_i, collapse = sep))
        cat("\n")
    }
}

print_board(p)
@

\section{Evaluating a solution}

We need to compute on what row, column, diagonal (top
left to bottom right) or reverse diagonal (top right to
bottom left) a queen stands. Rows and columns are
simple; we label the diagonals as follows.

<<>>=
mat <- array(NA, dim = c(N,N))  ## diagonals
for (r in 1:N)
    for (c in 1:N)
        mat[r,c] <- c - r
mat

mat <- array(NA, dim = c(N,N))  ## reverse diagonals
for (r in 1:N)
    for (c in 1:N)
        mat[r,c] <- c + r - (N + 1)
mat
@

\noindent Note that for reverse diagonals, the \texttt{N + 1}
would not be necessary; it serves only to shift the
diagonal labels so that the main diagonal is zero.

Thus for a given solution \texttt{p}, we know the row,
column, diagonal and reverse diagonal for each queen.
We define the quality of a solution by the number of
attacks that happen: for a valid solution, that number
should be zero.

<<>>=
n_attacks <- function(p) {
    ## more than one Q on a column?
    sum(duplicated(p)) +

    ## more than one Q on a diagonal?
    sum(duplicated(p - seq_along(p))) +

    ## more than one Q on a reverse diagonal?
    sum(duplicated(p + seq_along(p)))
}

n_attacks(p)
@


\section{Changing a solution}

A given position may be modified by picking one row
randomly and then moving the queen there to the left or
right. We allow for moves up to \texttt{step}
squares, which we set to \texttt{3} in the example.

<<>>=
neighbour <- function(p) {
    step <- 3
    i <- sample.int(N, 1)
    p[i] <- p[i] + sample(c(1:step, -(1:step)), 1)

    if (p[i] > N)
        p[i] <- 1
    else if (p[i] < 1)
        p[i] <- N
    p
}
@

<<>>=
print_board(p)
print_board(p <- neighbour(p))
print_board(p <- neighbour(p))
@

\section{Solving the model}

We use three different LS methods: a `classical'
Stochastic Local Search (\texttt{LSopt}),
Threshold Accepting (\texttt{TAopt}) and
Simulated Annealing (\texttt{SAopt}).

<<>>=
p0 <- rep(1, N)  ## or a random initial solution: p0 <- sample.int(N)
print_board(p0)

sol <- LSopt(n_attacks, list(x0 = p0,
                             neighbour = neighbour,
                             printBar = FALSE,
                             nS = 10000))
print_board(sol$xbest)

sol <- TAopt(n_attacks, list(x0 = p0,
                             neighbour = neighbour,
                             printBar = FALSE,
                             nS = 1000))
print_board(sol$xbest)

sol <- SAopt(n_attacks, list(x0 = p0,
                             neighbour = neighbour,
                             printBar = FALSE,
                             nS = 1000))
print_board(sol$xbest)
@


\bibliographystyle{plainnat}
\bibliography{NMOF}
\end{document}