{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [4.3 Solving a CSP using Search](http://artint.info/2e/html/ArtInt2e.Ch4.S3.html)\n",
    "- [Implementation Details](http://artint.info/AIPython/aipython.pdf#page=56) (page 56)\n",
    "\n",
    "## About\n",
    "We can already solve CSPs by using the search methods we learnt before. The search space is partial assignments to the variables in the CSP.\n",
    "\n",
    "For example, imagine a CSP with two variables, `A` and `B`, and domains both `\\{1,2,3\\}`. We start with the root node, `{}`, and fill in its children at the first level: `{A:1}`, `{A:2}`, and `{A:3}`. Then each of those nodes have several children, merging its own values with the values of the next variable. For example, the children of `{A:1}` are `{A:1, B:1}`, `{A:1, B:2}`, and `{A:1, B:3}`. For the sake of simplicity, in the second level we will just show `{B:1}`, `{B:2}`, and `{B:3}` but the user can figure out the assignment of variable `A` by tracking the node's parent. The tree goes deeper and deeper in this manner.\n",
    "\n",
    "Because we are interested in __whether__ there is a solution, rather than the path to the solution (notice that all solutions have the same length), and because the search space is acyclic, we can use depth-first search (with branch-and-bound technique to improve the performance). As an optimization, before generating the neighboring nodes, we check if those nodes satisfy the constraints; if not, there is no point in going on further, as it will never lead to a solution.\n",
    "\n",
    "In order to use search algorithms on our CSP, we must first convert it into a search problem by using the class `Search_from_CSP`.\n",
    "\n",
    "You can run each cell by selecting it and pressing *Ctrl+Enter* in Windows or *Shift+Return* in MacOS. Alternatively, you can click the *Play* button in the toolbar, to the left of the stop button. For more information, check out our AISpace2 [Tutorial](https://aispace2.github.io/AISpace2/tutorial.html).\n",
    "\n",
    "Feel free to modify our codes either in this notebook or somewhere outside (e.g. python files in `/aipython/`). If you want to modify our codes outside, you might find [this](https://aispace2.github.io/AISpace2/tutorial.html#tutorial-faq-why-update-aipython-not-reflect) helpful for how your changes can take effect.\n",
    "\n",
    "You need to run the following command to import our pre-defined problems. You can also define your own problems ([how?](https://aispace2.github.io/AISpace2/tutorial.html#tutorial-csp-construct-yourself)). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run this to import pre-defined problems\n",
    "from aipython.cspProblem import csp_simple1, csp_simple2, csp_simple3, csp_extended1, csp_extended2, csp_extended3, csp_crossword1, csp_crossword2, csp_crossword3, csp_crossword2d, csp_five_queens, csp_eight_queens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from aipython.searchGeneric import Searcher\n",
    "from aipython.cspSearch import Search_from_CSP\n",
    "\n",
    "search_csp = Searcher(problem=Search_from_CSP(csp=csp_simple2))\n",
    "\n",
    "# Visualization options\n",
    "# For more explanation please visit: https://aispace2.github.io/AISpace2/tutorial.html#tutorial-common-visualization-options\n",
    "search_csp.sleep_time = 0.2 # The time, in seconds, between each step in auto solving\n",
    "search_csp.line_width = 2.0 # The thickness of edges\n",
    "search_csp.text_size = 13 # The fontsize of the text\n",
    "search_csp.detail_level = 2 # 0=no text, 1=truncated text, 2=full text\n",
    "search_csp.show_edge_costs = False\n",
    "\n",
    "# Display the widget\n",
    "display(search_csp)\n",
    "search_csp.search()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}