AI - Lab 03 - Local Search - 8 Queens.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Artificial Intelligence — Lab — Exercise 03 — Question 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 08 September 2020"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solve 8-queens problem.\n",
    "<br>Place 8 queens in a chessboard so that no queen is under attack from any other queen. \n",
    "<br>One such “safe” configuration of 8 queens is shown below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>[X, X, X, Q, X, X, X, X]\n",
    "<br>[X, X, X, X, X, Q, X, X]\n",
    "<br>[X, X, X, X, X, X, X, Q]\n",
    "<br>[X, Q, X, X, X, X, X, X]\n",
    "<br>[X, X, X, X, X, X, Q, X]\n",
    "<br>[Q, X, X, X, X, X, X, X]\n",
    "<br>[X, X, Q, X, X, X, X, X]\n",
    "<br>[X, X, X, X, Q, X, X, X]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "class Board:\n",
    "    \"\"\"Class to work with the chessboard and its related functions. \"\"\"\n",
    "    \n",
    "    def __init__(self, config):\n",
    "        \"\"\"To create a new board configuration with its cost. \"\"\"\n",
    "        \n",
    "        self.config = config\n",
    "        self.size = len(self.config)\n",
    "        self.cost = self.find_conflicts()\n",
    "    \n",
    "    def __str__(self):\n",
    "        \"\"\"To print the board in a formatted manner. \"\"\"\n",
    "        \n",
    "        ret_str = \"\"\n",
    "        for pos in self.config:\n",
    "            for i in range(1, self.size+1):\n",
    "                if i == pos:\n",
    "                    ret_str += \"👑 \"\n",
    "                else:\n",
    "                    ret_str += \"❌ \"\n",
    "            \n",
    "            ret_str += \"\\n\"\n",
    "        \n",
    "        return ret_str\n",
    "    \n",
    "    def find_conflicts(self):\n",
    "        \"\"\"To find the number of conflicts in the given board configuration. \"\"\"\n",
    "        \n",
    "        conflicts = 0\n",
    "        \n",
    "        for i in range(self.size):\n",
    "            for j in range(i+1, self.size):\n",
    "                \n",
    "                if self.config[i] == self.config[j]:         #same row\n",
    "                    conflicts += 1\n",
    "                \n",
    "                elif self.config[i]+i == self.config[j]+j:   #same diagonal\n",
    "                    conflicts += 1\n",
    "                    \n",
    "                elif self.config[i]-i == self.config[j]-j:   #same antidiagonal\n",
    "                    conflicts += 1\n",
    "        \n",
    "        return conflicts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solver:\n",
    "    \"\"\"Class to solve the 8-Queens Problem given a configuration.\"\"\"\n",
    "    \n",
    "    def find_next_board(self, board):\n",
    "        \"\"\"To find the best next best board configuration possible, with minimum cost. \"\"\"\n",
    "\n",
    "        next_best_board = board\n",
    "\n",
    "        for i in range(board.size):\n",
    "            for j in range(1, board.size + 1):\n",
    "                if j != board.config[i]:\n",
    "                    new_config = [x for x in board.config]\n",
    "                    new_config[i] = j\n",
    "                    new_board = Board(new_config)\n",
    "\n",
    "                    if new_board.cost < next_best_board.cost:\n",
    "                        next_best_board = new_board\n",
    "\n",
    "        return next_best_board\n",
    "        \n",
    "    def hill_climber(self, board):\n",
    "        \"\"\"To find a solution to 8-Queens problem without conflicts. \"\"\"\n",
    "\n",
    "        while True:\n",
    "            next_board = self.find_next_board(board)\n",
    "        \n",
    "            if next_board.cost == board.cost: #No more improvement\n",
    "                break\n",
    "            else:\n",
    "                board = next_board\n",
    "                \n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Initial Board Configuration\n",
      "\n",
      "❌ ❌ ❌ 👑 ❌ ❌ ❌ ❌ \n",
      "❌ ❌ 👑 ❌ ❌ ❌ ❌ ❌ \n",
      "❌ 👑 ❌ ❌ ❌ ❌ ❌ ❌ \n",
      "❌ ❌ ❌ ❌ 👑 ❌ ❌ ❌ \n",
      "❌ ❌ ❌ 👑 ❌ ❌ ❌ ❌ \n",
      "❌ ❌ 👑 ❌ ❌ ❌ ❌ ❌ \n",
      "❌ 👑 ❌ ❌ ❌ ❌ ❌ ❌ \n",
      "❌ ❌ 👑 ❌ ❌ ❌ ❌ ❌ \n",
      "\n",
      "No. of Conflicts:  17\n",
      "\n",
      "Final Board Configuration\n",
      "\n",
      "❌ ❌ 👑 ❌ ❌ ❌ ❌ ❌ \n",
      "❌ ❌ ❌ ❌ ❌ 👑 ❌ ❌ \n",
      "❌ 👑 ❌ ❌ ❌ ❌ ❌ ❌ \n",
      "❌ ❌ ❌ ❌ 👑 ❌ ❌ ❌ \n",
      "👑 ❌ ❌ ❌ ❌ ❌ ❌ ❌ \n",
      "❌ ❌ ❌ 👑 ❌ ❌ ❌ ❌ \n",
      "❌ ❌ ❌ ❌ ❌ ❌ 👑 ❌ \n",
      "❌ ❌ 👑 ❌ ❌ ❌ ❌ ❌ \n",
      "\n",
      "No. of Conflicts:  1\n",
      "-----------------------------------\n",
      "\n",
      "Initial Board Configuration\n",
      "\n",
      "👑 ❌ ❌ ❌ ❌ ❌ ❌ ❌ \n",
      "❌ 👑 ❌ ❌ ❌ ❌ ❌ ❌ \n",
      "❌ ❌ ❌ 👑 ❌ ❌ ❌ ❌ \n",
      "❌ ❌ 👑 ❌ ❌ ❌ ❌ ❌ \n",
      "❌ ❌ ❌ ❌ ❌ 👑 ❌ ❌ \n",
      "❌ ❌ ❌ ❌ 👑 ❌ ❌ ❌ \n",
      "❌ ❌ ❌ ❌ ❌ ❌ ❌ 👑 \n",
      "❌ ❌ ❌ ❌ ❌ ❌ ❌ 👑 \n",
      "\n",
      "No. of Conflicts:  10\n",
      "\n",
      "Final Board Configuration\n",
      "\n",
      "❌ ❌ ❌ ❌ ❌ 👑 ❌ ❌ \n",
      "❌ 👑 ❌ ❌ ❌ ❌ ❌ ❌ \n",
      "❌ ❌ ❌ ❌ ❌ ❌ 👑 ❌ \n",
      "👑 ❌ ❌ ❌ ❌ ❌ ❌ ❌ \n",
      "❌ ❌ 👑 ❌ ❌ ❌ ❌ ❌ \n",
      "❌ ❌ ❌ ❌ 👑 ❌ ❌ ❌ \n",
      "❌ ❌ ❌ ❌ ❌ ❌ ❌ 👑 \n",
      "❌ ❌ ❌ 👑 ❌ ❌ ❌ ❌ \n",
      "\n",
      "No. of Conflicts:  0\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    \"\"\"Driver function to execute the 8-Queens Problem. \"\"\"\n",
    "    \n",
    "    init_config = [4, 3, 2, 5, 4, 3, 2, 3]\n",
    "    init_board = Board(init_config)\n",
    "    \n",
    "    print(\"\\nInitial Board Configuration\\n\")\n",
    "    print(init_board)\n",
    "    print(\"No. of Conflicts: \", init_board.cost)\n",
    "    \n",
    "    s = Solver()\n",
    "    final_board = s.hill_climber(init_board)\n",
    "    \n",
    "    print(\"\\nFinal Board Configuration\\n\")\n",
    "    print(final_board)\n",
    "    print(\"No. of Conflicts: \", final_board.cost)\n",
    "    \n",
    "    init_config = [1, 2, 4, 3, 6, 5, 8, 8]\n",
    "    init_board = Board(init_config)\n",
    "    \n",
    "    print(\"-----------------------------------\")\n",
    "    print(\"\\nInitial Board Configuration\\n\")\n",
    "    print(init_board)\n",
    "    print(\"No. of Conflicts: \", init_board.cost)\n",
    "    \n",
    "    s = Solver()\n",
    "    final_board = s.hill_climber(init_board)\n",
    "    \n",
    "    print(\"\\nFinal Board Configuration\\n\")\n",
    "    print(final_board)\n",
    "    print(\"No. of Conflicts: \", final_board.cost)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Hill-Climbing Algorithm finds only the local optimum and not the global optimum. \n",
    "This is why for some states the solution state is found (as in the 2nd example) for some configurations, <br>while it may not solve it completely (as in the 1st example) for some configurations. "
   ]
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}