{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "title: N-Queens\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Originally Contributed by**: Matthew Helm ([with help from @mtanneau on Julia Discourse](https://discourse.julialang.org/t/which-jump-jl-solver-for-this-problem/43350/17?u=mthelm85))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The N-Queens problem involves placing N queens on an N x N chessboard such that none of the queens attacks another. In chess, a \n",
    "queen can move vertically, horizontally, and diagonally so there cannot be more than one queen on any given row, column, or \n",
    "diagonal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/n_queens4.png\" style=\"width: auto; height: auto\" alt=\"4 Queens\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Note that none of the queens above are able to attack any other as a result of their careful placement.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "using GLPK\n",
    "using JuMP\n",
    "using LinearAlgebra\n",
    "\n",
    "# N-Queens\n",
    "N = 8\n",
    "\n",
    "model = Model(GLPK.Optimizer);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, let's create an N x N chessboard of binary values. 0 will represent an empty space on the board and 1 will represent a \n",
    "space occupied by one of our queens:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8×8 Array{VariableRef,2}:\n",
       " x[1,1]  x[1,2]  x[1,3]  x[1,4]  x[1,5]  x[1,6]  x[1,7]  x[1,8]\n",
       " x[2,1]  x[2,2]  x[2,3]  x[2,4]  x[2,5]  x[2,6]  x[2,7]  x[2,8]\n",
       " x[3,1]  x[3,2]  x[3,3]  x[3,4]  x[3,5]  x[3,6]  x[3,7]  x[3,8]\n",
       " x[4,1]  x[4,2]  x[4,3]  x[4,4]  x[4,5]  x[4,6]  x[4,7]  x[4,8]\n",
       " x[5,1]  x[5,2]  x[5,3]  x[5,4]  x[5,5]  x[5,6]  x[5,7]  x[5,8]\n",
       " x[6,1]  x[6,2]  x[6,3]  x[6,4]  x[6,5]  x[6,6]  x[6,7]  x[6,8]\n",
       " x[7,1]  x[7,2]  x[7,3]  x[7,4]  x[7,5]  x[7,6]  x[7,7]  x[7,8]\n",
       " x[8,1]  x[8,2]  x[8,3]  x[8,4]  x[8,5]  x[8,6]  x[8,7]  x[8,8]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@variable(model, x[i=1:N, j=1:N], Bin)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can add our constraints:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# There must be exactly one queen in a given row/column\n",
    "for i=1:N\n",
    "    @constraint(model, sum(x[i, :]) == 1)\n",
    "    @constraint(model, sum(x[:, i]) == 1)\n",
    "end\n",
    "\n",
    "# There can only be one queen on any given diagonal\n",
    "for i in -(N-1):(N-1)\n",
    "    @constraint(model, sum(diag(x,i)) <= 1)\n",
    "    @constraint(model, sum(diag(reverse(x,dims=1), i)) <=1)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's it! We are ready to put our model to work and see if it is able to find a feasible solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "optimize!(model)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now review the solution that our model found:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8×8 Array{Int64,2}:\n",
       " 0  0  0  0  0  1  0  0\n",
       " 0  0  0  0  0  0  0  1\n",
       " 0  1  0  0  0  0  0  0\n",
       " 0  0  0  1  0  0  0  0\n",
       " 1  0  0  0  0  0  0  0\n",
       " 0  0  0  0  0  0  1  0\n",
       " 0  0  0  0  1  0  0  0\n",
       " 0  0  1  0  0  0  0  0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution = convert.(Int,value.(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/n_queens.png\" style=\"width: auto; height: auto\" alt=\"4 Queens\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.5.1",
   "language": "julia",
   "name": "julia-1.5"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}