Local_Search/n_queens.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving the n-Queens Problem using Local Search\n",
    "\n",
    "Student Name: [Add your name]\n",
    "\n",
    "I have used the following AI tools: [list tools]\n",
    "\n",
    "I understand that my submission needs to be my own work: [your initials]\n",
    "\n",
    "## Instructions\n",
    "\n",
    "Total Points: Undergrads 100 + 5 bonus / Graduate students 110\n",
    "\n",
    "Complete this notebook. Use the provided notebook cells and insert additional code and markdown cells as needed. Submit the completely rendered notebook as a HTML file. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The n-Queens Problem\n",
    "\n",
    "* __Goal:__ Find an arrangement of $n$ queens on a $n \\times n$ chess board so that no queen is on the same row, column or diagonal as any other queen.\n",
    "\n",
    "* __State space:__ An arrangement of the queens on the board. We restrict the state space to arrangements where there is only a single queen per column. We represent a state as an integer vector $\\mathbf{q} = \\{q_1, q_2, \\dots, q_n\\}$, each number representing the row positions of the queens from left to right. We will call a state a \"board.\"\n",
    "\n",
    "* __Objective function:__ The number of pairwise conflicts (i.e., two queens in the same row/column/diagonal).\n",
    "The optimization problem is to find the optimal arrangement $\\mathbf{q}^*$ of $n$ queens on the board can be written as:\n",
    "\n",
    "  > minimize: $\\mathrm{conflicts}(\\mathbf{q})$\n",
    "  >\n",
    "  > subject to: $\\mathbf{q} \\ \\text{contains only one queen per column}$\n",
    "\n",
    "  Note: the constraint (subject to) is enforced by the definition of the state space.\n",
    "\n",
    "* __Local improvement move:__ Move one queen to a different row in its column.\n",
    "\n",
    "* __Termination:__ For this problem there is always an arrangement $\\mathbf{q}^*$ with $\\mathrm{conflicts}(\\mathbf{q}^*) = 0$, however, the local improvement moves might end up in a local minimum. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Helper functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from matplotlib import colors\n",
    "\n",
    "np.random.seed(1234)\n",
    "\n",
    "\n",
    "def random_board(n):\n",
    "    \"\"\"Creates a random board of size n x n. Note that only a single queen is placed in each column!\"\"\"\n",
    "    \n",
    "    return(np.random.randint(0,n, size = n))\n",
    "\n",
    "def comb2(n): return n*(n-1)//2 # this is n choose 2 equivalent to math.comb(n, 2); // is int division\n",
    "\n",
    "def conflicts(board):\n",
    "    \"\"\"Calculate the number of conflicts, i.e., the objective function.\"\"\"\n",
    "\n",
    "    n = len(board)\n",
    "    \n",
    "    horizontal_cnt = [0] * n\n",
    "    diagonal1_cnt = [0] * 2 * n\n",
    "    diagonal2_cnt = [0] * 2 * n\n",
    "    \n",
    "    for i in range(n):\n",
    "        horizontal_cnt[board[i]] += 1\n",
    "        diagonal1_cnt[i + board[i]] += 1\n",
    "        diagonal2_cnt[i - board[i] + n] += 1\n",
    "    \n",
    "    return sum(map(comb2, horizontal_cnt + diagonal1_cnt + diagonal2_cnt))\n",
    "\n",
    "# decrease the font size to fit larger boards\n",
    "def show_board(board, cols = ['white', 'gray'], fontsize = 48):  \n",
    "    \"\"\"display the board\"\"\"\n",
    "    \n",
    "    n = len(board)\n",
    "    \n",
    "    # create chess board display\n",
    "    display = np.zeros([n,n])\n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            if (((i+j) % 2) != 0): \n",
    "                display[i,j] = 1\n",
    "    \n",
    "    cmap = colors.ListedColormap(cols)\n",
    "    fig, ax = plt.subplots()\n",
    "    ax.imshow(display, cmap = cmap, \n",
    "              norm = colors.BoundaryNorm(range(len(cols)+1), cmap.N))\n",
    "    ax.set_xticks([])\n",
    "    ax.set_yticks([])\n",
    "    \n",
    "    # place queens. Note: Unicode u265B is a black queen\n",
    "    for j in range(n):\n",
    "        plt.text(j, board[j], u\"\\u265B\", fontsize = fontsize, \n",
    "                 horizontalalignment = 'center',\n",
    "                 verticalalignment = 'center')\n",
    "    \n",
    "    print(f\"Board with {conflicts(board)} conflicts.\")\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Create a board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Board with 4 conflicts.\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAGFCAYAAAASI+9IAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAiy0lEQVR4nO3df2xUVf7/8VeH0lagBYaiCAgNUEGC8UeUXUQI3Y+OiySAbF2KWdGsbFiJ8cd/SDbaBhEkkV2akJDIz9WgpJttUDbiD2hBgWCJihZNtVJKSysVCgXEFlrm+0e/c7h35t7+gE7n1/Px19xz71zO1Dqvvs+599wkv9/vFwAAkjyR7gAAIHoQCgAAg1AAABiEAgDAIBQAAAahAAAwCAUAgJHclYOuXr2quro6paenKykpKdx9AgD0ML/frwsXLmj48OHyeNzrgS6FQl1dnW677bYe6xwAIDJqamo0cuRI1/1dCoX09HRzsoyMjJ7pGTq0cuXKSHch4bz88suR7kJC4Xe8d7W0tOif//yn+T5306VQCAwZZWRkEAq9JC0tLdJdSDj8bvcufscjo7MpACaaAQAGoQAAMAgFAIBBKAAADEIBAGAQCgAAg1AAABiEAgDAIBQAAAahAAAwCAUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAABqEAADAIBQCAQSgAAAxCAQBgEAoAAINQAAAYhAIAwCAUAAAGoQAAMAgFAIBBKAAADEIBAGAQCgAAg1AAABiEAgDAIBQAAAahAAAwCAUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAABqEAADAIBQCAQSgAAAxCAQBgEAoAAINQAAAYhAIAwCAUAAAGoQAAMAgFAIBBKAAADEIBAGAQCgAAg1AAABiEAgDAIBQAAAahAAAwCAUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAABqEAADAIBQCAQSgAAAxCAQBgEAoAAINQAAAYhAIAwCAUAAAGoQAAMAgFAIBBKAAADEIBAGAQCgAAg1AAABiEAgDAIBQAAAahAAAwCAUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAARpLf7/d3dtD58+c1cOBALV26VGlpab3Rr4T36quvRroLCaegoCDSXUgo/I73rsD3eFNTkzIyMlyPo1IAABiEAgDAIBQAAAahAAAwCAUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAABqEAADAIBQCAQSgAAAxCAQBgEAoAAINQAAAYhAIAdEFtba2efvppjRo1SmPHjtVzzz2nM2fORLpbPS450h0AgGjX2NioBx54QDU1NaZt3bp12rt3r8rKyuLqMcWEAoCEtnv3bn300Udqa2uTz+fTI488EnLMhg0bbIEQUF5erqKiIj355JO29paWFm3fvl2HDx9WZmam8vLydPvtt4ftM/QkQgFAwlq0aJE2btxottesWaOnnnpKW7ZssR1XUVHheo7gfU1NTZoxY4a+/vpr0/baa69pw4YNWrhwYY/0O5yYUwCQkD744ANbIARs3bpVxcXFtjafz+d6nunTp9u28/PzbYEgSVeuXNHixYt1+vTp6+9wLyEUACSkTz75xHXfnj17bNvz58/X2rVrNWDAANM2cOBAFRYWhgTGp59+6njO5uZm7du37wZ63DsYPgKQkDoa47/11ltD2p5//nn5/X69+OKLkqRNmzZp3rx5Icd5vV7X844ePbr7He1lVAoAEtITTzyh4cOHh7SPGjVKixcvdnzPxYsXzetLly45HvPCCy84tk+dOlX33nvvdfS0dxEKABKS1+vV7t27NXfuXN1yyy2mvbi4WEOGDHF8z/nz581ra0BYzZs3T88884zZTk5OVm5uroqLi5WUlNRDvQ8fQgFA3KqpqdGCBQs0ePBgeb1eLVy4UPX19Wb/hAkTVFxcrLfeesu0/fjjj67n60ooSNJNN91kXh86dEhFRUUaOnSoaTtw4IB8Pp+8Xq/GjRunV155RS0tLd3+fOHAnAKAuBS44ay2tta0vf3229q/f7+OHDlimzTOzMw0r0tKSjR//nzHc164cMG87igUSkpKzOs77rjDtu/w4cPKycnR5cuXJUlnz57V8uXLdeTIEe3YsaOLny58qBQAxKVNmzbZAiHg2LFj2rZtm63NOlxUWlrqes6uVAoNDQ06evSoJGnYsGG2qkGS3njjDRMIVu+//37IpayRQCgAiEs//fRTl/dZQ6GiosI2xGTVlUrBGipjxowJ2V9ZWenar2PHjrnu6y2EAoC4NGXKFNd999xzj2178ODB8niufR1ah3+srJXCr7/+6niM9b1OoTB58mTH93k8Hk2dOtW1z72FUAAQl/Ly8nT//feHtPt8PuXm5traPB6PBg0aZLbdhpC6Uil0Fgqvv/66Jk6cGNK+YsUK21VQkUIoAIhLKSkp+uyzz7Ru3TozcTx58mTt2rVLycmh19gETzY76WxOob6+3rYWklMoDBkyRCNGjJAkZWdna8WKFSorK9PSpUu7+MnCi1AAELdSU1O1ZMkSbdu2TcOGDVNZWZm+//57x2Ot8wqVlZWOk9SdVQrBYeIUCgcOHDBLbLz00ktatmyZ7rvvvq59oF5AKACIex6PR3PmzJHf79fKlSsdjwm+YS34C76trc12F7NTKASvmeQUCvn5+ZLab2p7/PHHu9T/3kQoAEgIjz32mCTpvffeU1VVVcj+4FAInlewDh1JnVcKaWlpIctoWKuEhx56yDZkFS0IBQAJIScnRxkZGWptbdXq1atD9ndWKViHjqTQUDhx4oTtktKsrKyQZS0CVYIkLViwoFv97y2EAoCEkJKSolmzZkmSNm/erJ9//tm2P/iv9qqqKlVXV5vtziqFzuYTrFVCWlqa5s6d2/0P0QsIBQAJIzCE1NLSojfffNO2z2kRPOsQUnCl0NzcrLa2NrPdWShYq4RZs2YpIyOjW33vLYQCgIQxc+ZMpaamSpLWr1+vs2fPmn1OoWD9og+uFCT7DWwdhYK1SpDa76GIVoQCgIQxYMAAPfzww5Lah38KCwvNvu5WCoFzSO3LU5w4ccK2zxoKBQUF5nV6eroZxopGhAKAhGIdyy8sLDR/7TtdCVRdXW2uVHKqFAKh4HSzWyAUDh48qI8//tj27wcvkhdNCAUACWX27NlmnaPGxkatX79eknOlIF37wr/eULDOJUjRe9VRAKEAIKEMHTpUDz74oNles2aNWlpaOg2FjoaPgkPh5ptvVv/+/UOqhMzMTDN8Fa0IBQAJJ3AVkiTV1dVp8+bNSklJsT14JyAwr+BWKfzwww+qq6uztbtVCbm5uY7rLkUTQgFAwgm+R2D16tVqa2tzrBZqa2tVWVnpWim4DR0FVwlS9A8dSYQCgASUlZVle6ZCVVWV3n33XddlJ0pKSlwrheD1jqT2UAiuEkaOHKlp06bdWMd7AaEAICH5fD7b9qpVq+T1eh2PLSkpca0UnJ69cOrUqZAq4dFHHw1Z9iIaRffgFgCESVpamm376NGjro/hLC0tVXZ2dkj7F198oYaGhpD2oqKikLZovgzVilAAgP+vsbHRsb2+vt62bHbAhx9+6Hj8uXPnerJbvYrhIwDogqamppA2txCJZVQKABJeQUGBuaGtp1VUVOidd94Jy7nDgVAAkPCWLVsWtvsHdu7cGVOhwPARAMCgUgCQ8Pr27RvpLkQNKgUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMDgklQACa+8vFx9+vQJy7lLS0v17LPPhuXc4UAoAEh448ePD9sdzZWVlWE5b7gwfAQAMKgUACS8rKyssJ27ubk5bOcOB0IBQMI7efJkpLsQNQgFAAkpPz8/5DnKYE4BAGBBKAAADEIBAGAQCgAAg1AAABiEAgDAIBQAAAahAAAwCAUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAABqEAADAIBQCAQSgAAAxCAQBgEAoAAINQAAAYhAIAwCAUAAAGoQAAMAgFAICR3J2DX375ZWVkZISrL7AoKCiIdBcSzquvvhrpLiQUfsd7V3Nzc5eOo1IAABiEAgDAIBQAAAahAAAwCAUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAABqEAADAIBQCAQSgAAAxCAQBgEAoAAINQAGJQbW2tnn76aY0aNUpjx47Vc889pzNnzkS6W4gD3XryGoDIa2xs1AMPPKCamhrTtm7dOu3du1dlZWVKS0uLYO8Q6wgFIIrs3r1bH330kdra2uTz+fTII4+EHLNhwwZbIASUl5erqKhITz75pK29paVF27dv1+HDh5WZmam8vDzdfvvtYfsMiG2EAhAlFi1apI0bN5rtNWvW6KmnntKWLVtsx1VUVLieI3hfU1OTZsyYoa+//tq0vfbaa9qwYYMWLlzYI/1GfGFOAYgCH3zwgS0QArZu3ari4mJbm8/ncz3P9OnTbdv5+fm2QJCkK1euaPHixTp9+vT1dxhxi1AAosAnn3zium/Pnj227fnz52vt2rUaMGCAaRs4cKAKCwtDAuPTTz91PGdzc7P27dt3Az1GvGL4CIgCHY3x33rrrSFtzz//vPx+v1588UVJ0qZNmzRv3ryQ47xer+t5R48e3f2OIu5RKQBR4IknntDw4cND2keNGqXFixc7vufixYvm9aVLlxyPeeGFFxzbp06dqnvvvfc6eop4RygAUcDr9Wr37t2aO3eubrnlFtNeXFysIUOGOL7n/Pnz5rU1IKzmzZunZ555xmwnJycrNzdXxcXFSkpK6qHeI54QCkAvqamp0YIFCzR48GB5vV4tXLhQ9fX1Zv+ECRNUXFyst956y7T9+OOPrufrSihI0k033WReHzp0SEVFRRo6dKhpO3DggHw+n7xer8aNG6dXXnlFLS0t3f58iA/MKQC9IHDDWW1trWl7++23tX//fh05csQ2aZyZmWlel5SUaP78+Y7nvHDhgnndUSiUlJSY13fccYdt3+HDh5WTk6PLly9Lks6ePavly5fryJEj2rFjRxc/HeIJlQLQCzZt2mQLhIBjx45p27ZttjbrcFFpaanrObtSKTQ0NOjo0aOSpGHDhtmqBkl64403TCBYvf/++yGXsiIxEApAL/jpp5+6vM8aChUVFbYhJquuVArWUBkzZkzI/srKStd+HTt2zHUf4hehAPSCKVOmuO675557bNuDBw+Wx3Ptf03r8I+VtVL49ddfHY+xvtcpFCZPnuz4Po/Ho6lTp7r2GfGLUAB6QV5enu6///6Qdp/Pp9zcXFubx+PRoEGDzLbbEFJXKoXOQuH111/XxIkTQ9pXrFhhuwoKiYNQAHpBSkqKPvvsM61bt85MHE+ePFm7du1ScnLo9R7Bk81OOptTqK+vt62F5BQKQ4YM0YgRIyRJ2dnZWrFihcrKyrR06dIufjLEG0IB6CWpqalasmSJtm3bpmHDhqmsrEzff/+947HWeYXKykrHSerOKoXgMHEKhQMHDpglNl566SUtW7ZM9913X9c+EOISoQD0Mo/Hozlz5sjv92vlypWOxwTfsBb8Bd/W1ma7i9kpFILXTHIKhfz8fEntN7U9/vjjXeo/4huhAETAY489Jkl67733VFVVFbI/OBSC5xWsQ0dS55VCWlpayDIa1irhoYcesg1ZIXERCkAE5OTkKCMjQ62trVq9enXI/s4qBevQkRQaCidOnLBdUpqVlRWyrEWgSpCkBQsWdKv/iF+EAhABKSkpmjVrliRp8+bN+vnnn237g/9qr6qqUnV1tdnurFLobD7BWiWkpaVp7ty53f8QiEuEAhAhgSGklpYWvfnmm7Z9TovgWYeQgiuF5uZmtbW1me3OQsFaJcyaNUsZGRnd6jviF6EARMjMmTOVmpoqSVq/fr3Onj1r9jmFgvWLPrhSkOw3sHUUCtYqQWq/hwIIIBSACBkwYIAefvhhSe3DP4WFhWZfdyuFwDmk9uUpTpw4YdtnDYWCggLzOj093QxjARKhAESUdSy/sLDQ/LXvdCVQdXW1uVLJqVIIhILTzW6BUDh48KA+/vhj278fvEgeEhuhAETQ7NmzzTpHjY2NWr9+vSTnSkG69oV/vaFgnUuQuOoIoQgFIIKGDh2qBx980GyvWbNGLS0tnYZCR8NHwaFw8803q3///iFVQmZmphm+AgIIBSDCAlchSVJdXZ02b96slJQU24N3AgLzCm6Vwg8//KC6ujpbu1uVkJub67juEhIboQBEWPA9AqtXr1ZbW5tjtVBbW6vKykrXSsFt6Ci4SpAYOoIzQgGIsKysLNszFaqqqvTuu++6LjtRUlLiWikEr3cktYdCcJUwcuRITZs27cY6jrhEKABRwOfz2bZXrVolr9freGxJSYlrpeD07IVTp06FVAmPPvpoyLIXgCQxoAhEgbS0NNv20aNHXR/DWVpaquzs7JD2L774Qg0NDSHtRUVFIW1chgo3hAIQpRobGx3b6+vrbctmB3z44YeOx587d64nu4U4x/AREIOamppC2txCBOgOKgUgyhQUFJgb2npaRUWF3nnnnbCcG/GBUACizLJly8J2/8DOnTsJBXSI4SMAgEGlAESZvn37RroLSGBUCgAAg1AAABiEAgDAIBQAAAahAAAwCAUAgMElqUCUKS8vV58+fcJy7tLSUj377LNhOTfiA6EARJnx48eH7Y7mysrKsJwX8YPhIwCAQaUARJmsrKywnbu5uTls50Z8IBSAKHPy5MlIdwEJjFAAokB+fn7Ic5SBSGBOAQBgEAoAAINQAAAYhAIAwCAUAAAGoQAAMAgFAIBBKAAADEIBAGAQCgAAg1AAABiEAgDAIBQAAAahAAAwCAUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAABqEAADAIBQCAQSgAAAxCAQBgJPn9fn9nB50/f14DBw7U0qVLlZaW1hv9SnivvvpqpLuQcAoKCiLdhYTC73jvCnyPNzU1KSMjw/U4KgUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAABqEAADAIBQCAQSgAAAxCAQBgEAoAAINQAAAYhAIAwCAUAAAGoQAAMJIj3YFwaWpq0p49e1RVVaU+ffpo3LhxysnJUb9+/SLdtbhUW1urf/zjH9qzZ4/69u2rmTNnqqCgQEOGDIl01wB0Q1yGwqVLl7Rx40adP3/etJWVlam6ulp/+9vf1Ldv3wj2Lv40NjbqgQceUE1NjWlbt26d9u7dq7KyMp7WB8SQmAuFY8eOqbKyUn6/X2PHjtW4ceNCjvnyyy9tgRDQ0NCg7777TnfddZetvbW1VeXl5aqrq1O/fv00adIkZWZmhu0zxJLdu3fro48+Ultbm3w+nx555JGQYzZs2GALhIDy8nIVFRXpySeftLW3tLRo+/btOnz4sDIzM5WXl6fbb789bJ8BQNfFVCjs2LFDX331ldk+ePCg7rrrLj322GO2486cOeN6jtOnT9u2m5ubtWXLFv3888+mbd++fZo9e7buvvvunul4jFq0aJE2btxottesWaOnnnpKW7ZssR1XUVHheo7gfU1NTZoxY4a+/vpr0/baa69pw4YNWrhwYY/0G8D1i5mJ5oqKClsgBBw5ckTff/+9rW3s2LGu5xk9erRtu7S01BYIknT16lXt3LlTv/766w30OLZ98MEHtkAI2Lp1q4qLi21tPp/P9TzTp0+3befn59sCQZKuXLmixYsXhwQ2gN4XM6Hw008/ue6rqqqybU+aNEl//OMflZKSYtpSU1M1c+bMkOGmY8eOOZ6ztbVV1dXVN9Dj2PbJJ5+47tuzZ49te/78+Vq7dq0GDBhg2gYOHKjCwsKQwPj0008dz9nc3Kx9+/bdQI8B9ISYGT7q6CoW65dRwO9//3tJ0q5duyRJc+bM0cSJE0OOu+mmm1zPO2jQoG72Mn50NMZ/6623hrQ9//zz8vv9evHFFyVJmzZt0rx580KO83q9rucNruIA9L6YqRTuvPNOpaenh7QPHDhQ9913n+N7Ll++bF5fuXLF8Zjf/e53ju233Xab45dfonjiiSc0fPjwkPZRo0Zp8eLFju+5ePGieX3p0iXHY1544QXH9qlTp+ree++9jp4C6EkxEwr9+vXTwoULNWHCBPXv39+0z58/3/Xeg5aWFvPaGhBWEydO1D333GO2PR6PJk6cqLy8PCUlJfVQ72OP1+vV7t27NXfuXN1yyy2mvbi42LVqs17xZQ0Iq3nz5umZZ54x28nJycrNzVVxcXFC/7yBaBFVodDU1KT//Oc/WrVqlVatWqX//ve/unDhgtk/dOhQ5eXlafbs2aatsbHR9XxdCQVJtvsWFi1apD//+c+24Dlx4oT+/e9/a9WqVVq7dq327Nmj1tbWbn++aFNTU6MFCxZo8ODB8nq9Wrhwoerr683+CRMmqLi4WG+99ZZp+/HHH13P15VQkOxDdocOHVJRUZGGDh1q2g4cOCCfzyev16tx48bplVdesf23BBA+UTOn4HTD2TfffKOamhr9/e9/V2pqqmm3VgZVVVWaNGmS4zm7GgrWiWrrl5MknTx5Ulu3blVbW5ukaxOip06d0oIFC7r46aJP4Iaz2tpa0/b2229r//79OnLkiG2exnrPRklJiebPn+94TmuAdxQKJSUl5vUdd9xh23f48GHl5OSY/15nz57V8uXLdeTIEe3YsaOLnw7A9YqaSuGrr75yvOHs7Nmz+vbbb21t1r80jx8/7nrOroTCxYsX9csvv0hqn7AOvtt5//79JhCsKioqbH9Vx5pNmzbZAiHg2LFj2rZtm63NOlxUWlrqes6uVAoNDQ06evSoJGnYsGEhE/1vvPGG43+r999/P+RSVgA9L2pC4ezZs13eZ60Uzpw5Y/sL1cr65eIWCtZQGTx4cMj+joanOupztOvoEt/gfdZQ6CgMu1IpWENlzJgxIfsrKytd++V2+TCAnhM1oTBy5EjXfcOGDbNtp6Wl2SYlg+9TCLBWCm5XH3UWCiNGjHB8X1JSkkaNGuXa52g3ZcoU133WiXep/efi8Vz7VbEO/1hZKwW3G/+s73UKhcmTJzu+z+PxaOrUqa59BtAzoiYUJk2a5HgJ5NixY0PuL/B4PLZF1tyGkLoyfGQNFKdQ+L//+7+QeQZJ+sMf/uB4f0SsyMvL0/333x/S7vP5lJuba2vzeDy2ezbchpC6Uil0Fgqvv/664/0kK1assF0FBSA8omaiOTk5WX/961/15Zdfqrq6WkePHtWIESP0l7/8xfFSxX79+um3336TdP2hcOHCBds6SU6h0K9fP6Wnp+uXX36R1+vV3XffrbFjx7pWELEiJSVFn332mTZu3Kh9+/Zp+/btmjx5snbt2uX4887MzDRDaV2pFJxCob6+3rYWklMoDBkyRCNGjNB3332n7OxsPf300/L5fK73ogDoWVFTKUjtwTB58mT96U9/0oABA3Ty5EkzCRzMOkHZ2NiopqamkGM6m1MIHnZyCoUTJ06YsewpU6Zo+vTpMR8IAampqVqyZIm2bdumYcOGqaysLGQdqQDrvEJlZaXjJHVnlUJwmDiFwoEDB8wSGy+99JKWLVtGIAC9KKpCIcDj8Wj8+PGSpM8//9zxmOAb1oKrhatXr9rmEa43FAJDJYGb2uKRx+PRnDlz5Pf7tXLlSsdjgm9YC/6Cb2trs93F7BQKwWsmOYVCfn6+pPY/EB5//PEu9R9Az4nKUJCuXb9eXl7ueJVP8KWMwaEQfLOTUyhY35OcnByyjIa1ShgzZozthrZ4E1h+/L333nOcuA8OheB5heDLiTurFNLS0kLmkKxVwkMPPcQzLYAIiNpQyMrKUmpqqq5evar9+/eH7A+uFIK/yDoLhXPnztnCZtCgQSFj6dYvPrcb5OJFTk6OMjIy1NraqtWrV4fs76xSCL4sODgUrAErtf/3Df55B6oESTF9YyAQy6I2FJKTk5WdnS2p/ca24C+d4FA4d+6czp07Z7Y7C4XgyiJ46Mj6JZacnKwJEyZ0+zPEkpSUFM2aNUuStHnz5pBnTAT/1V5VVWVbWryzSqGz+QRrlZCWlqa5c+d2/0MAuGFRGwrStSGktrY2HTx40LbPaclr6xd9cAi0trbq6tWrZruz+QRrlZCdnZ0QzxkODCG1tLTozTfftO1zWgTP+jMKDu3m5mbbneCdhYK1Spg1a5YyMjK61XcAPSOqQ2HcuHHq06ePpPY1cQKXoEqhlYJk/6J3WkDNGhQdVQrBQx3xPnQUMHPmTLPG1Pr1623Da06hYP2id1qixHoDW0ehYK0SpPZ7KABERlSHQmpqqnm05uXLl3Xo0CGzr7NKoaNQcLqE1RoKe/fuNa9TUlIS5qHyAwYM0MMPPyypffinsLDQ7OtupRA4h9S+PMWJEyds+6yhUFBQYF6np6ebYSwAvS+qQ0GSbSz/0KFD5ovdqVJoamoyf912FApON7sFQqGmpsa29s+ECRNCFsmLZ9ax/MLCQvPXvtOVQNXV1aY6c6oUAqHgdLNbIBQOHjyojz/+2Pbvd/Q0PADhFfWhMH78eHOVym+//abDhw9Lcg4F6doQUkeh4HTJZSAUgi+1vPPOO6+v4zFq9uzZZp2jxsZGrV+/XpL741ADX/jXGwrWuQSJq46ASIv6UOjfv79t4bmDBw+qtbXV9a/JQBXgdF+CW6XQv39/paSkhFQJ/fr1c7zBKp4NHTpUDz74oNles2aNWlpaOg2FjoaPgkPh5ptvVv/+/UOqhMzMTDN8BSAyoj4UJPsQ0oULF/TVV18pOTlZKSkpIccGvvDdKoXTp0+HfIG5VQkTJ040E92JJHAVkiTV1dVp8+bNSklJcVwAMPAzc6sUfvjhB9XV1dna3aqE3NxcJSdHzXJcQEKKuVCQ2h98c/XqVcdq4fz58zpz5oxrKLjNJwRXCVLiXHUULPgegdWrV6utrc2xWqitrVVlZaVrpeA2dBRcJUgMHQHRICZCYfDgwbZnKpw7d07ffvut67zC8ePHXUPBbT4huErIyMjQ6NGjb6zjMSorK8v2TIWqqiq9++67rstOlJSUuFYKwesdSe2hEFwljBw5UtOmTbuxjgO4YTERCpLMpakBn3/+ueu8QlVVleucglOlcPHixZAqITs723EJ6UTh8/ls26tWrZLX63U8tqSkxLVScHr2wqlTp0KqhEcffTShf95AtIiZAdzgseZffvnF9UEux48fdxzqOHnypOMTwb777rtO/71EE3wH99GjR10fw1laWmqWJLH64osv1NDQENJeVFQU0sZlqEB0iOlvPusdzlYXL150fPym2/N/m5ube7Rf8crtedX19fW2ZbMDPvzwQ8fjrWtUAYguMTN81F1OcwpuIYIb5/SQI7cQARC9YrJSmDFjRtjGn8+cOaNvvvkmLOeOVQUFBeaGtp5WUVGhd955JyznBtB9MRkK06ZNC9v9AxUVFYRCkGXLloVtjmXnzp2EAhBF4nb4CADQfTFZKSxfvjzSXUgoibQgIJDoqBQAAAahAAAwCAUAgEEoAAAMQgEAYBAKAAAjJi9JXbJkSdjuaD5+/Lj+97//heXcsaq8vDxsNwuWlpbq2WefDcu5AXRfTIbCkCFDwvYlxXo9ocaPHx+2O5rdFikEEBkMHwEAjJisFP71r3+F7dytra1hO3esysrKCtu5WbYciC4xGQpOT/lC+Jw8eTLSXQDQS2ImFHJycpSTkxPpbiSM/Pz8kOcoA4h/zCkAAAxCAQBgEAoAAINQAAAYhAIAwCAUAAAGoQAAMAgFAIBBKAAADEIBAGAQCgAAg1AAABiEAgDAIBQAAAahAAAwCAUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAABqEAADAIBQCAQSgAAIzkrhzk9/slSS0tLWHtDK45f/58pLuQcJqbmyPdhYTC73jvCvy8A9/nbpL8nR0hqba2VrfddlvP9AwAEDE1NTUaOXKk6/4uhcLVq1dVV1en9PR0JSUl9WgHAQDh5/f7deHCBQ0fPlwej/vMQZdCAQCQGJhoBgAYhAIAwCAUAAAGoQAAMAgFAIBBKAAADEIBAGD8P9cHJ0hljWYsAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Queens (left to right) are at rows: [3 3 2 1]\n",
      "Number of conflicts: 4\n"
     ]
    }
   ],
   "source": [
    "board = random_board(4)\n",
    "\n",
    "show_board(board)\n",
    "print(f\"Queens (left to right) are at rows: {board}\")\n",
    "print(f\"Number of conflicts: {conflicts(board)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A board $4 \\times 4$ with no conflicts:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Board with 0 conflicts.\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAGFCAYAAAASI+9IAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAjQElEQVR4nO3dW2xU1d/G8adlaEuhBVpAzhBKOTQQwACKCKH+pYoknIKhGEWjGCIxHu6QC4UgHkjkVRISEgEhGtD0okExoggtCDRIAwIFUi0t5VAQ6LnAFHp4L8gsZ8/sTVvodKad7+dq9tp7FmsMzsNvrb32RDQ2NjYKAABJkcEeAAAgdBAKAACDUAAAGIQCAMAgFAAABqEAADAIBQCA4WrORQ0NDSopKVFcXJwiIiICPSYAQCtrbGxUdXW1+vfvr8hI53qgWaFQUlKiQYMGtdrgAADBcenSJQ0cONDxfLNCIS4uznQWHx/fOiPDA3366afBHkLY+eCDD4I9hLDC3/G2VVtbq//7v/8z3+dOmhUKnimj+Ph4QqGNxMTEBHsIYYe/222Lv+PB0dQSAAvNAACDUAAAGIQCAMAgFAAABqEAADAIBQCAQSgAAAxCAQBgEAoAAINQAAAYhAIAwCAUAAAGoQAAMAgFAIBBKADt0OXLl/Xaa69p8ODBSkpK0ttvv63S0tJgDwsdQLN+TwFA6CgrK9NTTz2lS5cumbaNGzfqwIEDOnbsGL9TgEdCKAAhZN++ffr1119VX1+vtLQ0Pffcc37XbN682RIIHnl5ecrIyNArr7xiaa+trdUPP/yg3Nxc9erVS+np6RoxYkTAPgPaN0IBCBFLly7Vli1bzPH69ev16quvatu2bZbr8vPzHfvwPVdZWakZM2bor7/+Mm0ff/yxNm/erCVLlrTKuNGxsKYAhICffvrJEgge27dvV2ZmpqUtLS3NsZ/p06dbjletWmUJBEm6d++eli1bpps3bz78gNFhEQpACNi7d6/juf3791uOFy1apK+++krdunUzbd27d9eGDRv8AuP333+37dPtduvgwYOPMGJ0VEwfASHgQXP8/fr182t755131NjYqPfee0+StHXrVi1YsMDvuoSEBMd+hwwZ0vKBosOjUgBCwEsvvaT+/fv7tQ8ePFjLli2zfU9NTY15ffv2bdtr3n33Xdv2qVOn6vHHH3+IkaKjIxSAEJCQkKB9+/Zp3rx5euyxx0x7ZmamEhMTbd9TVVVlXnsHhLcFCxbojTfeMMcul0sLFy5UZmamIiIiWmn06EgIBaCNXLp0SYsXL1bPnj2VkJCgJUuW6OrVq+b8qFGjlJmZqa+//tq0/fPPP479NScUJKlLly7m9dGjR5WRkaHevXubtiNHjigtLU0JCQkaPny4PvzwQ9XW1rb486FjYE0BaAOeDWeXL182bd9++60OHz6skydPWhaNe/XqZV5nZWVp0aJFtn1WV1eb1w8KhaysLPN69OjRlnO5ublKTU3V3bt3JUnl5eVas2aNTp48qV27djXz06EjoVIA2sDWrVstgeBRWFioHTt2WNq8p4uys7Md+2xOpXD9+nWdOXNGktS3b19L1SBJn3/+uQkEbz/++KPfrawID4QC0AbOnz/f7HPeoZCfn2+ZYvLWnErBO1SGDRvmd76goMBxXIWFhY7n0HERCkAbmDJliuO5CRMmWI579uypyMj//tf0nv7x5l0p3Lp1y/Ya7/fahcLkyZNt3xcZGampU6c6jhkdF6EAtIH09HRNmjTJrz0tLU0LFy60tEVGRqpHjx7m2GkKqTmVQlOh8MknnyglJcWvfe3atZa7oBA+CAWgDURFRemPP/7Qxo0bzcLx5MmTtWfPHrlc/vd7+C4222lqTeHq1auWZyHZhUJiYqIGDBggSUpOTtbatWt17NgxrVixopmfDB0NoQC0kejoaC1fvlw7duxQ3759dezYMZ07d872Wu91hYKCAttF6qYqBd8wsQuFI0eOmEdsvP/++1q5cqUmTpzYvA+EDolQANpYZGSk5s6dq8bGRn366ae21/huWPP9gq+vr7fsYrYLBd9nJtmFwqpVqyTd39T24osvNmv86NgIBSAI5s+fL0n6/vvvVVRU5HfeNxR81xW8p46kpiuFmJgYv8doeFcJzz77rGXKCuGLUACCIDU1VfHx8aqrq9O6dev8zjdVKXhPHUn+oXDx4kXLLaVDhw71e6yFp0qQpMWLF7do/Oi4CAUgCKKiojR79mxJ0jfffKNr165Zzvv+q72oqEjFxcXmuKlKoan1BO8qISYmRvPmzWv5h0CHRCgAQeKZQqqtrdUXX3xhOWf3EDzvKSTfSsHtdqu+vt4cNxUK3lXC7NmzFR8f36Kxo+MiFIAgmTVrlqKjoyVJmzZtUnl5uTlnFwreX/S+lYJk3cD2oFDwrhKk+3soAA9CAQiSbt26aebMmZLuT/9s2LDBnGtppeDpQ7r/eIqLFy9aznmHwurVq83ruLg4M40FSIQCEFTec/kbNmww/9q3uxOouLjY3KlkVyl4QsFus5snFHJycvTbb79Z/nzfh+QhvBEKQBDNmTPHPOeorKxMmzZtkmRfKUj/feE/bCh4ryVI3HUEf4QCEES9e/fW008/bY7Xr1+v2traJkPhQdNHvqHQp08fde3a1a9K6NWrl5m+AjwIBSDIPHchSVJJSYm++eYbRUVFWX54x8OzruBUKfz9998qKSmxtDtVCQsXLrR97hLCG6EABJnvHoF169apvr7etlq4fPmyCgoKHCsFp6kj3ypBYuoI9ggFIMiGDh1q+U2FoqIi7dy50/GxE1lZWY6Vgu/zjqT7oeBbJQwcOFDTpk17tIGjQyIUgBCQlpZmOf7ss8+UkJBge21WVpZjpWD32wv//vuvX5Xwwgsv+D32ApAkJhSBEBATE2M5PnPmjOPPcGZnZys5Odmv/c8//9T169f92jMyMvzauA0VTggFIESVlZXZtl+9etXy2GyPX375xfb6ioqK1hwWOjimj4B2qLKy0q/NKUSAlqBSAELM6tWrzYa21pafn6/vvvsuIH2jYyAUgBCzcuXKgO0f2L17N6GAB2L6CABgUCkAIaZz587BHgLCGJUCAMAgFAAABqEAADAIBQCAQSgAAAxCAQBgcEsqEGLy8vLUqVOngPSdnZ2tt956KyB9o2MgFIAQM3LkyIDtaC4oKAhIv+g4mD4CABhUCkCIGTp0aMD6drvdAesbHQOhAISYK1euBHsICGOEAhACVq1a5fc7ykAwsKYAADAIBQCAQSgAAAxCAQBgEAoAAINQAAAYhAIAwCAUAAAGoQAAMAgFAIBBKAAADEIBAGAQCgAAg1AAABiEAgDAIBQAAAahAAAwCAUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAABqEAADAiGhsbG5u6qKqqSt27d9eKFSsUExPTFuMKex999FGwhxB2Vq9eHewhhBX+jrctz/d4ZWWl4uPjHa+jUgAAGIQCAMAgFAAABqEAADAIBQCAQSgAAAxCAQBgEAoAAINQAAAYhAIAwCAUAAAGoQAAMAgFAIBBKAAADEIBAGAQCgAAg1AAABiuYA8gUCorK7V//34VFRWpU6dOGj58uFJTUxUbGxvsoQFAyOqQoXD79m1t2bJFVVVVpu3YsWMqLi7Wm2++qc6dOwdxdAAQutpdKBQWFqqgoECNjY1KSkrS8OHD/a45fvy4JRA8rl+/rrNnz2rcuHGW9rq6OuXl5amkpESxsbEaM2aMevXqFbDPAAChql2Fwq5du3TixAlznJOTo3Hjxmn+/PmW60pLSx37uHnzpuXY7XZr27Ztunbtmmk7ePCg5syZo/Hjx7fOwAGgnWg3C835+fmWQPA4efKkzp07Z2lLSkpy7GfIkCGW4+zsbEsgSFJDQ4N2796tW7duPcKIAaD9aTehcP78ecdzRUVFluMxY8bo+eefV1RUlGmLjo7WrFmz/KabCgsLbfusq6tTcXHxI4wYANqfdjN9lJiY6HiuW7dufm1PPvmkJGnPnj2SpLlz5yolJcXvui5dujj226NHjxaOEgDat3ZTKYwdO1ZxcXF+7d27d9fEiRNt33P37l3z+t69e7bXPPHEE7btgwYNUr9+/R5ipADQfrWbUIiNjdWSJUs0atQode3a1bQvWrTIce9BbW2tee0dEN5SUlI0YcIEcxwZGamUlBSlp6crIiKilUYPAO1DSE0fVVZWau/evSooKJAkjRgxQjNnzjQVQu/evZWenq78/Hzt3LlTklRWVqb+/fvb9tecUJBk2bewdOlSv/4uXryo7OxslZSUqEuXLho7dqymT58ulyuk/vMBwCMLmUrBs+EsLy9Pbrdbbrdbp06d0tatWy1f7pIslYHvIrO35oaCdx+9e/e2nLty5Yq2b9+uwsJCud1ulZeX6+DBg8rIyGj2ZwOA9iJkQuHEiRO2G87Ky8t1+vRpS5v34vCFCxcc+2xOKNTU1OjGjRuS7i9Y++52Pnz4sOrr6/3el5+fr6tXrzr+2QDQHoVMKJSXlzf7nHelUFpaqurqatv3eQeBUyh4h0rPnj39zpeVlTV7XADQ3oVMKAwcONDxXN++fS3HMTExlkVgpykk70rB6e6jpkJhwIABtu+LiIjQ4MGDHccMAO1RyITCmDFjbBeMk5KS/PYXREZGKiYmxhw7TSE1Z/rIO1DsQuF///uf3zqDJD3zzDO2+yMAoD0LmdtnXC6XXn/9dR0/flzFxcU6c+aMBgwYoJdfftn21tDY2FjduXNH0sOHQnV1teU5SXahEBsbq7i4ON24cUMJCQkaP368kpKSHCsIAGjPQiYUpPvBMHnyZE2cOFHFxcW6cuWKbty4oT59+vhd673YXFZWpsrKSnXv3t1yTVNrCr7TTnahcPHiRfMojClTpmjSpEkt+1AA0I6EzPSRt8jISI0cOVKSdOjQIdtrfDes+VYLDQ0NlnWEhw2F7OxsMya7x2QAQEcSkqEgSaNHj5Yk5eXl2d7l4/vMIt9Q8N3bYBcK3u9xuVx+j9HwrhKGDRtm2UkNAB1RyIbC0KFDFR0drYaGBh0+fNjvvG+l4Puv/qZCoaKiwhI2PXr08Fu78FQJ0v2FcADo6EI2FFwul5KTkyXd39jmuxfBNxQqKipUUVFhjpsKBd/KwnfqyLtKcLlcGjVqVIs/AwC0NyEbCtJ/U0j19fXKycmxnLN75LX3F71vCNTV1amhocEcN7We4F0lJCcnW26BBYCOKqRDYfjw4erUqZMkKTc319yCKvlXCpL1i963UpCsQfGgSsG7SpCYOgIQPkI6FKKjo81Pa969e1dHjx4155qqFB4UCp5bWL15h8KBAwfM66ioKI0YMeLhPgAAtDMhHQqSLHP5R48eNV/sdpVCZWWlWTx+UCjYbXbzhMKlS5csP/05atQov4fkAUBHFfKhMHLkSHNX0J07d5SbmyvJPhSk/6aQHhQKds9K8oSC91qCdP8X3wAgXIR8KHTt2tXy4LmcnBzV1dU5/raypwqw25fgVCl07dpVUVFRflVCbGyshg0b9oifAADaj5APBck6hVRdXa0TJ07I5XIpKirK71rPF75TpXDz5k2/21udqoSUlBSz0A0A4aDdhYJ0/4dvGhoabKuFqqoqlZaWOoaC03qCb5UgcdcRgPDTLkKhZ8+elt9UqKio0OnTpx3XFS5cuOAYCk7rCb5VQnx8vIYMGfJoAweAdqZdhIIkc2uqx6FDhxzXFYqKihzXFOwqhZqaGr8qITk52faR3QDQkYXUo7MfxOWyDvXGjRuqqamxvfbChQtKTEz0a79y5Ypu3brl13727Nkm/zwACAft+pvPe4ezt5qaGtuf3ywoKLC93u12t+q4AKC9ajfTRy1lt6bgFCIAgPvaZaUwY8aMgM33l5aW6tSpUwHpGwBCXbsMhWnTpgVs/0B+fj6hACBsddjpIwBAy7XLSmHNmjXBHgIAdEhUCgAAg1AAABiEAgDAIBQAAAahAAAwCAUAgNEub0ldvnx5wHY0X7hwQT///HNA+gaAUNcuQyExMTFgO5rLysoC0i8AtAdMHwEAjHZZKXz55ZcB67uuri5gfQNAqGuXoVBdXR3sIQBAh9RuQiE1NVWpqanBHgYAdGisKQAADEIBAGAQCgAAg1AAABiEAgDAIBQAAAahAAAwCAUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAABqEAADAIBQCAQSgAAAxCAQBgEAoAAINQAAAYhAIAwCAUAAAGoQAAMAgFAIBBKAAADFdLLv7ggw8UHx8fqLHAy+rVq4M9hLDz0UcfBXsIYYW/423L7XY36zoqBQCAQSgAAAxCAQBgEAoAAINQAAAYhAIAwCAUAAAGoQAAMAgFAIBBKAAADEIBAGAQCgAAg1AAABiEAgDAIBQAAAahAAAwWvQjOwAQriorK7V//34VFRWpU6dOGj58uFJTUxUbGxvsobUqQgEAmnD79m1t2bJFVVVVpu3YsWMqLi7Wm2++qc6dOwdxdK2LUAAQ1goLC1VQUKDGxkYlJSVp+PDhftccP37cEgge169f19mzZzVu3DhLe11dnfLy8lRSUqLY2FiNGTNGvXr1CthnaE2EAoCwtWvXLp04ccIc5+TkaNy4cZo/f77lutLSUsc+bt68aTl2u93atm2brl27ZtoOHjyoOXPmaPz48a0z8ABioRlAWMrPz7cEgsfJkyd17tw5S1tSUpJjP0OGDLEcZ2dnWwJBkhoaGrR7927dunXrEUbcNggFAGHp/PnzjueKioosx2PGjNHzzz+vqKgo0xYdHa1Zs2b5TTcVFhba9llXV6fi4uJHGHHbYPoIQFhKTEx0PNetWze/tieffFKStGfPHknS3LlzlZKS4nddly5dHPvt0aNHC0fZ9qgUAISlsWPHKi4uzq+9e/fumjhxou177t69a17fu3fP9ponnnjCtn3QoEHq16/fQ4y0bREKAMJSbGyslixZolGjRqlr166mfdGiRY57D2pra81r74DwlpKSogkTJpjjyMhIpaSkKD09XREREa00+sBh+ghAh1VZWam9e/eqoKBAkjRixAjNnDnTVAi9e/dWenq68vPztXPnTklSWVmZ+vfvb9tfc0JBkmXfwtKlS/36u3jxorKzs1VSUqIuXbpo7Nixmj59ulyu4H8lUykA6JA8G87y8vLkdrvldrt16tQpbd261fLlLslSGfguMntrbih499G7d2/LuStXrmj79u0qLCyU2+1WeXm5Dh48qIyMjGZ/tkAiFAB0SCdOnLDdcFZeXq7Tp09b2rwXhy9cuODYZ3NCoaamRjdu3JB0f8Had7fz4cOHVV9f7/e+/Px8Xb161fHPbiuEAoAOqby8vNnnvCuF0tJSVVdX277POwicQsE7VHr27Ol3vqysrNnjCgZCAUCHNHDgQMdzffv2tRzHxMRYFoGdppC8KwWnu4+aCoUBAwbYvi8iIkKDBw92HHNbIRQAdEhjxoyxXTBOSkry218QGRmpmJgYc+w0hdSc6SPvQLELhf/9739+6wyS9Mwzz9juj2hrwV/qBoAAcLlcev3113X8+HEVFxfrzJkzGjBggF5++WXbW0NjY2N1584dSQ8fCtXV1ZbnJNmFQmxsrOLi4nTjxg0lJCRo/PjxSkpKcqwg2hqhAKDDcrlcmjx5siZOnKji4mJduXJFN27cUJ8+ffyu9V5sLisrU2Vlpbp37265pqk1Bd9pJ7tQuHjxonkUxpQpUzRp0qSWfagAY/oIQIcXGRmpkSNHSpIOHTpke43vhjXfaqGhocGyjvCwoZCdnW3GZPeYjGAjFACEhdGjR0uS8vLybO/y8X1mkW8o+O5tsAsF7/e4XC6/x2h4VwnDhg2z7KQOFYQCgLAwdOhQRUdHq6GhQYcPH/Y771sp+P6rv6lQqKiosIRNjx49/NYuPFWCdH8hPBQRCgDCgsvlUnJysqT7G9t89yL4hkJFRYUqKirMcVOh4FtZ+E4deVcJLpdLo0aNavFnaAuEAoCw4ZlCqq+vV05OjuWc3SOvvb/ofUOgrq5ODQ0N5rip9QTvKiE5OdlyC2woIRQAhI3hw4erU6dOkqTc3FxzC6rkXylI1i9630pBsgbFgyoF7ypBCt2pI4lQABBGoqOjzU9r3r17V0ePHjXnmqoUHhQKnltYvXmHwoEDB8zrqKgojRgx4uE+QBsgFACEFe+5/KNHj5ovdrtKobKy0iwePygU7Da7eULh0qVLlp/+HDVqlN9D8kIJoQAgrIwcOdLcFXTnzh3l5uZKsg8F6b8ppAeFgt2zkjyh4L2WIN3/xbdQRigACCtdu3a1PHguJydHdXV1jr+t7KkC7PYlOFUKXbt2VVRUlF+VEBsbq2HDhj3iJwgsQgFA2PGeQqqurtaJEyfkcrkUFRXld63nC9+pUrh586bf7a1OVUJKSopZ6A5VhAKAsOO7R+Dw4cNqaGiwrRaqqqpUWlrqGApO6wm+VYIU2ncdeRAKAMJOz549Lb+pUFFRodOnTzuuK1y4cMExFJzWE3yrhPj4eA0ZMuTRBt4GCAUAYclza6rHoUOHHNcVioqKHNcU7CqFmpoavyohOTnZ9pHdoYZHZwMISy6X9evvxo0bqqmpsb32woULSkxM9Gu/cuWKbt265dd+9uzZJv+8UNU+RgkAbcB7h7O3mpoa25/fLCgosL3e7Xa36rjaEtNHANAMdmsKTiHSnlEpAAh7M2bMCNh8f2lpqU6dOhWQvgOBUAAQ9qZNmxaw/QP5+fntKhSYPgIAGFQKAMLemjVrgj2EkEGlAAAwCAUAgEEoAAAMQgEAYBAKAACDUAAAGNySCiDsLV++PGA7mi9cuKCff/45IH0HAqEAIOwlJiYGbEdzWVlZQPoNFKaPAAAGlQKAsPfll18GrO+6urqA9R0IhAKAsFddXR3sIYQMQgFAWEpNTVVqamqwhxFyWFMAABiEAgDAIBQAAAahAAAwCAUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAABqEAADAIBQCAQSgAAAxCAQBgEAoAAINQAAAYhAIAwCAUAAAGoQAAMAgFAIBBKAAADEIBAGAQCgAAg1AAABgRjY2NjU1dVFVVpe7du2vFihWKiYlpi3GFvY8++ijYQwg7q1evDvYQwgp/x9uW53u8srJS8fHxjtdRKQAADEIBAGAQCgAAg1AAABiEAgDAIBQAAAahAAAwCAUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAABqEAADAIBQCAQSigVVy+fFmvvfaaBg8erKSkJL399tsqLS0N9rAAtJAr2ANA+1dWVqannnpKly5dMm0bN27UgQMHdOzYMX6tD2hHCAU80L59+/Trr7+qvr5eaWlpeu655/yu2bx5syUQPPLy8pSRkaFXXnnF0l5bW6sffvhBubm56tWrl9LT0zVixIiAfQYAzUcowNHSpUu1ZcsWc7x+/Xq9+uqr2rZtm+W6/Px8xz58z1VWVmrGjBn666+/TNvHH3+szZs3a8mSJa0ybgAPjzUF2Prpp58sgeCxfft2ZWZmWtrS0tIc+5k+fbrleNWqVZZAkKR79+5p2bJlunnz5sMPGECrIBRga+/evY7n9u/fbzletGiRvvrqK3Xr1s20de/eXRs2bPALjN9//922T7fbrYMHDz7CiAG0BqaPYOtBc/z9+vXza3vnnXfU2Nio9957T5K0detWLViwwO+6hIQEx36HDBnS8oECaFVUCrD10ksvqX///n7tgwcP1rJly2zfU1NTY17fvn3b9pp3333Xtn3q1Kl6/PHHH2KkAFoToQBbCQkJ2rdvn+bNm6fHHnvMtGdmZioxMdH2PVVVVea1d0B4W7Bggd544w1z7HK5tHDhQmVmZioiIqKVRg/gYREKYezSpUtavHixevbsqYSEBC1ZskRXr14150eNGqXMzEx9/fXXpu2ff/5x7K85oSBJXbp0Ma+PHj2qjIwM9e7d27QdOXJEaWlpSkhI0PDhw/Xhhx+qtra2xZ8PQMuxphCmPBvOLl++bNq+/fZbHT58WCdPnrQsGvfq1cu8zsrK0qJFi2z7rK6uNq8fFApZWVnm9ejRoy3ncnNzlZqaqrt370qSysvLtWbNGp08eVK7du1q5qcD8LCoFMLU1q1bLYHgUVhYqB07dljavKeLsrOzHftsTqVw/fp1nTlzRpLUt29fS9UgSZ9//rkJBG8//vij362sAFofoRCmzp8/3+xz3qGQn59vmWLy1pxKwTtUhg0b5ne+oKDAcVyFhYWO5wC0DkIhTE2ZMsXx3IQJEyzHPXv2VGTkf39VvKd/vHlXCrdu3bK9xvu9dqEwefJk2/dFRkZq6tSpjmMG0DoIhTCVnp6uSZMm+bWnpaVp4cKFlrbIyEj16NHDHDtNITWnUmgqFD755BOlpKT4ta9du9ZyFxSAwCAUwlRUVJT++OMPbdy40SwcT548WXv27JHL5X//ge9is52m1hSuXr1qeRaSXSgkJiZqwIABkqTk5GStXbtWx44d04oVK5r5yQA8CkIhjEVHR2v58uXasWOH+vbtq2PHjuncuXO213qvKxQUFNguUjdVKfiGiV0oHDlyxDxi4/3339fKlSs1ceLE5n0gAI+MUIAiIyM1d+5cNTY26tNPP7W9xnfDmu8XfH19vWUXs10o+D4zyS4UVq1aJen+prYXX3yxWeMH0HoIBUiS5s+fL0n6/vvvVVRU5HfeNxR81xW8p46kpiuFmJgYv8doeFcJzz77rGXKCkDbIBQgSUpNTVV8fLzq6uq0bt06v/NNVQreU0eSfyhcvHjRckvp0KFD/R5r4akSJGnx4sUtGj+A1kEoQNL9hefZs2dLkr755htdu3bNct73X+1FRUUqLi42x01VCk2tJ3hXCTExMZo3b17LPwSAR0YowPBMIdXW1uqLL76wnLN7CJ73FJJvpeB2u1VfX2+OmwoF7yph9uzZio+Pb9HYAbQOQgHGrFmzFB0dLUnatGmTysvLzTm7UPD+ovetFCTrBrYHhYJ3lSDd30MBIDgIBRjdunXTzJkzJd2f/tmwYYM519JKwdOHdP/xFBcvXrSc8w6F1atXm9dxcXFmGgtA2yMUYOE9l79hwwbzr327O4GKi4vNnUp2lYInFOw2u3lCIScnR7/99pvlz/d9SB6AtkMowGLOnDnmOUdlZWXatGmTJPtKQfrvC/9hQ8F7LUHiriMg2AgFWPTu3VtPP/20OV6/fr1qa2ubDIUHTR/5hkKfPn3UtWtXvyqhV69eZvoKQHAQCvDjuQtJkkpKSvTNN98oKirK8sM7Hp51BadK4e+//1ZJSYml3alKWLhwoe1zlwC0HUIBfnz3CKxbt0719fW21cLly5dVUFDgWCk4TR35VgkSU0dAKCAU4Gfo0KGW31QoKirSzp07HR87kZWV5Vgp+D7vSLofCr5VwsCBAzVt2rRHGziAR0YowFZaWprl+LPPPlNCQoLttVlZWY6Vgt1vL/z7779+VcILL7zg99gLAG2PCVzYiomJsRyfOXPG8Wc4s7OzlZyc7Nf+559/6vr1637tGRkZfm3chgqEBkIBzVZWVmbbfvXqVctjsz1++eUX2+srKipac1gAWhHTR2gVlZWVfm1OIQIgdFEpoEmrV682G9paW35+vr777ruA9A2g5QgFNGnlypUB2z+we/duQgEIIUwfAQAMKgU0qXPnzsEeAoA2QqUAADAIBQCAQSgAAAxCAQBgEAoAAINQAAAY3JKKJuXl5alTp04B6Ts7O1tvvfVWQPoG0HKEApo0cuTIgO1oLigoCEi/AB4O00cAAINKAU0aOnRowPp2u90B6xtAyxEKaNKVK1eCPQQAbYRQgK1Vq1b5/Y4ygI6PNQUAgEEoAAAMQgEAYBAKAACDUAAAGIQCAMAgFAAABqEAADAIBQCAQSgAAAxCAQBgEAoAAINQAAAYhAIAwCAUAAAGoQAAMAgFAIBBKAAADEIBAGAQCgAAg1AAABiEAgDAIBQAAAahAAAwCAUAgOFqzkWNjY2SpNra2oAOBv+pqqoK9hDCjtvtDvYQwgp/x9uW57+35/vcSURjU1dIunz5sgYNGtQ6IwMABM2lS5c0cOBAx/PNCoWGhgaVlJQoLi5OERERrTpAAEDgNTY2qrq6Wv3791dkpPPKQbNCAQAQHlhoBgAYhAIAwCAUAAAGoQAAMAgFAIBBKAAADEIBAGD8P560PnjoTWvPAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "board = [1,3,0,2]\n",
    "show_board(board)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tasks\n",
    "\n",
    "## General [10 Points]\n",
    "\n",
    "1. Make sure that you use the latest version of this notebook. Sync your forked repository and pull the latest revision. \n",
    "2. Your implementation can use libraries like math, numpy, scipy, but not libraries that implement intelligent agents or complete search algorithms. Try to keep the code simple! In this course, we want to learn about the algorithms and we often do not need to use object-oriented design.\n",
    "3. You notebook needs to be formatted professionally. \n",
    "    - Add additional markdown blocks for your description, comments in the code, add tables and use mathplotlib to produce charts where appropriate\n",
    "    - Do not show debugging output or include an excessive amount of output.\n",
    "    - Check that your submitted file is readable and contains all figures.\n",
    "4. Document your code. Use comments in the code and add a discussion of how your implementation works and your design choices."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 1: Steepest-ascend Hill Climbing Search [30 Points]\n",
    "\n",
    "Calculate the objective function for all local moves (see definition of local moves above) and always choose the best among all local moves. If there are no local moves that improve the objective, then you have reached a local optimum. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Code and description go here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 2: Stochastic Hill Climbing 1 [10 Points]\n",
    "\n",
    "Chooses randomly from among all uphill moves till you have reached a local optimum."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Code and description go here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 3: Stochastic Hill Climbing 2 [20 Points]\n",
    "\n",
    "A popular version of stochastic hill climbing generates only a single random local neighbor at a time and accept it if it has a better objective function value than the current state. This is very efficient if each state has many possible successor states. This method is called \"First-choice hill climbing\" in the textbook.\n",
    "\n",
    "__Notes:__ \n",
    "\n",
    "* Detecting local optima is tricky! You can, for example, stop if you were not able to improve the objective function during the last $x$ tries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Code and description go here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 4: Hill Climbing Search with Random Restarts [10 Points]\n",
    "\n",
    "Hill climbing will often end up in local optima. Restart the each of the three hill climbing algorithm up to 100 times with a random board to find a better (hopefully optimal) solution. Note that restart just means to run the algorithm several times starting with a new random board."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Code and description go here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 5: Simulated Annealing [10 Points]\n",
    "\n",
    "Simulated annealing is a form of stochastic hill climbing that avoid local optima by also allowing downhill moves with a probability proportional to a temperature. The temperature is decreased in every iteration following an annealing schedule. You have to experiment with the annealing schedule (Google to find guidance on this).\n",
    "\n",
    "\n",
    "1. Implement simulated annealing for the n-Queens problem.\n",
    "2. Compare the performance with the previous algorithms. \n",
    "2. Discuss your choice of annealing schedule."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Code and description go here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 6: Compare Performance [10 Points]\n",
    "\n",
    "Compare the algorithm using runtime and objective function values. Use boards of size 4 and 8 to explore how the different algorithms perform. Make sure that you run the algorithms for each board size several times (at least 100 times) with different starting boards and report averages.\n",
    "\n",
    "Complete the following table\n",
    "\n",
    "| Algorithm           | Board size | Avg. Run time | Avg. number of conflicts | % of runs ending in optimal solution  |\n",
    "| ------------------- | ---------- | ------------- | --------------------------------- | - |\n",
    "| Steepest asc. HC    |     4      |               |                                   |   |\n",
    "| Stochastic HC 1     |     4      |               |                                   |   |\n",
    "| Stochastic HC 2     |     4      |               |                                   |   |\n",
    "| Simulated Annealing |     4      |               |                                   |   |\n",
    "| Steepest asc. HC    |     8      |               |                                   |   |\n",
    "| Stochastic HC 1     |     8      |               |                                   |   |\n",
    "| Stochastic HC 2     |     8      |               |                                   |   |\n",
    "| Simulated Annealing |     8      |               |                                   |   |\n",
    "\n",
    "\n",
    "Add the used code and the answer to the following questions below.\n",
    "\n",
    "* How do the algorithms scale with problem size? You will need to run more board sizes. You can add the results to the table above and show the result as a chart.\n",
    "\n",
    "* What is the largest board each algorithm can solve in a reasonable amount time?\n",
    "\n",
    "Hint: See [Profiling Python Code](../HOWTOs/profiling_code.ipynb) for help about how to measure runtime in Python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Code, results, charts and discussion go here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Advanced task: Exploring other Local Moves\n",
    "\n",
    "* __Graduate students__ need to complete this task [10 points]\n",
    "* __Undergraduate students__ can attempt this as a bonus task [max +5 bonus points].\n",
    "\n",
    "Implement a few different local moves. Implement:\n",
    "\n",
    "* moving one queen only one square at a time\n",
    "* switching two columns\n",
    "* move two queens at a time \n",
    "\n",
    "Compare the performance of these moves for the 8-Queens problem using your stochastic hill climbing 2 implementation from above. Also consider mixing the use of several types of local moves (e.g., move one queen and moving two queens).\n",
    "\n",
    "Describe what you find out about how well these moves and combinations of these moves work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Code and description go here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## More things to do\n",
    "\n",
    "Implement a Genetic Algorithm for the n-Queens problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Code and description go here"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.12"
  },
  "toc-autonumbering": false,
  "toc-showcode": false,
  "toc-showmarkdowntxt": false,
  "toc-showtags": false
 },
 "nbformat": 4,
 "nbformat_minor": 4
}