{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Copyright 2010-2017 Google\n",
    "# Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "# you may not use this file except in compliance with the License.\n",
    "# You may obtain a copy of the License at\n",
    "#\n",
    "#     http://www.apache.org/licenses/LICENSE-2.0\n",
    "#\n",
    "# Unless required by applicable law or agreed to in writing, software\n",
    "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "# See the License for the specific language governing permissions and\n",
    "# limitations under the License.\n",
    "\n",
    "\"\"\"OR-tools solution to the N-queens problem.\"\"\"\n",
    "from __future__ import print_function\n",
    "import time\n",
    "import sys\n",
    "from ortools.sat.python import cp_model\n",
    "\n",
    "class NQueenSolutionPrinter(cp_model.CpSolverSolutionCallback):\n",
    "  \"\"\"Print intermediate solutions.\"\"\"\n",
    "\n",
    "  def __init__(self, queens):\n",
    "    self.__queens = queens\n",
    "    self.__solution_count = 0\n",
    "    self.__start_time = time.time()\n",
    "\n",
    "  def SolutionCount(self):\n",
    "    return self.__solution_count\n",
    "\n",
    "  def NewSolution(self):\n",
    "    current_time = time.time()\n",
    "    print('Solution %i, time = %f s' %\n",
    "          (self.__solution_count, current_time - self.__start_time))\n",
    "    self.__solution_count += 1\n",
    "\n",
    "    all_queens = range(len(self.__queens))\n",
    "    for i in all_queens:\n",
    "      for j in all_queens:\n",
    "        if self.Value(self.__queens[j]) == i:\n",
    "          # There is a queen in column j, row i.\n",
    "          print('Q', end = ' ')\n",
    "        else:\n",
    "          print('_', end = ' ')\n",
    "      print()\n",
    "    print()\n",
    "\n",
    "\n",
    "def main(board_size):\n",
    "  # Creates the solver.\n",
    "  model = cp_model.CpModel()\n",
    "  # Creates the variables.\n",
    "  # The array index is the column, and the value is the row.\n",
    "  queens = [model.NewIntVar(0, board_size - 1, 'x%i' % i)\n",
    "            for i in range(board_size)]\n",
    "  # Creates the constraints.\n",
    "\n",
    "  # All rows must be different.\n",
    "  model.AddAllDifferent(queens)\n",
    "\n",
    "  # All columns must be different because the indices of queens are all\n",
    "  # different.\n",
    "\n",
    "  # No two queens can be on the same diagonal.\n",
    "  diag1 = []\n",
    "  diag2 = []\n",
    "  for i in range(board_size):\n",
    "    q1 = model.NewIntVar(0, 2 * board_size, 'diag1_%i' % i)\n",
    "    q2 = model.NewIntVar(-board_size, board_size, 'diag2_%i' % i)\n",
    "    diag1.append(q1)\n",
    "    diag2.append(q2)\n",
    "    model.Add(q1 == queens[i] + i)\n",
    "    model.Add(q2 == queens[i] - i)\n",
    "  model.AddAllDifferent(diag1)\n",
    "  model.AddAllDifferent(diag2)\n",
    "\n",
    "  ### Solve model.\n",
    "  solver = cp_model.CpSolver()\n",
    "  solution_printer = NQueenSolutionPrinter(queens)\n",
    "  status = solver.SearchForAllSolutions(model, solution_printer)\n",
    "\n",
    "  print()\n",
    "  print('Statistics')\n",
    "  print('  - conflicts       : %i' % solver.NumConflicts())\n",
    "  print('  - branches        : %i' % solver.NumBranches())\n",
    "  print('  - wall time       : %f ms' % solver.WallTime())\n",
    "  print('  - solutions found : %i' % solution_printer.SolutionCount())\n",
    "\n",
    "\n",
    "# By default, solve the 8x8 problem.\n",
    "board_size = 8\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "  if len(sys.argv) > 1:\n",
    "    board_size = int(sys.argv[1])\n",
    "  main(board_size)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}