eightqueensrevisited.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Constraint Satisfaction\n",
    "## Eight Queens Revisited\n",
    "### Introduction\n",
    "You are already familiar with the eight queens problem, now let's look at how we can solve it using *constraint satisfaction*.\n",
    "\n",
    "### Constraint Satisfaction\n",
    "We have already been thinking of the eight queens problem as trying to assign values to variables. In doing local search we moved pieces at random and checked whether we had improved the solution. Now, we will start with an empty board (or optionally one that is partially full), and then we will try placing pieces one by one in valid spaces. This is probably similar to how you would solve the problem by hand.\n",
    "\n",
    "The key part, and the essence of the technique, is that for each variable (column) we keep track of its *domain*, its list of possible values (rows). If we decide to place a piece in the second column, we must update the domain of every other column to indicate which values are still permitted. If at some point we have no possible valid options for a column, we must backtrack and try another option. This is the combination of depth first search and the propagation of constraints.\n",
    "\n",
    "### Eight Queens Code (Again)\n",
    "This time we'll need to interact with the state at a deeper level, modifying the individual components, not just treating each state as a black box. The class below is a *partial* eight queens state because it can have any number of its columns allocated, while keeping track of the values that are still possible in the other columns.\n",
    "\n",
    "Particularly take care when reading the `set_value` method, as this encapsulates the mechanics of the problem and propagates the constraints."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import copy\n",
    "\n",
    "class PartialEightQueensState:\n",
    "    def __init__(self, n=8):\n",
    "        self.n = n\n",
    "\n",
    "        # a list of possible values for each column\n",
    "        self.possible_values = [[i for i in range(0, self.n)] for _ in range(0, self.n)]\n",
    "        self.final_values = [-1] * self.n\n",
    "\n",
    "    def is_goal(self):\n",
    "        \"\"\"This partial state is a goal state if every column has a final value\"\"\"\n",
    "        return all(value != -1 for value in self.final_values)\n",
    "\n",
    "    def is_invalid(self):\n",
    "        \"\"\"This partial state is invalid if any column has no possible values\"\"\"\n",
    "        return any(len(values) == 0 for values in self.possible_values)\n",
    "\n",
    "    def get_possible_values(self, column):\n",
    "        return self.possible_values[column].copy()\n",
    "\n",
    "    def get_final_state(self):\n",
    "        if self.is_goal():\n",
    "            return self.final_values\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "    def get_singleton_columns(self):\n",
    "        \"\"\"Returns the columns which have no final value but exactly 1 possible value\"\"\"\n",
    "        return [index for index, values in enumerate(self.possible_values)\n",
    "                if len(values) == 1 and self.final_values[index] == -1]\n",
    "\n",
    "    def set_value(self, column, row):\n",
    "        \"\"\"Returns a new state with this column set to this row, and the change propagated to other domains\"\"\"\n",
    "        if row not in self.possible_values[column]:\n",
    "            raise ValueError(f\"{row} is not a valid choice for column {column}\")\n",
    "\n",
    "        # create a deep copy: the method returns a new state, does not modify the existing one\n",
    "        state = copy.deepcopy(self)\n",
    "\n",
    "        # update this column\n",
    "        state.possible_values[column] = [row]\n",
    "        state.final_values[column] = row\n",
    "\n",
    "        # now update all other columns possible values\n",
    "        # start with columns to the left\n",
    "        for update_col in range(0, column):\n",
    "            # remove same row\n",
    "            if row in state.possible_values[update_col]:\n",
    "                state.possible_values[update_col].remove(row)\n",
    "\n",
    "            # remove upper diagonal\n",
    "            upper_diag = row + (column - update_col)\n",
    "            if upper_diag in state.possible_values[update_col]:\n",
    "                state.possible_values[update_col].remove(upper_diag)\n",
    "\n",
    "            # lower diagonal\n",
    "            lower_diag = row - (column - update_col)\n",
    "            if lower_diag in state.possible_values[update_col]:\n",
    "                state.possible_values[update_col].remove(lower_diag)\n",
    "\n",
    "        # now update columns to the right\n",
    "        for update_col in range(column + 1, state.n):\n",
    "            # remove same row\n",
    "            if row in state.possible_values[update_col]:\n",
    "                state.possible_values[update_col].remove(row)\n",
    "\n",
    "            # remove upper diagonal\n",
    "            upper_diag = row + (update_col - column)\n",
    "            if upper_diag in state.possible_values[update_col]:\n",
    "                state.possible_values[update_col].remove(upper_diag)\n",
    "\n",
    "            # lower diagonal\n",
    "            lower_diag = row - (update_col - column)\n",
    "            if lower_diag in state.possible_values[update_col]:\n",
    "                state.possible_values[update_col].remove(lower_diag)\n",
    "\n",
    "        # if any other columns with no final value only have 1 possible value, make them final\n",
    "        singleton_columns = state.get_singleton_columns()\n",
    "        while len(singleton_columns) > 0:\n",
    "            col = singleton_columns[0]\n",
    "            state = state.set_value(col, state.possible_values[col][0])\n",
    "            singleton_columns = state.get_singleton_columns()\n",
    "\n",
    "        return state"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Depth First Search with Constraint Propagation\n",
    "Now finding a solution is a simple matter of picking a column to set, picking a value to set to that column, finding the resulting state with constraint propagation, and then searching all possible options until we find a solution.\n",
    "\n",
    "Here is the pseudocode from Russell and Norvig (p. 215):\n",
    "\n",
    "<br>\n",
    "<figure>\n",
    "<img src=\"resources/constraint_propagation.png\", width=600>\n",
    "</figure>\n",
    "<br>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 4, 6, 0, 3, 1, 7, 5]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "def pick_next_column(partial_state):\n",
    "    \"\"\"\n",
    "    Used in depth first search, currently chooses a random \n",
    "    column that has more than one possible value\n",
    "    \"\"\"\n",
    "    col_indices = [index for index, values in enumerate(partial_state.possible_values) if len(values) > 1]\n",
    "    return random.choice(col_indices)\n",
    "\n",
    "\n",
    "def order_values(partial_state, col_index):\n",
    "    \"\"\"\n",
    "    Get values for a particular column in the \n",
    "    order we should try them in. Currently random.\n",
    "    \"\"\"\n",
    "    values = partial_state.get_possible_values(col_index)\n",
    "    random.shuffle(values)\n",
    "    return values\n",
    "\n",
    "\n",
    "def depth_first_search(partial_state=PartialEightQueensState()):\n",
    "    \"\"\"\n",
    "    This will do a depth first search on partial states, trying \n",
    "    each possible value for a single column.\n",
    "\n",
    "    Notice that we do not need to try every column: if we try \n",
    "    every possible value for a column and can't find a\n",
    "    solution, then there is no possible value for this column, \n",
    "    so there is no solution.\n",
    "    \"\"\"\n",
    "    col_index = pick_next_column(partial_state)\n",
    "    values = order_values(partial_state, col_index)\n",
    "\n",
    "    for value in values:\n",
    "        new_state = partial_state.set_value(col_index, value)\n",
    "        if new_state.is_goal():\n",
    "            return new_state\n",
    "        if not new_state.is_invalid():\n",
    "            deep_state = depth_first_search(new_state)\n",
    "            if deep_state is not None and deep_state.is_goal():\n",
    "                return deep_state\n",
    "    return None\n",
    "\n",
    "\n",
    "partial_state = PartialEightQueensState(n=8)\n",
    "goal = depth_first_search(partial_state).get_final_state()\n",
    "print(goal)1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the most basic form of the technique, but it is quite powerful. It can easily handle quite large board sizes, much larger than we could do using local search. Try some out by changing the value of `n` above.\n",
    "\n",
    "Now consider a few ways to improve this code:\n",
    "* Add some metrics to calculate how many partial states are generated to better compare with other methods\n",
    "* Modify the code so that you can pass an initial configuration into the `PartialEightQueensState` constructor, which should then run these values through `set_value` to update possible values\n",
    " * Can you find a starting state which has no possible solution, but does not start with two queens attacking each other?\n",
    "* Change how the algorithm picks the next column. It can be more efficient to pick the column which currently has the fewest options. Compare your metric from before.\n",
    "* Change how the algorithm picks which order to try the values it assigns to a column. One idea might be to prioritise values which *least constrain* other columns, but watch out this doesn't end up adding more complexity than it saves.\n",
    " * One way to check this would be to try timing your code. You can use `time.time()` or the [`timeit` module](https://docs.python.org/3.8/library/timeit.html)."
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}