<jupyter_start><jupyter_text>**8 Puzzle Problem using A* Algorithm** Heuristic Function: Number of Misplaced Tiles<jupyter_code># importing libraries
import numpy as np
import pandas as pd
import copy as cp
# function to find the path
def find_path(state):
  bestsol = np.array([], int).reshape(-1, 9)
  count = len(state) - 1

  while count != -1:
    bestsol = np.insert(bestsol, 0, state[count]['puzzle'], 0)
    count = (state[count]['parent'])
    
  return bestsol
# function to find the value of h
def find_h(puzzle, goal):
  mscost = np.sum(puzzle != goal) - 1
  return mscost if mscost > 0 else 0
# function to find the co-ordinates of each value in a state
def find_coordinates(puzzle):
  pos = np.array(range(9))

  for p, q in enumerate(puzzle):
    pos[q] = p
    
  return pos
# find the solution using A* algorithm
def find_solution(initialState, goalState):
  steps = np.array([('up', [0, 1, 2], -3), ('down', [6, 7, 8], 3), \
                    ('left', [0, 3, 6], -1), ('right', [2, 5, 8], 1)],
                  dtype=[('move', str, 1), ('position', list), ('head', int)])
  dtstate = [('puzzle', list), ('parent', int), ('gn', int), ('hn', int)]
  goalCoordinates = find_coordinates(goalState)

  # initializing the parent, gn and hn, where hn is misplaced_tiles
  parent = -1
  gn = 0
  hn = find_h(find_coordinates(initialState), goalCoordinates)
  state = np.array([(initialState, parent, gn, hn)], dtstate)

  # We make use of priority queues with position as keys and fn as value.
  dtpriority = [('position', int), ('fn', int)]
  priority = np.array([(0, hn)], dtpriority)

  while 1:
    priority = np.sort(priority, kind='mergesort', order=['fn', 'position'])
    position, fn = priority[0]

    # sort priority queue using merge sort,the first element is picked for exploring.
    priority = np.delete(priority, 0, 0)
    initialState, parent, gn, hn = state[position]
    initialState = np.array(initialState)

    # Identify the blank square in input
    blank = int(np.where(initialState == 0)[0])

    # Increase cost g(n) by 1
    gn = gn + 1
    c = 1

    for s in steps:
      c = c + 1
      if blank not in s['position']:
        # generate new state as copy of current
        openstates = cp.deepcopy(initialState)
        openstates[blank], openstates[blank + s['head']] = \
        openstates[blank + s['head']], openstates[blank]
        
        # The check function is called, if the node has been previously explored or not.
        if ~(np.all(list(state['puzzle']) == openstates, 1)).any():
          # calls the Misplaced_tiles function to calculate the cost
          hn = find_h(find_coordinates(openstates), goalCoordinates)
          # generate and add new state in the list
          q = np.array([(openstates, position, gn, hn)], dtstate)
          state = np.append(state, q, 0)
          # f(n) is the sum of cost to reach node and the cost to reach from the node to the goal state
          fn = gn + hn
          q = np.array([(len(state) - 1, fn)], dtpriority)
          priority = np.append(priority, q, 0)
          # Checking if the node in openstates are matching the goal state.
          if np.array_equal(openstates, goalState):
            return state
# setting the initial and final state
initialState = np.array([1, 2, 3, 0, 4, 6, 7, 5, 8])
goalState = np.array([1, 2, 3, 4, 5, 6, 7, 8, 0])
solution = find_solution(initialState, goalState)
# displaying the travelled states details as Pandas Dataframe
df = pd.DataFrame(solution)
df.columns = ['state', 'parent', 'g', 'h']
f = []

for i in range(len(solution)):
  f.append(solution[i][-1]+solution[i][-2])
  
df['f'] = f
print(f"{20*'='} Travelled States Details {20*'='}\n")
print(df)
# displaying the solution
bestpath = find_path(solution)
g = []
h = []
f = []

for i in range(len(bestpath)):
  for j in range(len(solution)):
    if np.sum(bestpath[i] == solution[j][0]) == 9:
      g.append(solution[j][-2])
      h.append(solution[j][-1])
      f.append(solution[j][-1]+solution[j][-2])

print(f"\n{20*'='} Solution {20*'='}")

for i in range(len(bestpath)):
  print(f"\nstep {i}: g = {g[i]}, h = {h[i]}, f = {f[i]}\n{bestpath[i].reshape(-1, 3, 3)[0]}")
  
print(f"\n{20*'='} End {20*'='}")<jupyter_output>==================== Solution ====================

step 0: g = 0, h = 3, f = 3
[[1 2 3]
 [0 4 6]
 [7 5 8]]

step 1: g = 1, h = 2, f = 3
[[1 2 3]
 [4 0 6]
 [7 5 8]]

step 2: g = 2, h = 1, f = 3
[[1 2 3]
 [4 5 6]
 [7 0 8]]

step 3: g = 3, h = 0, f = 3
[[1 2 3]
 [4 5 6]
 [7 8 0]]

==================== End ====================
{'fraction_non_alphanumeric': 0.17587719298245613, 'fraction_numerical': 0.03048245614035088, 'mean_word_length': 3.1614963503649633, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '132874', 'license': 'CC0-1.0', 'n_tokens_mistral': 1737, 'n_tokens_neox': 1573, 'n_words': 537, 'path': '8_puzzle_problem_A_star_algorithm.ipynb', 'repo_name': 'ahammedshaneebnk/AI_Search_Algorithms_Exercises', 'size': '4560'}