# Placement of queens (3. 4. 06)

# Functions to solve the problems
f.queen.det <- function(n,draw=TRUE)
{
  ## Purpose: safe placement of n queens on a n x n chess board
  ## by a deterministic algorithm
  ## -------------------------------------------------------------------------
  ## Arguments: 
  ## -------------------------------------------------------------------------
  ## Author: Hans-Ruedi Kuensch, Date: 26 Oct 2001, 12:20
  m <- matrix(1,nrow=n,ncol=n) # matrix of allowed positions
  # 0 if a position is in conflict with placements in previous rows or
  # if we have already tried to place a queen at this position
  # Start by placing the first queen at (1,1)
  p <- c(1,rep(0,n-1)) # p[i]=column index where queen in row i is placed
  m[1,1] <- 0
  npos <- 1 # number of placements made so far
  j <- 1 #index of current row 
  while (j < n) {
    j <- j+1 #go to next row
    m[j,] <- 1 #all columns allowed in row i at the beginning.
    # Find the columns which are in conflict with previous rows 
    m[j,p[1:(j-1)]] <- 0 # conflicts along a column 
    ind <- p[1:(j-1)] + ((j-1):1)
    ind <- ind[ind <= n]
    m[j,ind] <- 0 #conflicts along one diagonal
    ind <- p[1:(j-1)] - ((j-1):1)
    ind <- ind[ind > 0]
    m[j,ind] <- 0 #conflicts along the other diagonals
    if (all(m[j,]==0)) { # conflicts everywhere in row j
      j <- j-1 # go back one row 
      while (all(m[j,]==0)) { # continue to go back if conflicts everywhere
        p[j] <- 0 # remove queens that have been placed in such rows
        j <- j-1
      }
    }
    p[j] <- min((1:n)[m[j,]==1]) # place a queen at the first possible place
    m[j,p[j]] <- 0 # take into account that this position has been tried
    npos <- npos + 1 #increase number of placements made so far.
  }
  if (draw) {
    plot(p[n:1]-0.5,(1:n)-0.5,xlim=c(0,n),ylim=c(0,n),xaxs="i",yaxs="i",
         xlab="",ylab="",pch=15) 
    for (j in (1:(n-1))){
      abline(v=j)
      abline(h=j)}
  }
  npos
}


f.queen.rand <- function(n,draw=TRUE,nstop=101)
{
  ## Purpose: safe placement of n queens on a n x n chess board
  ## by a randomized algorithm with restarting option
  ## -------------------------------------------------------------------------
  ## Arguments: nstop = threshold for restarting
  ## -------------------------------------------------------------------------
  ## Author: Hans-Ruedi Kuensch, Date: 26 Oct 2001, 12:20
  ##         modified April 3, 2006
  npos1 <- 0 # Total number of all placements
  weiter <- TRUE # do we need to continue ?
  while (weiter) {
    m <- matrix(1,nrow=n,ncol=n) # same meaning as in f.queen.det
    p <- rep(0,n-1) # same meaning as in f.queen.det
    p[1] <- ceiling(runif(1)*n) # random position in first row
    npos2 <- 1 # number of placements in this attempt
    m[1,p[1]] <- 0 # we have tried this position 
    j <- 1
    while ((j < n) & (npos2 < nstop)) { 
      j <- j+1 # go to next row 
      m[j,] <- 1
      m[j,p[1:(j-1)]] <- 0 # Find the forbidden positions in row j
      ind <- p[1:(j-1)] + ((j-1):1)
      ind <- ind[ind <= n]
      m[j,ind] <- 0
      ind <- p[1:(j-1)] - ((j-1):1)
      ind <- ind[ind > 0]
      m[j,ind] <- 0 
      if (all(m[j,]==0)) { # no placement possible in row j
        j <- j-1 #go back one row 
        while (all(m[j,]==0)) { # go further back if necessary
         p[j] <- 0 # remove the queens in row j
        j <- j-1
      }
      }
      ind <- (1:n)[m[j,]==1] # find all allowed columns in row j
      if (length(ind)==1) p[j] <- ind  # put a queen at one of these columns
      else p[j] <- sample(ind,1)
      m[j,p[j]] <- 0 # we have now tried this position
      npos2 <- npos2 + 1 # increase the number of placements in this attempt
    }
    npos1 <- npos1+npos2 # increase the total number of placements
    if (j==n) weiter <- FALSE # if placement was in row n we are done
  }
  if (draw) {
    plot(p[n:1]-0.5,(1:n)-0.5,xlim=c(0,n),ylim=c(0,n),xaxs="i",yaxs="i",
         xlab="",ylab="",pch=15) 
    for (j in (1:(n-1))){
      abline(v=j)
      abline(h=j)}
  }
  npos1
}

# try it out !  Interesting cases n=8,16,20; n=22,28,29,30 take very long 
f.queen.det(8)
f.queen.rand(8)
par(mfrow=c(2,2))
for (i in (5:8)) f.queen.det(i)

# compare the number of placements required
pos <- rep(0,26)
for (i in (5:30)) pos[i-4] <- f.queen.rand(i,draw=FALSE,nstop=101)
for (i in (5:30)) pos[i-4] <- f.queen.rand(i,draw=FALSE)
for (i in (5:20)) pos[i-4] <- f.queen.det(i,draw=FALSE)



# see the gains of restarting (vary the value nstop)
erg <- rep(0,100)
for (i in (1:100)) erg[i] <- f.queen.rand(25,draw=FALSE,nstop=10001)
sort(erg)
mean(erg)
sqrt(var(erg))