AIND-Constraint_Satisfaction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Constraint Satisfaction Problems Lab\n",
    "\n",
    "## Introduction\n",
    "Constraint Satisfaction is a technique for solving problems by expressing limits on the values of each variable in the solution with mathematical constraints.  We've used constraints before -- constraints in the Sudoku project are enforced implicitly by filtering the legal values for each box, and the planning project represents constraints as arcs connecting nodes in the planning graph -- but in this lab exercise we will use a symbolic math library to explicitly construct binary constraints and then use Backtracking to solve the N-queens problem (which is a generalization [8-queens problem](https://en.wikipedia.org/wiki/Eight_queens_puzzle)).  Using symbolic constraints should make it easier to visualize and reason about the constraints (especially for debugging), but comes with a performance penalty.\n",
    "\n",
    "![8-queens puzzle solution](EightQueens.gif)\n",
    "\n",
    "Briefly, the 8-queens problem asks you to place 8 queens on a standard 8x8 chessboard such that none of the queens are in \"check\" (i.e., no two queens occupy the same row, column, or diagonal). The N-queens problem generalizes the puzzle to to any size square board.\n",
    "\n",
    "## I. Lab Overview\n",
    "Students should read through the code and the wikipedia page (or other resources) to understand the N-queens problem, then:\n",
    "\n",
    "0. Complete the warmup exercises in the [Sympy_Intro notebook](Sympy_Intro.ipynb) to become familiar with they sympy library and symbolic representation for constraints\n",
    "0. Implement the [NQueensCSP class](#II.-Representing-the-N-Queens-Problem) to develop an efficient encoding of the N-queens problem and explicitly generate the constraints bounding the solution\n",
    "0. Write the [search functions](#III.-Backtracking-Search) for recursive backtracking, and use them to solve the N-queens problem\n",
    "0. (Optional) Conduct [additional experiments](#IV.-Experiments-%28Optional%29) with CSPs and various modifications to the search order (minimum remaining values, least constraining value, etc.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import matplotlib as mpl\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from util import constraint, displayBoard\n",
    "from sympy import *\n",
    "from IPython.display import display\n",
    "init_printing()\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## II. Representing the N-Queens Problem\n",
    "There are many acceptable ways to represent the N-queens problem, but one convenient way is to recognize that one of the constraints (either the row or column constraint) can be enforced implicitly by the encoding.  If we represent a solution as an array with N elements, then each position in the array can represent a column of the board, and the value at each position can represent which row the queen is placed on.\n",
    "\n",
    "In this encoding, we only need a constraint to make sure that no two queens occupy the same row, and one to make sure that no two queens occupy the same diagonal.\n",
    "\n",
    "### Define Symbolic Expressions for the Problem Constraints\n",
    "Before implementing the board class, we need to construct the symbolic constraints that will be used in the CSP.  Declare any symbolic terms required, and then declare two generic constraint generators:\n",
    "- `diffRow` - generate constraints that return True if the two arguments do not match\n",
    "- `diffDiag` - generate constraints that return True if two arguments are not on the same diagonal (Hint: you can easily test whether queens in two columns are on the same diagonal by testing if the difference in the number of rows and the number of columns match)\n",
    "\n",
    "Both generators should produce binary constraints (i.e., each should have two free symbols) once they're bound to specific variables in the CSP.  For example, Eq((a + b), (b + c)) is not a binary constraint, but Eq((a + b), (b + c)).subs(b, 1) _is_ a binary constraint because one of the terms has been bound to a constant, so there are only two free variables remaining. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Declare any required symbolic variables\n",
    "raise NotImplementedError(\"TODO: declare symbolic variables for the constraint generators\")\n",
    "\n",
    "# Define diffRow and diffDiag constraints\n",
    "raise NotImplementedError(\"TODO: create the diffRow and diffDiag constraint generators\")\n",
    "diffRow = constraint(...)\n",
    "diffRow = constraint(...)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Test diffRow and diffDiag\n",
    "_x = symbols(\"x:3\")\n",
    "\n",
    "# generate a diffRow instance for testing\n",
    "raise NotImplementedError(\"TODO: use your diffRow constraint to generate a diffRow constraint for _x[0] and _x[1]\")\n",
    "diffRow_test = None\n",
    "\n",
    "assert(len(diffRow_test.free_symbols) == 2)\n",
    "assert(diffRow_test.subs({_x[0]: 0, _x[1]: 1}) == True)\n",
    "assert(diffRow_test.subs({_x[0]: 0, _x[1]: 0}) == False)\n",
    "assert(diffRow_test.subs({_x[0]: 0}) != False)  # partial assignment is not false\n",
    "print(\"Passed all diffRow tests.\")\n",
    "\n",
    "# generate a diffDiag instance for testing\n",
    "raise NotImplementedError(\"TODO: use your diffDiag constraint to generate a diffDiag constraint for _x[0] and _x[2]\")\n",
    "diffDiag_test = None\n",
    "\n",
    "assert(len(diffDiag_test.free_symbols) == 2)\n",
    "assert(diffDiag_test.subs({_x[0]: 0, _x[2]: 2}) == False)\n",
    "assert(diffDiag_test.subs({_x[0]: 0, _x[2]: 0}) == True)\n",
    "assert(diffDiag_test.subs({_x[0]: 0}) != False)  # partial assignment is not false\n",
    "print(\"Passed all diffDiag tests.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The N-Queens CSP Class\n",
    "Implement the CSP class as described above, with constraints to make sure each queen is on a different row and different diagonal than every other queen, and a variable for each column defining the row that containing a queen in that column."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class NQueensCSP:\n",
    "    \"\"\"CSP representation of the N-queens problem\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    N : Integer\n",
    "        The side length of a square chess board to use for the problem, and\n",
    "        the number of queens that must be placed on the board\n",
    "    \"\"\"\n",
    "    def __init__(self, N):\n",
    "        raise NotImplementedError(\"TODO: declare symbolic variables in self._vars in the CSP constructor\")\n",
    "        _vars = None\n",
    "        _domain = set(range(N))\n",
    "        self.size = N\n",
    "        self.variables = _vars\n",
    "        self.domains = {v: _domain for v in _vars}\n",
    "        self._constraints = {x: set() for x in _vars}\n",
    "\n",
    "        # add constraints - for each pair of variables xi and xj, create\n",
    "        # a diffRow(xi, xj) and a diffDiag(xi, xj) instance, and add them\n",
    "        # to the self._constraints dictionary keyed to both xi and xj;\n",
    "        # (i.e., add them to both self._constraints[xi] and self._constraints[xj])\n",
    "        raise NotImplementedError(\"TODO: add constraints in self._constraints in the CSP constructor\")\n",
    "    \n",
    "    @property\n",
    "    def constraints(self):\n",
    "        \"\"\"Read-only list of constraints -- cannot be used for evaluation \"\"\"\n",
    "        constraints = set()\n",
    "        for _cons in self._constraints.values():\n",
    "            constraints |= _cons\n",
    "        return list(constraints)\n",
    "    \n",
    "    def is_complete(self, assignment):\n",
    "        \"\"\"An assignment is complete if it is consistent, and all constraints\n",
    "        are satisfied.\n",
    "        \n",
    "        Hint: Backtracking search checks consistency of each assignment, so checking\n",
    "        for completeness can be done very efficiently\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        assignment : dict(sympy.Symbol: Integer)\n",
    "            An assignment of values to variables that have previously been checked\n",
    "            for consistency with the CSP constraints\n",
    "        \"\"\"\n",
    "        raise NotImplementedError(\"TODO: implement the is_complete() method of the CSP\")\n",
    "    \n",
    "    def is_consistent(self, var, value, assignment):\n",
    "        \"\"\"Check consistency of a proposed variable assignment\n",
    "                \n",
    "        self._constraints[x] returns a set of constraints that involve variable `x`.\n",
    "        An assignment is consistent unless the assignment it causes a constraint to\n",
    "        return False (partial assignments are always consistent).\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        var : sympy.Symbol\n",
    "            One of the symbolic variables in the CSP\n",
    "            \n",
    "        value : Numeric\n",
    "            A valid value (i.e., in the domain of) the variable `var` for assignment\n",
    "\n",
    "        assignment : dict(sympy.Symbol: Integer)\n",
    "            A dictionary mapping CSP variables to row assignment of each queen\n",
    "            \n",
    "        \"\"\"\n",
    "        raise NotImplementedError(\"TODO: implement the is_consistent() method of the CSP\")\n",
    "        \n",
    "        \n",
    "    def inference(self, var, value):\n",
    "        \"\"\"Perform logical inference based on proposed variable assignment\n",
    "        \n",
    "        Returns an empty dictionary by default; function can be overridden to\n",
    "        check arc-, path-, or k-consistency; returning None signals \"failure\".\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        var : sympy.Symbol\n",
    "            One of the symbolic variables in the CSP\n",
    "        \n",
    "        value : Integer\n",
    "            A valid value (i.e., in the domain of) the variable `var` for assignment\n",
    "            \n",
    "        Returns\n",
    "        -------\n",
    "        dict(sympy.Symbol: Integer) or None\n",
    "            A partial set of values mapped to variables in the CSP based on inferred\n",
    "            constraints from previous mappings, or None to indicate failure\n",
    "        \"\"\"\n",
    "        # TODO (Optional): Implement this function based on AIMA discussion\n",
    "        return {}\n",
    "    \n",
    "    def show(self, assignment):\n",
    "        \"\"\"Display a chessboard with queens drawn in the locations specified by an\n",
    "        assignment\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        assignment : dict(sympy.Symbol: Integer)\n",
    "            A dictionary mapping CSP variables to row assignment of each queen\n",
    "            \n",
    "        \"\"\"\n",
    "        locations = [(i, assignment[j]) for i, j in enumerate(self.variables)\n",
    "                     if assignment.get(j, None) is not None]\n",
    "        displayBoard(locations, self.size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## III. Backtracking Search\n",
    "Implement the [backtracking search](https://github.com/aimacode/aima-pseudocode/blob/master/md/Backtracking-Search.md) algorithm (required) and helper functions (optional) from the AIMA text.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def select(csp, assignment):\n",
    "    \"\"\"Choose an unassigned variable in a constraint satisfaction problem \"\"\"\n",
    "    # TODO (Optional): Implement a more sophisticated selection routine from AIMA\n",
    "    for var in csp.variables:\n",
    "        if var not in assignment:\n",
    "            return var\n",
    "    return None\n",
    "\n",
    "def order_values(var, assignment, csp):\n",
    "    \"\"\"Select the order of the values in the domain of a variable for checking during search;\n",
    "    the default is lexicographically.\n",
    "    \"\"\"\n",
    "    # TODO (Optional): Implement a more sophisticated search ordering routine from AIMA\n",
    "    return csp.domains[var]\n",
    "\n",
    "def backtracking_search(csp):\n",
    "    \"\"\"Helper function used to initiate backtracking search \"\"\"\n",
    "    return backtrack({}, csp)\n",
    "\n",
    "def backtrack(assignment, csp):\n",
    "    \"\"\"Perform backtracking search for a valid assignment to a CSP\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    assignment : dict(sympy.Symbol: Integer)\n",
    "        An partial set of values mapped to variables in the CSP\n",
    "        \n",
    "    csp : CSP\n",
    "        A problem encoded as a CSP. Interface should include csp.variables, csp.domains,\n",
    "        csp.inference(), csp.is_consistent(), and csp.is_complete().\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    dict(sympy.Symbol: Integer) or None\n",
    "        A partial set of values mapped to variables in the CSP, or None to indicate failure\n",
    "    \"\"\"\n",
    "    raise NotImplementedError(\"TODO: complete the backtrack function\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solve the CSP\n",
    "With backtracking implemented, now you can use it to solve instances of the problem. We've started with the classical 8-queen version, but you can try other sizes as well.  Boards larger than 12x12 may take some time to solve because sympy is slow in the way its being used here, and because the selection and value ordering methods haven't been implemented.  See if you can implement any of the techniques in the AIMA text to speed up the solver!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "num_queens = 8\n",
    "csp = NQueensCSP(num_queens)\n",
    "var = csp.variables[0]\n",
    "print(\"CSP problems have variables, each variable has a domain, and the problem has a list of constraints.\")\n",
    "print(\"Showing the variables for the N-Queens CSP:\")\n",
    "display(csp.variables)\n",
    "print(\"Showing domain for {}:\".format(var))\n",
    "display(csp.domains[var])\n",
    "print(\"And showing the constraints for {}:\".format(var))\n",
    "display(csp._constraints[var])\n",
    "\n",
    "print(\"Solving N-Queens CSP...\")\n",
    "assn = backtracking_search(csp)\n",
    "if assn is not None:\n",
    "    csp.show(assn)\n",
    "    print(\"Solution found:\\n{!s}\".format(assn))\n",
    "else:\n",
    "    print(\"No solution found.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## IV. Experiments (Optional)\n",
    "For each optional experiment, discuss the answers to these questions on the forum: Do you expect this change to be more efficient, less efficient, or the same?  Why or why not?  Is your prediction correct?  What metric did you compare (e.g., time, space, nodes visited, etc.)?\n",
    "\n",
    "- Implement a _bad_ N-queens solver: generate & test candidate solutions one at a time until a valid solution is found.  For example, represent the board as an array with $N^2$ elements, and let each element be True if there is a queen in that box, and False if it is empty.  Use an $N^2$-bit counter to generate solutions, then write a function to check if each solution is valid.  Notice that this solution doesn't require any of the techniques we've applied to other problems -- there is no DFS or backtracking, nor constraint propagation, or even explicitly defined variables.\n",
    "- Use more complex constraints -- i.e., generalize the binary constraint RowDiff to an N-ary constraint AllRowsDiff, etc., -- and solve the problem again.\n",
    "- Rewrite the CSP class to use forward checking to restrict the domain of each variable as new values are assigned.\n",
    "- The sympy library isn't very fast, so this version of the CSP doesn't work well on boards bigger than about 12x12.  Write a new representation of the problem class that uses constraint functions (like the Sudoku project) to implicitly track constraint satisfaction through the restricted domain of each variable.  How much larger can you solve?\n",
    "- Create your own CSP!"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:aind]",
   "language": "python",
   "name": "conda-env-aind-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}