190104140_Assignment2.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Path between I to G : ['I', 'A', 'C', 'D', 'G']\n",
      "Length of the path: 118\n"
     ]
    }
   ],
   "source": [
    "# Recursive function to find the length of a path between two vertices of a directed weighted graph\n",
    "\n",
    "path = []\n",
    "length = 0\n",
    "\n",
    "def findPath(graph, source, destination):\n",
    "    global length\n",
    "    path.append(source)\n",
    "    if source == destination:\n",
    "        return True\n",
    "\n",
    "    for neighbor in graph[source]:\n",
    "        if neighbor not in path:\n",
    "            if(findPath(graph, neighbor, destination)) :\n",
    "                length += graph[source][neighbor]\n",
    "                return True\n",
    "            \n",
    "    path.pop()\n",
    "    return False\n",
    "\n",
    "graph = {\n",
    "  'I': {'A': 35, 'B': 45},\n",
    "  'A': {'C': 22, 'D': 32},\n",
    "  'B': {'D': 28, 'E': 36},\n",
    "  'C': {'D': 31, 'G': 47},\n",
    "  'D': {'G': 30},\n",
    "  'E': {'G': 26}\n",
    "}\n",
    "     \n",
    "findPath(graph, 'I', 'G')\n",
    "print(\"Path between I to G : \" + str(path))\n",
    "print(\"Length of the path: \" + str(length))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Heuristic Value (h2) of this instance of 8-puzzle: 8\n"
     ]
    }
   ],
   "source": [
    "# H2 function using Manhattan Distance of tiles in 8-puzzle Problem\n",
    "\n",
    "def h2():\n",
    "    goalPos=[(1,1,1), (2,1,2), (3,1,3), (4,2,3), (5,3,3), (6,3,2), (7,3,1), (8,2,1)]\n",
    "    currPos=[(1,1,2), (2,1,3), (3,2,1), (4,2,3), (5,3,3), (6,2,2), (7,3,2), (8,1,1)]\n",
    "\n",
    "    h_value = 0 \n",
    "\n",
    "    for i in range(8):\n",
    "        if(currPos[i] != goalPos[i]):\n",
    "            h_value += abs(goalPos[i][1] - currPos[i][1]) + abs(goalPos[i][2] - currPos[i][2])\n",
    "\n",
    "    print(\"Heuristic Value (h2) of this instance of 8-puzzle: {0}\".format(h_value))\n",
    "\n",
    "h2()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Heuristic value (h3) for this instance of 8-Queen Problem: 5\n"
     ]
    }
   ],
   "source": [
    "# H3 function of number of attacking pairs of 8-Queen Problem\n",
    "\n",
    "def h3(state):\n",
    "    queenPos = []\n",
    "    h_value = 0\n",
    "    \n",
    "    for x in state:\n",
    "        queenPos.append(int(x))\n",
    "\n",
    "    for i in range(1, 9):\n",
    "        for j in range(i+1 , 9):\n",
    "            # Checking for attacking position face to face\n",
    "            if(queenPos[i-1] == queenPos[j-1]):\n",
    "                h_value += 1\n",
    "            # Checking for attacking position diagonally\n",
    "            if(abs(i - j) == abs(queenPos[i-1] - queenPos[j-1])):\n",
    "                h_value += 1  \n",
    "\n",
    "    print(\"Heuristic value (h3) for this instance of 8-Queen Problem: {0}\".format(h_value))\n",
    "\n",
    "h3(\"81765432\")"
   ]
  }
 ],
 "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.10.4"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "20013eb197313dcbf638f07c9453d4dc581035df3e467822dafecac058618166"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}