State_Space_Search_&_DFS,_BFS.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# Question B\n"
      ],
      "metadata": {
        "id": "fI6R5_XyKS9X"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "GOAL_STATE =  [[1,2,3],[4,5,6],[7,8,0]]\n",
        "\n",
        "#actions\n",
        "# This function return list of possible moves from the current state\n",
        "def get_possible_moves(state):\n",
        "    blank_position = find_blank_position(state)\n",
        "    row, col = blank_position\n",
        "    moves = []\n",
        "    if row > 0:\n",
        "        moves.append(\"up\")\n",
        "    if row < 2:\n",
        "        moves.append(\"down\")\n",
        "    if col > 0:\n",
        "        moves.append(\"left\")\n",
        "    if col < 2:\n",
        "        moves.append(\"right\")\n",
        "    return moves\n",
        "\n",
        "\n",
        "# succesor function\n",
        "#This function performs a move on the current state\n",
        "def perform_move(state, move):\n",
        "    blank_position = find_blank_position(state)\n",
        "    new_state = [row.copy() for row in state]  # Create a new 2D list\n",
        "    row, col = blank_position\n",
        "\n",
        "    if move == \"up\":\n",
        "        new_state[row][col], new_state[row - 1][col] = new_state[row - 1][col], new_state[row][col]\n",
        "    elif move == \"down\":\n",
        "        new_state[row][col], new_state[row + 1][col] = new_state[row + 1][col], new_state[row][col]\n",
        "    elif move == \"left\":\n",
        "        new_state[row][col], new_state[row][col - 1] = new_state[row][col - 1], new_state[row][col]\n",
        "    else:\n",
        "        new_state[row][col], new_state[row][col + 1] = new_state[row][col + 1], new_state[row][col]\n",
        "\n",
        "    return new_state\n",
        "\n",
        "\n",
        "def find_blank_position(state):\n",
        "    for i, row in enumerate(state):\n",
        "        for j, value in enumerate(row):\n",
        "            if value == 0:\n",
        "                return i, j\n",
        "\n",
        "\n",
        "#This function checks if current state is goal state\n",
        "def is_goal_state(state):\n",
        "  #Check if the current state is teh goal state\n",
        "  return state == GOAL_STATE\n"
      ],
      "metadata": {
        "id": "psBprHfWKlEd"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Question D"
      ],
      "metadata": {
        "id": "SPnGKek7KbSv"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from collections import defaultdict as dd\n",
        "\n",
        "class Graph:\n",
        "\n",
        "    def __init__(self):\n",
        "        self.graph = dd(list)\n",
        "        self.parent = dd(int)\n",
        "        self.distance = dd(int)\n",
        "        self.frontier = list()\n",
        "\n",
        "    def set_distance(self, node):\n",
        "        self.distance[node] = -1\n",
        "\n",
        "    # method to add edges in the BFS graph\n",
        "    def add_edge(self, a, b):\n",
        "        self.graph[a].append(b)\n",
        "        self.graph[b].append(a)\n",
        "\n",
        "    # method to backtrack and generate the path\n",
        "    def get_path(self, start, goal):\n",
        "        path, node = [], goal\n",
        "        while node != start:\n",
        "            path.append(node)\n",
        "            node = self.parent[node]\n",
        "        path.append(start)\n",
        "        path.reverse()\n",
        "        return path\n",
        "\n",
        "    # method to implement BFS\n",
        "    def bfs(self, start, goal):\n",
        "        self.distance[start] = 0\n",
        "        self.frontier.append(start)\n",
        "        while len(self.frontier) != 0:\n",
        "            a = self.frontier.pop(0)\n",
        "            for b in self.graph[a]:\n",
        "                if self.distance[b] == -1:\n",
        "                    self.distance[b] = self.distance[a] + 1\n",
        "                    self.parent[b] = a\n",
        "                    self.frontier.append(b)\n",
        "        distance = self.distance[goal]\n",
        "        if distance != -1:\n",
        "            path = self.get_path(start, goal)\n",
        "        else:\n",
        "            path = None\n",
        "        return path, distance\n",
        "\n",
        "def main():\n",
        "    graph = Graph()\n",
        "    num_nodes, num_edges = [int(x) for x in input('\\nEnter number of nodes, number of edges: ').split()]\n",
        "    for i in range(1, num_nodes + 1):\n",
        "        graph.set_distance(i)\n",
        "    print('\\n')\n",
        "    for i in range(num_edges):\n",
        "        a, b = [int(x) for x in input('Enter initial node, end node of edge ' + str(i + 1) + ': ').split()]\n",
        "        graph.add_edge(a, b)\n",
        "    start, goal = [int(x) for x in input('\\nEnter start node, goal node: ').split()]\n",
        "    path, distance = graph.bfs(start, goal)\n",
        "    if distance == -1:\n",
        "        print('\\nPath from start node to goal node does not exist.\\n')\n",
        "    else:\n",
        "        path_route = ' --> '.join([str(x) for x in path])\n",
        "        print('\\nPath from start node to goal node: ', path_route)\n",
        "        print('Total path distance: ', distance, '\\n')\n",
        "\n",
        "if __name__ == '__main__':\n",
        "    main()"
      ],
      "metadata": {
        "id": "pnxFN86cKl1g"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Question E"
      ],
      "metadata": {
        "id": "unn4cTgSKfuA"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import random\n",
        "def get_possible_moves(state):\n",
        "    blank_position = find_blank_position(state)\n",
        "    row, col = blank_position\n",
        "    moves = []\n",
        "    if row > 0:\n",
        "        moves.append(\"up\")\n",
        "    if row < 2:\n",
        "        moves.append(\"down\")\n",
        "    if col > 0:\n",
        "        moves.append(\"left\")\n",
        "    if col < 2:\n",
        "        moves.append(\"right\")\n",
        "    return moves\n",
        "\n",
        "def perform_move(state, move):\n",
        "    blank_position = find_blank_position(state)\n",
        "    new_state = [row.copy() for row in state]  # Create a new 2D list\n",
        "    row, col = blank_position\n",
        "\n",
        "    if move == \"up\":\n",
        "        new_state[row][col], new_state[row - 1][col] = new_state[row - 1][col], new_state[row][col]\n",
        "    elif move == \"down\":\n",
        "        new_state[row][col], new_state[row + 1][col] = new_state[row + 1][col], new_state[row][col]\n",
        "    elif move == \"left\":\n",
        "        new_state[row][col], new_state[row][col - 1] = new_state[row][col - 1], new_state[row][col]\n",
        "    else:\n",
        "        new_state[row][col], new_state[row][col + 1] = new_state[row][col + 1], new_state[row][col]\n",
        "\n",
        "    return new_state\n",
        "\n",
        "def find_blank_position(state):\n",
        "    for i, row in enumerate(state):\n",
        "        for j, value in enumerate(row):\n",
        "            if value == 0:\n",
        "                return i, j\n",
        "\n",
        "def generate_states_at_depth_d(goal_state, depth):\n",
        "    states_at_depth = []\n",
        "\n",
        "    def backtrack(current_state, depth_left):\n",
        "        if depth_left == 0:\n",
        "            states_at_depth.append(current_state)\n",
        "            return\n",
        "\n",
        "        moves = get_possible_moves(current_state)\n",
        "        random.shuffle(moves)\n",
        "        for move in moves:\n",
        "            new_state = perform_move(current_state, move)\n",
        "            backtrack(new_state, depth_left - 1)\n",
        "\n",
        "    backtrack(goal_state, depth)\n",
        "    return states_at_depth\n",
        "\n",
        "# Example usage:\n",
        "goal_state = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]\n",
        "depth = 2\n",
        "states = generate_states_at_depth_d(goal_state, depth)\n",
        "for i, state in enumerate(states):\n",
        "    print(f\"State {i + 1}:\\n\", \"\\n\".join(map(str, state)))\n",
        "    print()"
      ],
      "metadata": {
        "id": "0-XV4f73KmaJ"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}