The Queens Problem and functional indexing

[sbmack]

This is a formulation of the Queens problem. n Queens must be placed on an n x n chessboard such that no Queens share the same row, column or diagonal. The Show and Tell feature is that the diagonal constraints illustrate how to create a Left Hand Side (LHS) variable index as a function of another variable index. This allows the creation of constraint sets with differing numbers of terms in each constraint. Note that the index derived from parameter values must be defined first.

In the model below the size parameter is the dimension of the board. The size is initialized to 8, but it can be increased to test solution times for larger boards. The fixed parameter is the index of a square that forces the square into the solution. It is randomly generated and used in a constraint in the formulation. The purpose is to generate alternative solutions by forcing a randomly assigned square into the solution.

The ggplot function plots the solution as a grid board for visual inspection. Running the entire code block repeatedly will generate alternative solutions.

Comments, suggestions appreciated.

SteveM

require(tidyverse)
require(ROI)
require(ROI.plugin.glpk)
require(ompr)
require(ompr.roi)
require(ggplot2)
require(conflicted)
conflict_prefer("filter", "dplyr")

size <- 8

fixed <-  replicate(2, sample(1:size, 1))

qmodel <- MIPModel() %>% 
  add_variable(mat[i, j], i = 1:size, j = 1:size, type = 'binary') %>%
  
  # Must constraints to ensure each row and column is covered
  add_constraint(sum_over(mat[i, j], i = 1:size) == 1, j = 1:size) %>% 
  add_constraint(sum_over(mat[i, j], j = 1:size) == 1, i = 1:size) %>% 
  
  # Diagonal constraints that illustrate inter-index relationships
  # note that j is defined first when it is a parameter of an i function
  add_constraint(sum_over(mat[i, j], i = d:size, j = (i - d + 1)) <= 1, d = 1:size) %>%
  add_constraint(sum_over(mat[i, j], j = d:size, i = (j - d + 1)) <= 1, d = 1:size) %>%
  add_constraint(sum_over(mat[i, j], i = d:size, j = (size + d - i)) <= 1, d = 1:size) %>% 
  add_constraint(sum_over(mat[i, j], j = 1:d, i = (d - j + 1)) <= 1, d = 1:size) %>% 

  # Random square fixed at 1 to generate alternative solutions
  add_constraint(mat[fixed] == 1)
  
result <- solve_model(qmodel, with_ROI(solver = "glpk"))
solution <- get_solution(result, mat[i, j])
solution$value <- as.integer(solution$value)

ggplot(solution, aes(x = i, y = j, fill = value)) +
  geom_tile(aes(fill = value), colour = "grey50") +
  labs(title = "Queens Problem", x = "Columns", y = "Rows") +
  theme(legend.position="none") +
  scale_fill_gradientn(colours = c("white", "red"), values = c(0, 1)) +
  coord_fixed() +
  scale_x_continuous(limits = c(0, size + 1), breaks = 1:size) +
  scale_y_continuous(limits = c(0, size + 1), breaks = 1:size)

fixed
filter(solution, value == 1)

# Run this code to write out the model structure for visual inspection
# This is helpful for validating your intent

wd <- getwd()
file_out <- paste(wd, "test.txt", sep = "/")
ROI_write(as_ROI_model(qmodel), file_out, "lp_cplex")