8puzzel.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "from queue import PriorityQueue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## BFS Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_path(node):\n",
    "    path = []\n",
    "    while node:\n",
    "        parent_node_number = node['parent']['node_number'] if node['parent'] else None\n",
    "        path.append((node['state'], node['move'], node['node_number'], parent_node_number))\n",
    "        node = node['parent']\n",
    "\n",
    "    return path[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Global counter for node numbers\n",
    "node_counter = 0\n",
    "\n",
    "def expand(node, board_side):\n",
    "    global node_counter\n",
    "    neighbors = []\n",
    "    index = node['state'].index(0)\n",
    "    moves = [('left', -1), ('up', -board_side), ('right', 1), ('down', board_side)]\n",
    "\n",
    "    for m, offset in moves:\n",
    "        new_index = index + offset\n",
    "        if 0 <= new_index < len(node['state']) and (index % board_side != 0 or m != 'left') and ((index + 1) % board_side != 0 or m != 'right'):\n",
    "            new_state = node['state'][:]\n",
    "            new_state[index], new_state[new_index] = new_state[new_index], new_state[index]\n",
    "            node_counter += 1\n",
    "            neighbors.append({\n",
    "                'state': new_state,\n",
    "                'parent': node,\n",
    "                'move': m,\n",
    "                'depth': node['depth'] + 1,\n",
    "                'node_number': node_counter\n",
    "            })\n",
    "\n",
    "    return neighbors\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bfs_solve(initial_state):\n",
    "    global node_counter\n",
    "    goal_state = [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
    "    board_side = int(len(initial_state) ** 0.5)\n",
    "    explored, queue = set(), [{'state': initial_state, 'parent': None, 'move': None, 'depth': 0, 'node_number': 0}]\n",
    "    node_counter = 0\n",
    "\n",
    "    while queue:\n",
    "        node = queue.pop(0)\n",
    "        if node['state'] == goal_state:\n",
    "            return build_path(node), node['depth']\n",
    "\n",
    "        if tuple(node['state']) not in explored:\n",
    "            explored.add(tuple(node['state']))\n",
    "            neighbors = expand(node, board_side)\n",
    "            queue.extend(neighbors)\n",
    "\n",
    "    return None, None\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DFS Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_path_dfs(node):\n",
    "    path = []\n",
    "    while node:\n",
    "        parent_node_number = node['parent']['node_number'] if node['parent'] else None\n",
    "        path.append((node['state'], node['move'], node['node_number'], parent_node_number))\n",
    "        node = node['parent']\n",
    "\n",
    "    return path[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def expand_dfs(node, board_side):\n",
    "    global node_counter\n",
    "    neighbors = []\n",
    "    index = node['state'].index(0)\n",
    "    moves = [('left', -1), ('up', -board_side), ('right', 1), ('down', board_side)]\n",
    "\n",
    "    for m, offset in moves:\n",
    "        new_index = index + offset\n",
    "        if 0 <= new_index < len(node['state']) and (index % board_side != 0 or m != 'left') and ((index + 1) % board_side != 0 or m != 'right'):\n",
    "            new_state = node['state'][:]\n",
    "            new_state[index], new_state[new_index] = new_state[new_index], new_state[index]\n",
    "            node_counter += 1\n",
    "            neighbors.append({\n",
    "                'state': new_state,\n",
    "                'parent': node,\n",
    "                'move': m,\n",
    "                'depth': node['depth'] + 1,\n",
    "                'node_number': node_counter\n",
    "            })\n",
    "\n",
    "    return neighbors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dfs_solve(initial_state):\n",
    "    goal_state = [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
    "    board_side = int(len(initial_state) ** 0.5)\n",
    "\n",
    "    node_counter = 0\n",
    "    start_node = {\n",
    "        'state': initial_state, \n",
    "        'parent': None, \n",
    "        'move': None, \n",
    "        'depth': 0, \n",
    "        'node_number': node_counter\n",
    "    }\n",
    "\n",
    "    stack = [start_node]  # Using a stack for DFS\n",
    "    explored = set()\n",
    "\n",
    "    while stack:\n",
    "        current_node = stack.pop()\n",
    "        current_state = current_node['state']\n",
    "\n",
    "        if current_state == goal_state:\n",
    "            return build_path_dfs(current_node), current_node['depth']\n",
    "\n",
    "        if tuple(current_state) not in explored:\n",
    "            explored.add(tuple(current_state))\n",
    "            for neighbor in expand_dfs(current_node, board_side):\n",
    "                if tuple(neighbor['state']) not in explored:\n",
    "                    stack.append(neighbor)\n",
    "\n",
    "    return None, None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## IDS Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_path_ids(node):\n",
    "    path = []\n",
    "    while node:\n",
    "        parent_node_number = node['parent']['node_number'] if node['parent'] else None\n",
    "        path.append((node['state'], node['move'], node['node_number'], parent_node_number))\n",
    "        node = node['parent']\n",
    "\n",
    "    return path[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def expand_ids(node, board_side):\n",
    "    global node_counter\n",
    "    neighbors = []\n",
    "    index = node['state'].index(0)\n",
    "    moves = [('left', -1), ('up', -board_side), ('right', 1), ('down', board_side)]\n",
    "\n",
    "    for m, offset in moves:\n",
    "        new_index = index + offset\n",
    "        if 0 <= new_index < len(node['state']) and (index % board_side != 0 or m != 'left') and ((index + 1) % board_side != 0 or m != 'right'):\n",
    "            new_state = node['state'][:]\n",
    "            new_state[index], new_state[new_index] = new_state[new_index], new_state[index]\n",
    "            node_counter += 1\n",
    "            neighbors.append({\n",
    "                'state': new_state,\n",
    "                'parent': node,\n",
    "                'move': m,\n",
    "                'depth': node['depth'] + 1,\n",
    "                'node_number': node_counter\n",
    "            })\n",
    "\n",
    "    return neighbors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "def depth_limited_search(initial_state, goal_state, limit, board_side, node_counter):\n",
    "    stack = [{'state': initial_state, 'parent': None, 'move': None, 'depth': 0, 'node_number': node_counter}]\n",
    "    explored = set()\n",
    "\n",
    "    while stack:\n",
    "        node = stack.pop()\n",
    "        if node['depth'] > limit:\n",
    "            continue\n",
    "\n",
    "        if node['state'] == goal_state:\n",
    "            return build_path_ids(node), node['depth']\n",
    "\n",
    "        explored.add(tuple(node['state']))\n",
    "        for neighbor in expand_ids(node, board_side):\n",
    "            if tuple(neighbor['state']) not in explored:\n",
    "                stack.append(neighbor)\n",
    "\n",
    "    return None, None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ids_solve(initial_state):\n",
    "    goal_state = [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
    "    board_side = int(len(initial_state) ** 0.5)\n",
    "\n",
    "    node_counter = 0\n",
    "    for depth_limit in range(1, 100):  # Assuming a reasonable depth limit\n",
    "        result, depth = depth_limited_search(initial_state, goal_state, depth_limit, board_side, node_counter)\n",
    "        if result is not None:\n",
    "            return result, depth\n",
    "    return None, None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A* Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "def manhattan_distance(state, goal_state):\n",
    "    distance = 0\n",
    "    side_length = int(len(state) ** 0.5)\n",
    "    for num in range(1, len(state)):\n",
    "        current_idx = state.index(num)\n",
    "        goal_idx = goal_state.index(num)\n",
    "        current_row, current_col = divmod(current_idx, side_length)\n",
    "        goal_row, goal_col = divmod(goal_idx, side_length)\n",
    "        distance += abs(current_row - goal_row) + abs(current_col - goal_col)\n",
    "    return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_path_a_star(node):\n",
    "    path = []\n",
    "    while node:\n",
    "        parent_node_number = node['parent']['node_number'] if node['parent'] else None\n",
    "        path.append((node['state'], node['move'], node['node_number'], parent_node_number))\n",
    "        node = node['parent']\n",
    "\n",
    "    return path[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "def expand_a_star(node, board_side):\n",
    "    global node_counter\n",
    "    neighbors = []\n",
    "    index = node['state'].index(0)\n",
    "    moves = [('left', -1), ('up', -board_side), ('right', 1), ('down', board_side)]\n",
    "\n",
    "    for m, offset in moves:\n",
    "        new_index = index + offset\n",
    "        if 0 <= new_index < len(node['state']) and (index % board_side != 0 or m != 'left') and ((index + 1) % board_side != 0 or m != 'right'):\n",
    "            new_state = node['state'][:]\n",
    "            new_state[index], new_state[new_index] = new_state[new_index], new_state[index]\n",
    "            node_counter += 1\n",
    "            neighbors.append({\n",
    "                'state': new_state,\n",
    "                'parent': node,\n",
    "                'move': m,\n",
    "                'depth': node['depth'] + 1,\n",
    "                'node_number': node_counter,\n",
    "                'cost': 0\n",
    "            })\n",
    "\n",
    "    return neighbors\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "def a_star_solve(initial_state):\n",
    "    goal_state = [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
    "    board_side = int(len(initial_state) ** 0.5)\n",
    "\n",
    "    node_counter = 0\n",
    "    start_node = {\n",
    "        'state': initial_state, \n",
    "        'parent': None, \n",
    "        'move': None, \n",
    "        'depth': 0, \n",
    "        'node_number': node_counter, \n",
    "        'cost': manhattan_distance(initial_state, goal_state)\n",
    "    }\n",
    "    \n",
    "    open_set = [start_node]\n",
    "    explored = set()\n",
    "\n",
    "    while open_set:\n",
    "        # Sort the open set based on cost and pick the node with the lowest cost\n",
    "        open_set.sort(key=lambda node: node['cost'])\n",
    "        current_node = open_set.pop(0)\n",
    "        current_state = current_node['state']\n",
    "\n",
    "        if current_state == goal_state:\n",
    "            return build_path_a_star(current_node), current_node['depth']\n",
    "\n",
    "        explored.add(tuple(current_state))\n",
    "\n",
    "        for neighbor in expand_a_star(current_node, board_side):\n",
    "            if tuple(neighbor['state']) not in explored:\n",
    "                neighbor['cost'] = neighbor['depth'] + manhattan_distance(neighbor['state'], goal_state)\n",
    "                open_set.append(neighbor)\n",
    "\n",
    "    return None, None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## IDA* Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ida_search(node, g_cost, threshold, goal_state, board_side):\n",
    "    f_cost = g_cost + manhattan_distance(node['state'], goal_state)\n",
    "    if f_cost > threshold:\n",
    "        return f_cost, None\n",
    "    if node['state'] == goal_state:\n",
    "        return f_cost, node\n",
    "\n",
    "    min_cost = float('inf')\n",
    "    for neighbor in expand_a_star(node, board_side):\n",
    "        temp_cost, result = ida_search(neighbor, g_cost + 1, threshold, goal_state, board_side)\n",
    "        if result is not None:\n",
    "            return temp_cost, result\n",
    "        if temp_cost < min_cost:\n",
    "            min_cost = temp_cost\n",
    "\n",
    "    return min_cost, None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ida_star_solve(initial_state):\n",
    "    goal_state = [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
    "    board_side = int(len(initial_state) ** 0.5)\n",
    "\n",
    "    node_counter = 0\n",
    "    start_node = {\n",
    "        'state': initial_state, \n",
    "        'parent': None, \n",
    "        'move': None, \n",
    "        'depth': 0, \n",
    "        'node_number': node_counter, \n",
    "        'cost': manhattan_distance(initial_state, goal_state)\n",
    "    }\n",
    "\n",
    "    threshold = start_node['cost']\n",
    "    while True:\n",
    "        min_cost, result = ida_search(start_node, 0, threshold, goal_state, board_side)\n",
    "        if result is not None:\n",
    "            return build_path_a_star(result), result['depth']\n",
    "        if min_cost == float('inf'):\n",
    "            return None, None\n",
    "        threshold = min_cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## RBFS Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rbfs_search(node, f_limit, goal_state, board_side):\n",
    "    if node['state'] == goal_state:\n",
    "        return node, node['f_cost']\n",
    "\n",
    "    successors = expand_a_star(node, board_side)\n",
    "    if not successors:\n",
    "        return None, float('inf')\n",
    "\n",
    "    for s in successors:\n",
    "        s['f_cost'] = max(s['cost'] + manhattan_distance(s['state'], goal_state), node['f_cost'])\n",
    "\n",
    "    while True:\n",
    "        successors.sort(key=lambda x: x['f_cost'])\n",
    "        best = successors[0]\n",
    "\n",
    "        if best['f_cost'] > f_limit:\n",
    "            return None, best['f_cost']\n",
    "\n",
    "        alternative = successors[1]['f_cost'] if len(successors) > 1 else float('inf')\n",
    "        result, best['f_cost'] = rbfs_search(best, min(f_limit, alternative), goal_state, board_side)\n",
    "\n",
    "        if result is not None:\n",
    "            return result, best['f_cost']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rbfs_solve(initial_state):\n",
    "    goal_state = [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
    "    board_side = int(len(initial_state) ** 0.5)\n",
    "\n",
    "    node_counter = 0\n",
    "    start_node = {\n",
    "        'state': initial_state,\n",
    "        'parent': None,\n",
    "        'move': None,\n",
    "        'depth': 0,\n",
    "        'node_number': node_counter,\n",
    "        'cost': manhattan_distance(initial_state, goal_state),\n",
    "        'f_cost': manhattan_distance(initial_state, goal_state)\n",
    "    }\n",
    "\n",
    "    result, f_cost = rbfs_search(start_node, float('inf'), goal_state, board_side)\n",
    "    if result is not None:\n",
    "        return build_path_a_star(result), result['depth']\n",
    "    return None, None\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bidirectional Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_path_bidirectional(node):\n",
    "    path = []\n",
    "    while node:\n",
    "        parent_node_number = node['parent']['node_number'] if node['parent'] else None\n",
    "        path.append((node['state'], node['move'], node['node_number'], parent_node_number))\n",
    "        node = node['parent']\n",
    "\n",
    "    return path[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_paths(node_forward, node_backward):\n",
    "    path_forward = build_path_bidirectional(node_forward)\n",
    "    path_backward = build_path_bidirectional(node_backward)\n",
    "    return path_forward[:-1] + path_backward[::-1]  # Remove duplicate meeting state and reverse backward path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "def expand_bidirectional(node, board_side):\n",
    "    global node_counter\n",
    "    neighbors = []\n",
    "    index = node['state'].index(0)\n",
    "    moves = [('left', -1), ('up', -board_side), ('right', 1), ('down', board_side)]\n",
    "\n",
    "    for m, offset in moves:\n",
    "        new_index = index + offset\n",
    "        if 0 <= new_index < len(node['state']) and (index % board_side != 0 or m != 'left') and ((index + 1) % board_side != 0 or m != 'right'):\n",
    "            new_state = node['state'][:]\n",
    "            new_state[index], new_state[new_index] = new_state[new_index], new_state[index]\n",
    "            node_counter += 1\n",
    "            neighbors.append({\n",
    "                'state': new_state,\n",
    "                'parent': node,\n",
    "                'move': m,\n",
    "                'depth': node['depth'] + 1,\n",
    "                'node_number': node_counter\n",
    "            })\n",
    "\n",
    "    return neighbors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bidirectional_search(initial_state):\n",
    "    goal_state = [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
    "    board_side = int(len(initial_state) ** 0.5)\n",
    "\n",
    "    node_counter = 0\n",
    "    start_node = {'state': initial_state, 'parent': None, 'move': None, 'depth': 0, 'node_number': node_counter}\n",
    "    goal_node = {'state': goal_state, 'parent': None, 'move': None, 'depth': 0, 'node_number': node_counter}\n",
    "\n",
    "    if initial_state == goal_state:\n",
    "        return build_path_bidirectional(start_node), 0\n",
    "\n",
    "    frontier_forward = [start_node]\n",
    "    frontier_backward = [goal_node]\n",
    "    explored_forward = set()\n",
    "    explored_backward = set()\n",
    "\n",
    "    while frontier_forward and frontier_backward:\n",
    "        # Forward search\n",
    "        current_node_forward = frontier_forward.pop(0)\n",
    "        explored_forward.add(tuple(current_node_forward['state']))\n",
    "\n",
    "        # Backward search\n",
    "        current_node_backward = frontier_backward.pop(0)\n",
    "        explored_backward.add(tuple(current_node_backward['state']))\n",
    "\n",
    "        # Check for meeting point\n",
    "        if tuple(current_node_forward['state']) in explored_backward or tuple(current_node_backward['state']) in explored_forward:\n",
    "            # Merge paths\n",
    "            return merge_paths(current_node_forward, current_node_backward), current_node_forward['depth'] + current_node_backward['depth']\n",
    "\n",
    "        # Expand nodes in forward direction\n",
    "        for neighbor in expand_bidirectional(current_node_forward, board_side):\n",
    "            if tuple(neighbor['state']) not in explored_forward:\n",
    "                frontier_forward.append(neighbor)\n",
    "\n",
    "        # Expand nodes in backward direction\n",
    "        for neighbor in expand_bidirectional(current_node_backward, board_side):\n",
    "            if tuple(neighbor['state']) not in explored_backward:\n",
    "                frontier_backward.append(neighbor)\n",
    "\n",
    "    return None, None\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Input Related Functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_solvable(state):\n",
    "    \n",
    "    inversions = 0\n",
    "    for i in range(len(state)):\n",
    "        for j in range(i + 1, len(state)):\n",
    "            if state[i] > state[j] != 0:\n",
    "                inversions += 1\n",
    "\n",
    "    return inversions % 2 == 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "def move_tile(state, direction):\n",
    "    new_state = list(state)\n",
    "    index = new_state.index(0)\n",
    "    \n",
    "    if direction == 'up' and index >= 3:\n",
    "        new_state[index], new_state[index - 3] = new_state[index - 3], new_state[index]\n",
    "    elif direction == 'down' and index <= 5:\n",
    "        new_state[index], new_state[index + 3] = new_state[index + 3], new_state[index]\n",
    "    elif direction == 'left' and index % 3 != 0:\n",
    "        new_state[index], new_state[index - 1] = new_state[index - 1], new_state[index]\n",
    "    elif direction == 'right' and index % 3 != 2:\n",
    "        new_state[index], new_state[index + 1] = new_state[index + 1], new_state[index]\n",
    "    \n",
    "    return new_state\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_random_puzzle(moves=100):\n",
    "    state = [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
    "    directions = ['up', 'down', 'left', 'right']\n",
    "    for _ in range(moves):\n",
    "        state = move_tile(state, random.choice(directions))\n",
    "    return state\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_initial_state_from_user():\n",
    "    while True:\n",
    "        try:\n",
    "            # Ask the user to input the initial state\n",
    "            user_input = input(\"Enter the initial state of the 8-puzzle as a list of numbers from 0 to 8 (e.g., 1 2 3 4 5 6 7 8 0), or type 'exit' to stop: \")\n",
    "            if user_input.lower() == 'exit':\n",
    "                print(\"Program exited by user.\")\n",
    "                exit()\n",
    "\n",
    "            initial_state = [int(num) for num in user_input.split()]\n",
    "\n",
    "            # Check if the input is valid\n",
    "            if sorted(initial_state) == list(range(9)):\n",
    "                return initial_state\n",
    "            else:\n",
    "                print(\"Invalid input. Please enter a list of numbers from 0 to 8 with no duplicates.\")\n",
    "        except ValueError:\n",
    "            print(\"Invalid input. Please enter numbers only.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Main"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Using the generate_random_puzzle function to create an initial state\n",
    "initial_state = generate_random_puzzle()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Node Number: 0, Parent Node: None\n",
      "State: [0, 6, 2, 4, 3, 5, 1, 7, 8]\n",
      "Move: None\n",
      "**********\n",
      "Node Number: 467, Parent Node: 0\n",
      "State: [6, 0, 2, 4, 3, 5, 1, 7, 8]\n",
      "Move: right\n",
      "**********\n",
      "Node Number: 471, Parent Node: 467\n",
      "State: [6, 3, 2, 4, 0, 5, 1, 7, 8]\n",
      "Move: down\n",
      "**********\n",
      "Node Number: 1195, Parent Node: 471\n",
      "State: [6, 3, 2, 0, 4, 5, 1, 7, 8]\n",
      "Move: left\n",
      "**********\n",
      "Node Number: 1201, Parent Node: 1195\n",
      "State: [6, 3, 2, 1, 4, 5, 0, 7, 8]\n",
      "Move: down\n",
      "**********\n",
      "Node Number: 1549, Parent Node: 1201\n",
      "State: [6, 3, 2, 1, 4, 5, 7, 0, 8]\n",
      "Move: right\n",
      "**********\n",
      "Node Number: 1620, Parent Node: 1549\n",
      "State: [6, 3, 2, 1, 0, 5, 7, 4, 8]\n",
      "Move: up\n",
      "**********\n",
      "Node Number: 1639, Parent Node: 1620\n",
      "State: [6, 3, 2, 0, 1, 5, 7, 4, 8]\n",
      "Move: left\n",
      "**********\n",
      "Node Number: 1643, Parent Node: 1639\n",
      "State: [0, 3, 2, 6, 1, 5, 7, 4, 8]\n",
      "Move: up\n",
      "**********\n",
      "Node Number: 1646, Parent Node: 1643\n",
      "State: [3, 0, 2, 6, 1, 5, 7, 4, 8]\n",
      "Move: right\n",
      "**********\n",
      "Node Number: 1650, Parent Node: 1646\n",
      "State: [3, 1, 2, 6, 0, 5, 7, 4, 8]\n",
      "Move: down\n",
      "**********\n",
      "Node Number: 1654, Parent Node: 1650\n",
      "State: [3, 1, 2, 6, 4, 5, 7, 0, 8]\n",
      "Move: down\n",
      "**********\n",
      "Node Number: 1655, Parent Node: 1654\n",
      "State: [3, 1, 2, 6, 4, 5, 0, 7, 8]\n",
      "Move: left\n",
      "**********\n",
      "Node Number: 1658, Parent Node: 1655\n",
      "State: [3, 1, 2, 0, 4, 5, 6, 7, 8]\n",
      "Move: up\n",
      "**********\n",
      "Node Number: 1660, Parent Node: 1658\n",
      "State: [0, 1, 2, 3, 4, 5, 6, 7, 8]\n",
      "Move: up\n",
      "**********\n",
      "Depth: 14\n"
     ]
    }
   ],
   "source": [
    "\n",
    "# Check if the initial state is solvable\n",
    "if not is_solvable(initial_state):\n",
    "    print(\"The initial state is not solvable.\")\n",
    "else:\n",
    "    # Solve the 8-puzzle\n",
    "    path, depth = ida_star_solve(initial_state)\n",
    "    \n",
    "    # Check if a solution was found\n",
    "    if path:\n",
    "        # Print the solution path, depth, and parent node numbers\n",
    "        for state, move, node_number, parent_node_number in path:\n",
    "            print(f'Node Number: {node_number}, Parent Node: {parent_node_number}')\n",
    "            print('State:', state)\n",
    "            print('Move:', move)\n",
    "            print('*'*10)\n",
    "        print('Depth:', depth)\n",
    "    else:\n",
    "        print(\"No solution found.\")\n"
   ]
  }
 ],
 "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.12.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}