arc_consistency_heuristics.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "# Constraint Satisfaction Problems\n",
    "---\n",
    "# Heuristics for Arc-Consistency Algorithms\n",
    "\n",
    "## Introduction\n",
    "A ***Constraint Satisfaction Problem*** is a triple $(X,D,C)$ where: \n",
    "- $X$ is a set of variables $X_1, …, X_n$;\n",
    "- $D$ is a set of domains $D_1, …, D_n$, one for each variable and each of which consists of a set of allowable values $v_1, ..., v_k$;\n",
    "- $C$ is a set of constraints that specify allowable combinations of values.\n",
    "\n",
    "A CSP is called *arc-consistent* if every value in the domain of every variable is supported by all the neighbors of the variable while, is called *inconsistent*, if it has no solutions. <br>\n",
    "***Arc-consistency algorithms*** remove all unsupported values from the domains of variables making the CSP *arc-consistent* or decide that a CSP is *inconsistent* by finding that some variable has no supported values in its domain. <br> \n",
    "Heuristics significantly enhance the efficiency of the *arc-consistency algorithms* improving their average performance in terms of *consistency-checks* which can be considered a standard measure of goodness for such algorithms. *Arc-heuristic* operate at arc-level and selects the constraint that will be used for the next check, while *domain-heuristics* operate at domain-level and selects which values will be used for the next support-check."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from csp import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Domain-Heuristics for Arc-Consistency Algorithms\n",
    "In <a name=\"ref-1\"/>[[1]](#cite-van2002domain) are investigated the effects of a *domain-heuristic* based on the notion of a *double-support check* by studying its average time-complexity.\n",
    "\n",
    "The objective of *arc-consistency algorithms* is to resolve some uncertainty; it has to be know, for each $v_i \\in D_i$ and for each $v_j \\in D_j$, whether it is supported.\n",
    "\n",
    "A *single-support check*, $(v_i, v_j) \\in C_{ij}$, is one in which, before the check is done, it is already known that either $v_i$ or $v_j$ are supported. \n",
    "\n",
    "A *double-support check* $(v_i, v_j) \\in C_{ij}$, is one in which there is still, before the check, uncertainty about the support-status of both $v_i$ and $v_j$. \n",
    "\n",
    "If a *double-support check* is successful, two uncertainties are resolved. If a *single-support check* is successful, only one uncertainty is resolved. A good *arc-consistency algorithm*, therefore, would always choose to do a *double-support check* in preference of a *single-support check*, because the cormer offers the potential higher payback.\n",
    "\n",
    "The improvement with *double-support check* is that, where possible, *consistency-checks* are used to find supports for two values, one value in the domain of each variable, which were previously known to be unsupported. It is motivated by the insight that *in order to minimize the number of consistency-checks it is necessary to maximize the number of uncertainties which are resolved per check*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "### AC-3b: an improved version of AC-3 with Double-Support Checks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As shown in <a name=\"ref-2\"/>[[2]](#cite-van2000improving) the idea is to use *double-support checks* to improve the average performance of `AC3` which does not exploit the fact that relations are bidirectional and results in a new general purpose *arc-consistency algorithm* called `AC3b`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[0;32mdef\u001b[0m \u001b[0mAC3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mqueue\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mremovals\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0marc_heuristic\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mdom_j_up\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;34m\"\"\"[Figure 6.3]\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mif\u001b[0m \u001b[0mqueue\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0mqueue\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXk\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mXi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvariables\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mXk\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mneighbors\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msupport_pruning\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0mqueue\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0marc_heuristic\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mqueue\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0mchecks\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mwhile\u001b[0m \u001b[0mqueue\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mqueue\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0mrevised\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mrevise\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mremovals\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mif\u001b[0m \u001b[0mrevised\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurr_domains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mreturn\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m  \u001b[0;31m# CSP is inconsistent\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mfor\u001b[0m \u001b[0mXk\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mneighbors\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mif\u001b[0m \u001b[0mXk\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0mqueue\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXk\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXi\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mreturn\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m  \u001b[0;31m# CSP is satisfiable\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%psource AC3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[0;32mdef\u001b[0m \u001b[0mrevise\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mremovals\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;34m\"\"\"Return true if we remove a value.\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0mrevised\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mfor\u001b[0m \u001b[0mx\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurr_domains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;31m# If Xi=x conflicts with Xj=y for every possible y, eliminate Xi=x\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;31m# if all(not csp.constraints(Xi, x, Xj, y) for y in csp.curr_domains[Xj]):\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0mconflict\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mfor\u001b[0m \u001b[0my\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurr_domains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXj\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mif\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconstraints\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mconflict\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0mchecks\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mconflict\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mbreak\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mif\u001b[0m \u001b[0mconflict\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mprune\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mremovals\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0mrevised\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mreturn\u001b[0m \u001b[0mrevised\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%psource revise"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At any stage in the process of making 2-variable CSP *arc-consistent* in `AC3b`:\n",
    "- there is a set $S_i^+ \\subseteq D_i$ whose values are all known to be supported by $X_j$;\n",
    "- there is a set $S_i^? = D_i \\setminus S_i^+$ whose values are unknown, as yet, to be supported by $X_j$.\n",
    "\n",
    "The same holds if the roles for $X_i$ and $X_j$ are exchanged.\n",
    "\n",
    "In order to establish support for a value $v_i^? \\in S_i^?$ it seems better to try to find a support among the values in $S_j^?$ first, because for each $v_j^? \\in S_j^?$ the check $(v_i^?,v_j^?) \\in C_{ij}$ is a *double-support check* and it is just as likely that any $v_j^? \\in S_j^?$ supports $v_i^?$ than it is that any $v_j^+ \\in S_j^+$ does. Only if no support can be found among the elements in $S_j^?$, should the elements $v_j^+$ in $S_j^+$ be used for *single-support checks* $(v_i^?,v_j^+) \\in C_{ij}$. After it has been decided for each value in $D_i$ whether it is supported or not, either $S_x^+ = \\emptyset$ and the 2-variable CSP is *inconsistent*, or $S_x^+ \\neq \\emptyset$ and the CSP is *satisfiable*. In the latter case, the elements from $D_i$ which are supported by $j$ are given by $S_x^+$. The elements in $D_j$ which are supported by $x$ are given by the union of $S_j^+$ with the set of those elements of $S_j^?$ which further processing will show to be supported by some $v_i^+ \\in S_x^+$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[0;32mdef\u001b[0m \u001b[0mAC3b\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mqueue\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mremovals\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0marc_heuristic\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mdom_j_up\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mif\u001b[0m \u001b[0mqueue\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0mqueue\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXk\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mXi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvariables\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mXk\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mneighbors\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msupport_pruning\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0mqueue\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0marc_heuristic\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mqueue\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0mchecks\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mwhile\u001b[0m \u001b[0mqueue\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mqueue\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;31m# Si_p values are all known to be supported by Xj\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;31m# Sj_p values are all known to be supported by Xi\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;31m# Dj - Sj_p = Sj_u values are unknown, as yet, to be supported by Xi\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0mSi_p\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mSj_p\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mSj_u\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mpartition\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mSi_p\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mreturn\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m  \u001b[0;31m# CSP is inconsistent\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0mrevised\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mfor\u001b[0m \u001b[0mx\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mset\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurr_domains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mSi_p\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mprune\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mremovals\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0mrevised\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mif\u001b[0m \u001b[0mrevised\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mfor\u001b[0m \u001b[0mXk\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mneighbors\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mif\u001b[0m \u001b[0mXk\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0mqueue\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXk\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXi\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mif\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXi\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mqueue\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mif\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mqueue\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mset\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;31m# or queue -= {(Xj, Xi)} or queue.remove((Xj, Xi))\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mqueue\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdifference_update\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m{\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXi\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mqueue\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdifference_update\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXi\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;31m# the elements in D_j which are supported by Xi are given by the union of Sj_p with the set of those\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;31m# elements of Sj_u which further processing will show to be supported by some vi_p in Si_p\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mfor\u001b[0m \u001b[0mvj_p\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mSj_u\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mfor\u001b[0m \u001b[0mvi_p\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mSi_p\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0mconflict\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0;32mif\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconstraints\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvj_p\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvi_p\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                        \u001b[0mconflict\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                        \u001b[0mSj_p\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mvj_p\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0mchecks\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mconflict\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                        \u001b[0;32mbreak\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0mrevised\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mfor\u001b[0m \u001b[0mx\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mset\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurr_domains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXj\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mSj_p\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mprune\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mremovals\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mrevised\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mif\u001b[0m \u001b[0mrevised\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mfor\u001b[0m \u001b[0mXk\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mneighbors\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXj\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0;32mif\u001b[0m \u001b[0mXk\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0mXi\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                        \u001b[0mqueue\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXk\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mreturn\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m  \u001b[0;31m# CSP is satisfiable\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%psource AC3b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[0;32mdef\u001b[0m \u001b[0mpartition\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0mSi_p\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mset\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0mSj_p\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mset\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0mSj_u\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mset\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurr_domains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXj\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mfor\u001b[0m \u001b[0mvi_u\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurr_domains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0mconflict\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;31m# now, in order to establish support for a value vi_u in Di it seems better to try to find a support among\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;31m# the values in Sj_u first, because for each vj_u in Sj_u the check (vi_u, vj_u) is a double-support check\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;31m# and it is just as likely that any vj_u in Sj_u supports vi_u than it is that any vj_p in Sj_p does...\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mfor\u001b[0m \u001b[0mvj_u\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mSj_u\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mSj_p\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;31m# double-support check\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mif\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconstraints\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvi_u\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvj_u\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mconflict\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mSi_p\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mvi_u\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mSj_p\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mvj_u\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0mchecks\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mconflict\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mbreak\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;31m# ... and only if no support can be found among the elements in Sj_u, should the elements vj_p in Sj_p be used\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;31m# for single-support checks (vi_u, vj_p)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mif\u001b[0m \u001b[0mconflict\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mfor\u001b[0m \u001b[0mvj_p\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mSj_p\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;31m# single-support check\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mif\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconstraints\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvi_u\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvj_p\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0mconflict\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0mSi_p\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mvi_u\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mchecks\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mconflict\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0;32mbreak\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mreturn\u001b[0m \u001b[0mSi_p\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mSj_p\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mSj_u\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mSj_p\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%psource partition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "`AC3b` is a refinement of the `AC3` algorithm which consists of the fact that if, when arc $(i,j)$ is being processed and the reverse arc $(j,i)$ is also in the queue, then consistency-checks can be saved because only support for the elements in $S_j^?$ has to be found (as opposed to support for all the elements in $D_j$ in the\n",
    "`AC3` algorithm). <br>\n",
    "`AC3b` inherits all its properties like $\\mathcal{O}(ed^3)$ time-complexity and $\\mathcal{O}(e + nd)$ space-complexity fron `AC3` and where $n$ denotes the number of variables in the CSP, $e$ denotes the number of binary constraints and $d$ denotes the maximum domain-size of the variables."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "## Arc-Heuristics for Arc-Consistency Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "Many *arc-heuristics* can be devised, based on three major features of CSPs:\n",
    "- the number of acceptable pairs in each constraint (the *constraint size* or *satisfiability*);\n",
    "- the *domain size*;\n",
    "- the number of binary constraints that each variable participates in, equal to the *degree* of the node of that variable in the constraint graph. \n",
    "\n",
    "Simple examples of heuristics that might be expected to improve the efficiency of relaxation are:\n",
    "- ordering the list of variable pairs by *increasing* relative *satisfiability*;\n",
    "- ordering by *increasing size of the domain* of the variable $v_j$ relaxed against $v_i$;\n",
    "- ordering by *descending degree* of node of the variable relaxed.\n",
    "\n",
    "In <a name=\"ref-3\"/>[[3]](#cite-wallace1992ordering) are investigated the effects of these *arc-heuristics* in an empirical way, experimenting the effects of them on random CSPs. Their results demonstrate that the first two, later called `sat up` and `dom j up` for n-ary and binary CSPs respectively, significantly reduce the number of *consistency-checks*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[0;32mdef\u001b[0m \u001b[0mdom_j_up\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mqueue\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mreturn\u001b[0m \u001b[0mSortedSet\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mqueue\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mlambda\u001b[0m \u001b[0mt\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mneg\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurr_domains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mt\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%psource dom_j_up"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[0;32mdef\u001b[0m \u001b[0msat_up\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mto_do\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mreturn\u001b[0m \u001b[0mSortedSet\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mto_do\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mkey\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mlambda\u001b[0m \u001b[0mt\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m1\u001b[0m \u001b[0;34m/\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mvar\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mt\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mscope\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%psource sat_up"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "## Experimental Results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "For the experiments below on binary CSPs, in addition to the two *arc-consistency algorithms* already cited above, `AC3` and `AC3b`, the `AC4` algorithm was used. <br>\n",
    "The `AC4` algorithm runs in $\\mathcal{O}(ed^2)$ worst-case time but can be slower than `AC3` on average cases."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[0;32mdef\u001b[0m \u001b[0mAC4\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mqueue\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mremovals\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0marc_heuristic\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mdom_j_up\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mif\u001b[0m \u001b[0mqueue\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0mqueue\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXk\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mXi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mvariables\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mXk\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mneighbors\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msupport_pruning\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0mqueue\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0marc_heuristic\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mqueue\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0msupport_counter\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mCounter\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0mvariable_value_pairs_supported\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdefaultdict\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mset\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0munsupported_variable_value_pairs\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0mchecks\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;31m# construction and initialization of support sets\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mwhile\u001b[0m \u001b[0mqueue\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mqueue\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0mrevised\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mfor\u001b[0m \u001b[0mx\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurr_domains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mfor\u001b[0m \u001b[0my\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurr_domains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXj\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mif\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconstraints\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0msupport_counter\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0mvariable_value_pairs_supported\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mchecks\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mif\u001b[0m \u001b[0msupport_counter\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mprune\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mremovals\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mrevised\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0munsupported_variable_value_pairs\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mif\u001b[0m \u001b[0mrevised\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurr_domains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mreturn\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m  \u001b[0;31m# CSP is inconsistent\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;31m# propagation of removed values\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mwhile\u001b[0m \u001b[0munsupported_variable_value_pairs\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0munsupported_variable_value_pairs\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mfor\u001b[0m \u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mvariable_value_pairs_supported\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXj\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0mrevised\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mif\u001b[0m \u001b[0mx\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurr_domains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0msupport_counter\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m-=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mif\u001b[0m \u001b[0msupport_counter\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mXj\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mprune\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mremovals\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0mrevised\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0munsupported_variable_value_pairs\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mif\u001b[0m \u001b[0mrevised\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurr_domains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mXi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0;32mreturn\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m  \u001b[0;31m# CSP is inconsistent\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m    \u001b[0;32mreturn\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m  \u001b[0;31m# CSP is satisfiable\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%psource AC4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sudoku"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "#### Easy Sudoku"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ". . 3 | . 2 . | 6 . .\n",
      "9 . . | 3 . 5 | . . 1\n",
      ". . 1 | 8 . 6 | 4 . .\n",
      "------+-------+------\n",
      ". . 8 | 1 . 2 | 9 . .\n",
      "7 . . | . . . | . . 8\n",
      ". . 6 | 7 . 8 | 2 . .\n",
      "------+-------+------\n",
      ". . 2 | 6 . 9 | 5 . .\n",
      "8 . . | 2 . 3 | . . 9\n",
      ". . 5 | . 1 . | 3 . .\n"
     ]
    }
   ],
   "source": [
    "sudoku = Sudoku(easy1)\n",
    "sudoku.display(sudoku.infer_assignment())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 23.6 ms, sys: 0 ns, total: 23.6 ms\n",
      "Wall time: 22.4 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC3 needs 11322 consistency-checks'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time _, checks = AC3(sudoku, arc_heuristic=no_arc_heuristic)\n",
    "f'AC3 needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 7.43 ms, sys: 3.68 ms, total: 11.1 ms\n",
      "Wall time: 10.7 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC3b needs 8345 consistency-checks'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku = Sudoku(easy1)\n",
    "%time _, checks = AC3b(sudoku, arc_heuristic=no_arc_heuristic)\n",
    "f'AC3b needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 56.3 ms, sys: 0 ns, total: 56.3 ms\n",
      "Wall time: 55.4 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC4 needs 27718 consistency-checks'"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku = Sudoku(easy1)\n",
    "%time _, checks = AC4(sudoku, arc_heuristic=no_arc_heuristic)\n",
    "f'AC4 needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 17.2 ms, sys: 0 ns, total: 17.2 ms\n",
      "Wall time: 16.9 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC3 with DOM J UP arc heuristic needs 6925 consistency-checks'"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku = Sudoku(easy1)\n",
    "%time _, checks = AC3(sudoku, arc_heuristic=dom_j_up)\n",
    "f'AC3 with DOM J UP arc heuristic needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 40.9 ms, sys: 2.47 ms, total: 43.4 ms\n",
      "Wall time: 41.7 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC3b with DOM J UP arc heuristic needs 6278 consistency-checks'"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku = Sudoku(easy1)\n",
    "%time _, checks = AC3b(sudoku, arc_heuristic=dom_j_up)\n",
    "f'AC3b with DOM J UP arc heuristic needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 38.9 ms, sys: 1.96 ms, total: 40.9 ms\n",
      "Wall time: 40.7 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC4 with DOM J UP arc heuristic needs 9393 consistency-checks'"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku = Sudoku(easy1)\n",
    "%time _, checks = AC4(sudoku, arc_heuristic=dom_j_up)\n",
    "f'AC4 with DOM J UP arc heuristic needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 8 3 | 9 2 1 | 6 5 7\n",
      "9 6 7 | 3 4 5 | 8 2 1\n",
      "2 5 1 | 8 7 6 | 4 9 3\n",
      "------+-------+------\n",
      "5 4 8 | 1 3 2 | 9 7 6\n",
      "7 2 9 | 5 6 4 | 1 3 8\n",
      "1 3 6 | 7 9 8 | 2 4 5\n",
      "------+-------+------\n",
      "3 7 2 | 6 8 9 | 5 1 4\n",
      "8 1 4 | 2 5 3 | 7 6 9\n",
      "6 9 5 | 4 1 7 | 3 8 2\n"
     ]
    }
   ],
   "source": [
    "backtracking_search(sudoku, select_unassigned_variable=mrv, inference=forward_checking)\n",
    "sudoku.display(sudoku.infer_assignment())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "#### Harder Sudoku"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 1 7 | 3 6 9 | 8 . 5\n",
      ". 3 . | . . . | . . .\n",
      ". . . | 7 . . | . . .\n",
      "------+-------+------\n",
      ". 2 . | . . . | . 6 .\n",
      ". . . | . 8 . | 4 . .\n",
      ". . . | . 1 . | . . .\n",
      "------+-------+------\n",
      ". . . | 6 . 3 | . 7 .\n",
      "5 . . | 2 . . | . . .\n",
      "1 . 4 | . . . | . . .\n"
     ]
    }
   ],
   "source": [
    "sudoku = Sudoku(harder1)\n",
    "sudoku.display(sudoku.infer_assignment())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 17.7 ms, sys: 481 µs, total: 18.2 ms\n",
      "Wall time: 17.2 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC3 needs 12837 consistency-checks'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time _, checks = AC3(sudoku, arc_heuristic=no_arc_heuristic)\n",
    "f'AC3 needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 24.1 ms, sys: 2.6 ms, total: 26.7 ms\n",
      "Wall time: 25.1 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC3b needs 8864 consistency-checks'"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku = Sudoku(harder1)\n",
    "%time _, checks = AC3b(sudoku, arc_heuristic=no_arc_heuristic)\n",
    "f'AC3b needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 63.4 ms, sys: 3.48 ms, total: 66.9 ms\n",
      "Wall time: 65.5 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC4 needs 44213 consistency-checks'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku = Sudoku(harder1)\n",
    "%time _, checks = AC4(sudoku, arc_heuristic=no_arc_heuristic)\n",
    "f'AC4 needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 9.96 ms, sys: 570 µs, total: 10.5 ms\n",
      "Wall time: 10.3 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC3 with DOM J UP arc heuristic needs 7045 consistency-checks'"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku = Sudoku(harder1)\n",
    "%time _, checks = AC3(sudoku, arc_heuristic=dom_j_up)\n",
    "f'AC3 with DOM J UP arc heuristic needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 36.1 ms, sys: 0 ns, total: 36.1 ms\n",
      "Wall time: 35.5 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC3b with DOM J UP arc heuristic needs 6994 consistency-checks'"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku = Sudoku(harder1)\n",
    "%time _, checks = AC3b(sudoku, arc_heuristic=dom_j_up)\n",
    "f'AC3b with DOM J UP arc heuristic needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 40.3 ms, sys: 0 ns, total: 40.3 ms\n",
      "Wall time: 39.7 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC4 with DOM J UP arc heuristic needs 19210 consistency-checks'"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku = Sudoku(harder1)\n",
    "%time _, checks = AC4(sudoku, arc_heuristic=dom_j_up)\n",
    "f'AC4 with DOM J UP arc heuristic needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 1 7 | 3 6 9 | 8 2 5\n",
      "6 3 2 | 1 5 8 | 9 4 7\n",
      "9 5 8 | 7 2 4 | 3 1 6\n",
      "------+-------+------\n",
      "8 2 5 | 4 3 7 | 1 6 9\n",
      "7 9 1 | 5 8 6 | 4 3 2\n",
      "3 4 6 | 9 1 2 | 7 5 8\n",
      "------+-------+------\n",
      "2 8 9 | 6 4 3 | 5 7 1\n",
      "5 7 3 | 2 9 1 | 6 8 4\n",
      "1 6 4 | 8 7 5 | 2 9 3\n"
     ]
    }
   ],
   "source": [
    "backtracking_search(sudoku, select_unassigned_variable=mrv, inference=forward_checking)\n",
    "sudoku.display(sudoku.infer_assignment())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "### 8 Queens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ". - . - . - . -      0  0  0  0  0  0  0  0  \n",
      "- . - . - . - .      0  0  0  0  0  0  0  0  \n",
      ". - . - . - . -      0  0  0  0  0  0  0  0  \n",
      "- . - . - . - .      0  0  0  0  0  0  0  0  \n",
      ". - . - . - . -      0  0  0  0  0  0  0  0  \n",
      "- . - . - . - .      0  0  0  0  0  0  0  0  \n",
      ". - . - . - . -      0  0  0  0  0  0  0  0  \n",
      "- . - . - . - .      0  0  0  0  0  0  0  0  \n"
     ]
    }
   ],
   "source": [
    "chess = NQueensCSP(8)\n",
    "chess.display(chess.infer_assignment())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 689 µs, sys: 193 µs, total: 882 µs\n",
      "Wall time: 892 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC3 needs 666 consistency-checks'"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time _, checks = AC3(chess, arc_heuristic=no_arc_heuristic)\n",
    "f'AC3 needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 451 µs, sys: 127 µs, total: 578 µs\n",
      "Wall time: 584 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC3b needs 428 consistency-checks'"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chess = NQueensCSP(8)\n",
    "%time _, checks = AC3b(chess, arc_heuristic=no_arc_heuristic)\n",
    "f'AC3b needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 8.53 ms, sys: 109 µs, total: 8.64 ms\n",
      "Wall time: 8.48 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC4 needs 4096 consistency-checks'"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chess = NQueensCSP(8)\n",
    "%time _, checks = AC4(chess, arc_heuristic=no_arc_heuristic)\n",
    "f'AC4 needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.88 ms, sys: 0 ns, total: 1.88 ms\n",
      "Wall time: 1.88 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC3 with DOM J UP arc heuristic needs 666 consistency-checks'"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chess = NQueensCSP(8)\n",
    "%time _, checks = AC3(chess, arc_heuristic=dom_j_up)\n",
    "f'AC3 with DOM J UP arc heuristic needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.21 ms, sys: 326 µs, total: 1.53 ms\n",
      "Wall time: 1.54 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC3b with DOM J UP arc heuristic needs 792 consistency-checks'"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chess = NQueensCSP(8)\n",
    "%time _, checks = AC3b(chess, arc_heuristic=dom_j_up)\n",
    "f'AC3b with DOM J UP arc heuristic needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 4.71 ms, sys: 0 ns, total: 4.71 ms\n",
      "Wall time: 4.65 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AC4 with DOM J UP arc heuristic needs 4096 consistency-checks'"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chess = NQueensCSP(8)\n",
    "%time _, checks = AC4(chess, arc_heuristic=dom_j_up)\n",
    "f'AC4 with DOM J UP arc heuristic needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ". - . - Q - . -      2  2  3  3  0* 1  1  2  \n",
      "- Q - . - . - .      1  0* 3  3  2  2  2  2  \n",
      ". - . - . Q . -      3  2  3  2  2  0* 3  2  \n",
      "Q . - . - . - .      0* 3  1  2  3  3  3  3  \n",
      ". - . - . - Q -      2  2  2  2  3  3  0* 2  \n",
      "- . - Q - . - .      2  1  3  0* 2  3  2  2  \n",
      ". - . - . - . Q      1  3  2  3  3  1  2  0* \n",
      "- . Q . - . - .      2  2  0* 2  2  2  2  2  \n"
     ]
    }
   ],
   "source": [
    "backtracking_search(chess, select_unassigned_variable=mrv, inference=forward_checking)\n",
    "chess.display(chess.infer_assignment())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the experiments below on n-ary CSPs, due to the n-ary constraints, the `GAC` algorithm was used. <br>\n",
    "The `GAC` algorithm has $\\mathcal{O}(er^2d^t)$ time-complexity and $\\mathcal{O}(erd)$ space-complexity where $e$ denotes the number of n-ary constraints, $r$ denotes the constraint arity and $d$ denotes the maximum domain-size of the variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "    \u001b[0;32mdef\u001b[0m \u001b[0mGAC\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0morig_domains\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mto_do\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0marc_heuristic\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0msat_up\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;34m\"\"\"Makes this CSP arc-consistent using Generalized Arc Consistency\u001b[0m\n",
       "\u001b[0;34m        orig_domains is the original domains\u001b[0m\n",
       "\u001b[0;34m        to_do is a set of (variable,constraint) pairs\u001b[0m\n",
       "\u001b[0;34m        returns the reduced domains (an arc-consistent variable:domain dictionary)\u001b[0m\n",
       "\u001b[0;34m        \"\"\"\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mif\u001b[0m \u001b[0morig_domains\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0morig_domains\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdomains\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mif\u001b[0m \u001b[0mto_do\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0mto_do\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mconst\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mconst\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcsp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconstraints\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mvar\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mconst\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mscope\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0mto_do\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mto_do\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcopy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0mdomains\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0morig_domains\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcopy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0mto_do\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0marc_heuristic\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mto_do\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0mchecks\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mwhile\u001b[0m \u001b[0mto_do\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0mvar\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mconst\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mto_do\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0mother_vars\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mov\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mov\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mconst\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mscope\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mov\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0mnew_domain\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mset\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mif\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mother_vars\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mfor\u001b[0m \u001b[0mval\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mdomains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0;32mif\u001b[0m \u001b[0mconst\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mholds\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m{\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mval\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                        \u001b[0mnew_domain\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mval\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0mchecks\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;31m# new_domain = {val for val in domains[var]\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;31m#               if const.holds({var: val})}\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32melif\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mother_vars\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mother\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mother_vars\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mfor\u001b[0m \u001b[0mval\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mdomains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0;32mfor\u001b[0m \u001b[0mother_val\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mdomains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mother\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                        \u001b[0mchecks\u001b[0m \u001b[0;34m+=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                        \u001b[0;32mif\u001b[0m \u001b[0mconst\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mholds\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m{\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mval\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mother\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mother_val\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                            \u001b[0mnew_domain\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mval\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                            \u001b[0;32mbreak\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;31m# new_domain = {val for val in domains[var]\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;31m#               if any(const.holds({var: val, other: other_val})\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;31m#                      for other_val in domains[other])}\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m  \u001b[0;31m# general case\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mfor\u001b[0m \u001b[0mval\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mdomains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0mholds\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0many_holds\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdomains\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mconst\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mval\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mother_vars\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mchecks\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0;32mif\u001b[0m \u001b[0mholds\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                        \u001b[0mnew_domain\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mval\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;31m# new_domain = {val for val in domains[var]\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;31m#               if self.any_holds(domains, const, {var: val}, other_vars)}\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m            \u001b[0;32mif\u001b[0m \u001b[0mnew_domain\u001b[0m \u001b[0;34m!=\u001b[0m \u001b[0mdomains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mdomains\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnew_domain\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mnew_domain\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                    \u001b[0;32mreturn\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdomains\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0madd_to_do\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnew_to_do\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mvar\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mconst\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdifference\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mto_do\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m                \u001b[0mto_do\u001b[0m \u001b[0;34m|=\u001b[0m \u001b[0madd_to_do\u001b[0m\u001b[0;34m\u001b[0m\n",
       "\u001b[0;34m\u001b[0m        \u001b[0;32mreturn\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdomains\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mchecks\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%psource ACSolver.GAC"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "### Crossword"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[_] [_] [_] [*] [*] \n",
      "[_] [*] [_] [*] [*] \n",
      "[_] [_] [_] [_] [*] \n",
      "[_] [*] [_] [*] [*] \n",
      "[*] [*] [_] [_] [_] \n",
      "[*] [*] [_] [*] [*] \n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'ant',\n",
       " 'big',\n",
       " 'book',\n",
       " 'bus',\n",
       " 'buys',\n",
       " 'car',\n",
       " 'ginger',\n",
       " 'has',\n",
       " 'hold',\n",
       " 'lane',\n",
       " 'search',\n",
       " 'symbol',\n",
       " 'syntax',\n",
       " 'year'}"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "crossword = Crossword(crossword1, words1)\n",
    "crossword.display()\n",
    "words1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1min 20s, sys: 2.02 ms, total: 1min 20s\n",
      "Wall time: 1min 20s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'GAC needs 64617645 consistency-checks'"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time _, _, checks = ACSolver(crossword).GAC(arc_heuristic=no_heuristic)\n",
    "f'GAC needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.19 s, sys: 0 ns, total: 1.19 s\n",
      "Wall time: 1.19 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'GAC with SAT UP arc heuristic needs 908015 consistency-checks'"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "crossword = Crossword(crossword1, words1)\n",
    "%time _, _, checks = ACSolver(crossword).GAC(arc_heuristic=sat_up)\n",
    "f'GAC with SAT UP arc heuristic needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[B] [U] [S] [*] [*] \n",
      "[U] [*] [E] [*] [*] \n",
      "[Y] [E] [A] [R] [*] \n",
      "[S] [*] [R] [*] [*] \n",
      "[*] [*] [C] [A] [R] \n",
      "[*] [*] [H] [*] [*] \n"
     ]
    }
   ],
   "source": [
    "crossword.display(ACSolver(crossword).domain_splitting())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "### Kakuro"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Easy Kakuro"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*]\t10\\\t13\\\t[*]\t\n",
      "\\3\t[_]\t[_]\t13\\\t\n",
      "\\12\t[_]\t[_]\t[_]\t\n",
      "\\21\t[_]\t[_]\t[_]\t\n"
     ]
    }
   ],
   "source": [
    "kakuro = Kakuro(kakuro2)\n",
    "kakuro.display()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 17.8 ms, sys: 171 µs, total: 18 ms\n",
      "Wall time: 16.4 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'GAC needs 2752 consistency-checks'"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time _, _, checks = ACSolver(kakuro).GAC(arc_heuristic=no_heuristic)\n",
    "f'GAC needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 8.55 ms, sys: 0 ns, total: 8.55 ms\n",
      "Wall time: 8.39 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'GAC with SAT UP arc heuristic needs 1765 consistency-checks'"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kakuro = Kakuro(kakuro2)\n",
    "%time _, _, checks = ACSolver(kakuro).GAC(arc_heuristic=sat_up)\n",
    "f'GAC with SAT UP arc heuristic needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*]\t10\\\t13\\\t[*]\t\n",
      "\\3\t[1]\t[2]\t13\\\t\n",
      "\\12\t[5]\t[3]\t[4]\t\n",
      "\\21\t[4]\t[8]\t[9]\t\n"
     ]
    }
   ],
   "source": [
    "kakuro.display(ACSolver(kakuro).domain_splitting())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "#### Medium Kakuro"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*]\t17\\\t28\\\t[*]\t42\\\t22\\\t\n",
      "\\9\t[_]\t[_]\t31\\14\t[_]\t[_]\t\n",
      "\\20\t[_]\t[_]\t[_]\t[_]\t[_]\t\n",
      "[*]\t\\30\t[_]\t[_]\t[_]\t[_]\t\n",
      "[*]\t22\\24\t[_]\t[_]\t[_]\t[*]\t\n",
      "\\25\t[_]\t[_]\t[_]\t[_]\t11\\\t\n",
      "\\20\t[_]\t[_]\t[_]\t[_]\t[_]\t\n",
      "\\14\t[_]\t[_]\t\\17\t[_]\t[_]\t\n"
     ]
    }
   ],
   "source": [
    "kakuro = Kakuro(kakuro3)\n",
    "kakuro.display()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.96 s, sys: 0 ns, total: 1.96 s\n",
      "Wall time: 1.96 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'GAC needs 1290179 consistency-checks'"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time _, _, checks = ACSolver(kakuro).GAC(arc_heuristic=no_heuristic)\n",
    "f'GAC needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 225 ms, sys: 0 ns, total: 225 ms\n",
      "Wall time: 223 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'GAC with SAT UP arc heuristic needs 148780 consistency-checks'"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kakuro = Kakuro(kakuro3)\n",
    "%time _, _, checks = ACSolver(kakuro).GAC(arc_heuristic=sat_up)\n",
    "f'GAC with SAT UP arc heuristic needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*]\t17\\\t28\\\t[*]\t42\\\t22\\\t\n",
      "\\9\t[8]\t[1]\t31\\14\t[5]\t[9]\t\n",
      "\\20\t[9]\t[2]\t[1]\t[3]\t[5]\t\n",
      "[*]\t\\30\t[6]\t[9]\t[7]\t[8]\t\n",
      "[*]\t22\\24\t[7]\t[8]\t[9]\t[*]\t\n",
      "\\25\t[8]\t[4]\t[7]\t[6]\t11\\\t\n",
      "\\20\t[5]\t[3]\t[6]\t[4]\t[2]\t\n",
      "\\14\t[9]\t[5]\t\\17\t[8]\t[9]\t\n"
     ]
    }
   ],
   "source": [
    "kakuro.display(ACSolver(kakuro).domain_splitting())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "#### Harder Kakuro"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*]\t[*]\t[*]\t[*]\t[*]\t4\\\t24\\\t11\\\t[*]\t[*]\t[*]\t11\\\t17\\\t[*]\t[*]\t\n",
      "[*]\t[*]\t[*]\t17\\\t11\\12\t[_]\t[_]\t[_]\t[*]\t[*]\t24\\10\t[_]\t[_]\t11\\\t[*]\t\n",
      "[*]\t4\\\t16\\26\t[_]\t[_]\t[_]\t[_]\t[_]\t[*]\t\\20\t[_]\t[_]\t[_]\t[_]\t16\\\t\n",
      "\\20\t[_]\t[_]\t[_]\t[_]\t24\\13\t[_]\t[_]\t16\\\t\\12\t[_]\t[_]\t23\\10\t[_]\t[_]\t\n",
      "\\10\t[_]\t[_]\t24\\12\t[_]\t[_]\t16\\5\t[_]\t[_]\t16\\30\t[_]\t[_]\t[_]\t[_]\t[_]\t\n",
      "[*]\t[*]\t3\\26\t[_]\t[_]\t[_]\t[_]\t\\12\t[_]\t[_]\t4\\\t16\\14\t[_]\t[_]\t[*]\t\n",
      "[*]\t\\8\t[_]\t[_]\t\\15\t[_]\t[_]\t34\\26\t[_]\t[_]\t[_]\t[_]\t[_]\t[*]\t[*]\t\n",
      "[*]\t\\11\t[_]\t[_]\t3\\\t17\\\t\\14\t[_]\t[_]\t\\8\t[_]\t[_]\t7\\\t17\\\t[*]\t\n",
      "[*]\t[*]\t[*]\t23\\10\t[_]\t[_]\t3\\9\t[_]\t[_]\t4\\\t23\\\t\\13\t[_]\t[_]\t[*]\t\n",
      "[*]\t[*]\t10\\26\t[_]\t[_]\t[_]\t[_]\t[_]\t\\7\t[_]\t[_]\t30\\9\t[_]\t[_]\t[*]\t\n",
      "[*]\t17\\11\t[_]\t[_]\t11\\\t24\\8\t[_]\t[_]\t11\\21\t[_]\t[_]\t[_]\t[_]\t16\\\t17\\\t\n",
      "\\29\t[_]\t[_]\t[_]\t[_]\t[_]\t\\7\t[_]\t[_]\t23\\14\t[_]\t[_]\t3\\17\t[_]\t[_]\t\n",
      "\\10\t[_]\t[_]\t3\\10\t[_]\t[_]\t[*]\t\\8\t[_]\t[_]\t4\\25\t[_]\t[_]\t[_]\t[_]\t\n",
      "[*]\t\\16\t[_]\t[_]\t[_]\t[_]\t[*]\t\\23\t[_]\t[_]\t[_]\t[_]\t[_]\t[*]\t[*]\t\n",
      "[*]\t[*]\t\\6\t[_]\t[_]\t[*]\t[*]\t\\15\t[_]\t[_]\t[_]\t[*]\t[*]\t[*]\t[*]\t\n"
     ]
    }
   ],
   "source": [
    "kakuro = Kakuro(kakuro4)\n",
    "kakuro.display()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 76.5 ms, sys: 847 µs, total: 77.4 ms\n",
      "Wall time: 77 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'GAC needs 46633 consistency-checks'"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time _, _, checks = ACSolver(kakuro).GAC()\n",
    "f'GAC needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 64.6 ms, sys: 0 ns, total: 64.6 ms\n",
      "Wall time: 63.6 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'GAC with SAT UP arc heuristic needs 36828 consistency-checks'"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kakuro = Kakuro(kakuro4)\n",
    "%time _, _, checks = ACSolver(kakuro).GAC(arc_heuristic=sat_up)\n",
    "f'GAC with SAT UP arc heuristic needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[*]\t[*]\t[*]\t[*]\t[*]\t4\\\t24\\\t11\\\t[*]\t[*]\t[*]\t11\\\t17\\\t[*]\t[*]\t\n",
      "[*]\t[*]\t[*]\t17\\\t11\\12\t[3]\t[7]\t[2]\t[*]\t[*]\t24\\10\t[2]\t[8]\t11\\\t[*]\t\n",
      "[*]\t4\\\t16\\26\t[8]\t[5]\t[1]\t[9]\t[3]\t[*]\t\\20\t[8]\t[1]\t[9]\t[2]\t16\\\t\n",
      "\\20\t[3]\t[7]\t[9]\t[1]\t24\\13\t[8]\t[5]\t16\\\t\\12\t[9]\t[3]\t23\\10\t[3]\t[7]\t\n",
      "\\10\t[1]\t[9]\t24\\12\t[3]\t[9]\t16\\5\t[1]\t[4]\t16\\30\t[7]\t[5]\t[8]\t[1]\t[9]\t\n",
      "[*]\t[*]\t3\\26\t[8]\t[2]\t[7]\t[9]\t\\12\t[3]\t[9]\t4\\\t16\\14\t[9]\t[5]\t[*]\t\n",
      "[*]\t\\8\t[1]\t[7]\t\\15\t[8]\t[7]\t34\\26\t[1]\t[7]\t[3]\t[9]\t[6]\t[*]\t[*]\t\n",
      "[*]\t\\11\t[2]\t[9]\t3\\\t17\\\t\\14\t[8]\t[6]\t\\8\t[1]\t[7]\t7\\\t17\\\t[*]\t\n",
      "[*]\t[*]\t[*]\t23\\10\t[1]\t[9]\t3\\9\t[7]\t[2]\t4\\\t23\\\t\\13\t[4]\t[9]\t[*]\t\n",
      "[*]\t[*]\t10\\26\t[6]\t[2]\t[8]\t[1]\t[9]\t\\7\t[1]\t[6]\t30\\9\t[1]\t[8]\t[*]\t\n",
      "[*]\t17\\11\t[3]\t[8]\t11\\\t24\\8\t[2]\t[6]\t11\\21\t[3]\t[9]\t[7]\t[2]\t16\\\t17\\\t\n",
      "\\29\t[8]\t[2]\t[9]\t[3]\t[7]\t\\7\t[4]\t[3]\t23\\14\t[8]\t[6]\t3\\17\t[9]\t[8]\t\n",
      "\\10\t[9]\t[1]\t3\\10\t[2]\t[8]\t[*]\t\\8\t[2]\t[6]\t4\\25\t[8]\t[1]\t[7]\t[9]\t\n",
      "[*]\t\\16\t[4]\t[2]\t[1]\t[9]\t[*]\t\\23\t[1]\t[8]\t[3]\t[9]\t[2]\t[*]\t[*]\t\n",
      "[*]\t[*]\t\\6\t[1]\t[5]\t[*]\t[*]\t\\15\t[5]\t[9]\t[1]\t[*]\t[*]\t[*]\t[*]\t\n"
     ]
    }
   ],
   "source": [
    "kakuro.display(ACSolver(kakuro).domain_splitting())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "### Cryptarithmetic Puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{@{}r@{}}\n",
    "     S E N D \\\\\n",
    "{} + M O R E \\\\\n",
    "   \\hline\n",
    "   M O N E Y\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [],
   "source": [
    "cryptarithmetic = NaryCSP(\n",
    "    {'S': set(range(1, 10)), 'M': set(range(1, 10)),\n",
    "     'E': set(range(0, 10)), 'N': set(range(0, 10)), 'D': set(range(0, 10)),\n",
    "     'O': set(range(0, 10)), 'R': set(range(0, 10)), 'Y': set(range(0, 10)),\n",
    "     'C1': set(range(0, 2)), 'C2': set(range(0, 2)), 'C3': set(range(0, 2)),\n",
    "     'C4': set(range(0, 2))},\n",
    "    [Constraint(('S', 'E', 'N', 'D', 'M', 'O', 'R', 'Y'), all_diff),\n",
    "     Constraint(('D', 'E', 'Y', 'C1'), lambda d, e, y, c1: d + e == y + 10 * c1),\n",
    "     Constraint(('N', 'R', 'E', 'C1', 'C2'), lambda n, r, e, c1, c2: c1 + n + r == e + 10 * c2),\n",
    "     Constraint(('E', 'O', 'N', 'C2', 'C3'), lambda e, o, n, c2, c3: c2 + e + o == n + 10 * c3),\n",
    "     Constraint(('S', 'M', 'O', 'C3', 'C4'), lambda s, m, o, c3, c4: c3 + s + m == o + 10 * c4),\n",
    "     Constraint(('M', 'C4'), eq)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 21.7 s, sys: 0 ns, total: 21.7 s\n",
      "Wall time: 21.7 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'GAC needs 14080592 consistency-checks'"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time _, _, checks = ACSolver(cryptarithmetic).GAC(arc_heuristic=no_heuristic)\n",
    "f'GAC needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 939 ms, sys: 0 ns, total: 939 ms\n",
      "Wall time: 938 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'GAC with SAT UP arc heuristic needs 573120 consistency-checks'"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time _, _, checks = ACSolver(cryptarithmetic).GAC(arc_heuristic=sat_up)\n",
    "f'GAC with SAT UP arc heuristic needs {checks} consistency-checks'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "pycharm": {}
   },
   "outputs": [
    {
     "data": {
      "text/latex": [
       "\\begin{array}{@{}r@{}} 9567 \\\\ + 1085 \\\\ \\hline 10652 \\end{array}"
      ],
      "text/plain": [
       "<IPython.core.display.Latex object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "assignment = ACSolver(cryptarithmetic).domain_splitting()\n",
    "\n",
    "from IPython.display import Latex\n",
    "display(Latex(r'\\begin{array}{@{}r@{}} ' + '{}{}{}{}'.format(assignment['S'], assignment['E'], assignment['N'], assignment['D']) + r' \\\\ + ' + \n",
    "              '{}{}{}{}'.format(assignment['M'], assignment['O'], assignment['R'], assignment['E']) + r' \\\\ \\hline ' + \n",
    "              '{}{}{}{}{}'.format(assignment['M'], assignment['O'], assignment['N'], assignment['E'], assignment['Y']) + ' \\end{array}'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {}
   },
   "source": [
    "## References\n",
    "\n",
    "<a name=\"cite-van2002domain\"/><sup>[[1]](#ref-1) </sup>Van Dongen, Marc RC. 2002. _Domain-heuristics for arc-consistency algorithms_.\n",
    "\n",
    "<a name=\"cite-van2000improving\"/><sup>[[2]](#ref-2) </sup>Van Dongen, MRC and Bowen, JA. 2000. _Improving arc-consistency algorithms with double-support checks_.\n",
    "\n",
    "<a name=\"cite-wallace1992ordering\"/><sup>[[3]](#ref-3) </sup>Wallace, Richard J and Freuder, Eugene Charles. 1992. _Ordering heuristics for arc consistency algorithms_."
   ]
  }
 ],
 "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.7.5rc1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}