{
"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.
\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.
\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 [[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 [[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).
\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 [[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.
\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.
\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": [
""
]
},
"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",
"[[1]](#ref-1) Van Dongen, Marc RC. 2002. _Domain-heuristics for arc-consistency algorithms_.\n",
"\n",
"[[2]](#ref-2) Van Dongen, MRC and Bowen, JA. 2000. _Improving arc-consistency algorithms with double-support checks_.\n",
"\n",
"[[3]](#ref-3) 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
}