<kaggle_start><code># # 8 Puzzle Problem
# BMS College of Engineering - Dr Kavitha Sooda
# BMS College of Engineering - Dr Nagarathna N
# BMS College of Engineering - Prof G R Asha
# ##### Class 5C
# ## Objective
# Given a 3×3 board with 8 tiles and one empty space
# - Move the numbers around to match the final configuration using the empty spot
# - You can slide the numbers from above, below, left and right tiles into the empty space.
# ![](https://media.geeksforgeeks.org/wp-content/uploads/puzzle8init.jpg)
# # Use A* Algorithm
# ![](https://media.geeksforgeeks.org/wp-content/uploads/puzzle-1.jpg)
# ## 1. Create the function that finds us the total estimated cost of path through node n - F(n)
# - Create a way to find cost so far to reach node n - G(n)
# - Create a heuristic function to estimate cost from n to goal - H(n)
def G_n(state):
    # Note: You can skip this step if you feel you have a better way of getting G(n)
    pass


def H_n(state, target, g):
    cost = 0
    for i in state:
        d1, d2 = state.index(i), target.index(i)
        p, q = d1 % 3, d1 // 3
        x, y = d2 % 3, d2 // 3
        cost += abs(p - x) + abs(q - y)
    return cost + g


def F_n(poss_moves, target, g):  # Fill inputs as necessary
    return [
        sorted([(i, H_n(i, target, g)) for i in poss_moves], key=lambda x: x[1])[0][0]
    ]


# ## 2. Create a Search function
# ### To traverse across the tree using F(n) to select the next node
# 1. Make sure it to discard visited sites
# 2. Create possible moves function
# 3. Create move generator function
#
def astar(state, target):  # Add inputs if more are required
    visited_states = []
    visited_states.append(src)
    g = 0
    arr = [src]
    c = 0
    while arr:
        c += 1  # Calculate Number of Iterations                                   # Print current state to check
        if arr[0] == target:  # break if target found
            return True
        arr += F_n(
            possible_moves(arr[0], visited_states), target, g
        )  # else Add all possible moves to arr
        visited_states.append(arr[0])
        print("Level {} : {}".format(g, arr[0]))
        arr.pop(0)  # remove checked move from arr
        g += 1
    return False


def possible_moves(state, visited_states):  # Add inputs if more are required
    ind = state.index(-1)
    d = []
    if ind + 3 in range(9):
        d.append("d")
    if ind - 3 in range(9):
        d.append("u")
    if ind not in [0, 3, 6]:
        d.append("l")
    if ind not in [2, 5, 8]:
        d.append("r")
    pos_moves = []
    for move in d:
        pos_moves.append(gen(state, move, ind))
    return [move for move in pos_moves if move not in visited_states]


def gen(state, direction, b):
    temp = state.copy()
    if direction == "d":
        a = temp[b + 3]
        temp[b + 3] = temp[b]
        temp[b] = a
    elif direction == "u":
        a = temp[b - 3]
        temp[b - 3] = temp[b]
        temp[b] = a
    elif direction == "l":
        a = temp[b - 1]
        temp[b - 1] = temp[b]
        temp[b] = a
    elif direction == "r":
        a = temp[b + 1]
        temp[b + 1] = temp[b]
        temp[b] = a
    return temp


# Test 1
src = [1, 2, 3, -1, 4, 5, 6, 7, 8]
target = [1, 2, 3, 4, 5, -1, 6, 7, 8]
astar(src, target)
# Test 2
src = [1, 2, 3, -1, 4, 5, 6, 7, 8]
target = [1, 2, 3, 6, 4, 5, -1, 7, 8]
astar(src, target)
# # Test 3
# src = [1,2,3,7,4,5,6,-1,8]
# target=[1,2,3,6,4,5,-1,7,8]
# astar(src, target)
<|endoftext|>
[{"Id": 45013469, "ScriptId": 12365973, "ParentScriptVersionId": NaN, "ScriptLanguageId": 9, "AuthorUserId": 5817315, "CreationDate": "10/19/2020 05:15:12", "VersionNumber": 1.0, "Title": "AI - Lab Program 4", "EvaluationDate": "10/19/2020", "IsChange": true, "TotalLines": 121.0, "LinesInsertedFromPrevious": 63.0, "LinesChangedFromPrevious": 0.0, "LinesUnchangedFromPrevious": 58.0, "LinesInsertedFromFork": 63.0, "LinesDeletedFromFork": 14.0, "LinesChangedFromFork": 0.0, "LinesUnchangedFromFork": 58.0, "TotalVotes": 0}]
# # 8 Puzzle Problem
# BMS College of Engineering - Dr Kavitha Sooda
# BMS College of Engineering - Dr Nagarathna N
# BMS College of Engineering - Prof G R Asha
# ##### Class 5C
# ## Objective
# Given a 3×3 board with 8 tiles and one empty space
# - Move the numbers around to match the final configuration using the empty spot
# - You can slide the numbers from above, below, left and right tiles into the empty space.
# ![](https://media.geeksforgeeks.org/wp-content/uploads/puzzle8init.jpg)
# # Use A* Algorithm
# ![](https://media.geeksforgeeks.org/wp-content/uploads/puzzle-1.jpg)
# ## 1. Create the function that finds us the total estimated cost of path through node n - F(n)
# - Create a way to find cost so far to reach node n - G(n)
# - Create a heuristic function to estimate cost from n to goal - H(n)
def G_n(state):
    # Note: You can skip this step if you feel you have a better way of getting G(n)
    pass


def H_n(state, target, g):
    cost = 0
    for i in state:
        d1, d2 = state.index(i), target.index(i)
        p, q = d1 % 3, d1 // 3
        x, y = d2 % 3, d2 // 3
        cost += abs(p - x) + abs(q - y)
    return cost + g


def F_n(poss_moves, target, g):  # Fill inputs as necessary
    return [
        sorted([(i, H_n(i, target, g)) for i in poss_moves], key=lambda x: x[1])[0][0]
    ]


# ## 2. Create a Search function
# ### To traverse across the tree using F(n) to select the next node
# 1. Make sure it to discard visited sites
# 2. Create possible moves function
# 3. Create move generator function
#
def astar(state, target):  # Add inputs if more are required
    visited_states = []
    visited_states.append(src)
    g = 0
    arr = [src]
    c = 0
    while arr:
        c += 1  # Calculate Number of Iterations                                   # Print current state to check
        if arr[0] == target:  # break if target found
            return True
        arr += F_n(
            possible_moves(arr[0], visited_states), target, g
        )  # else Add all possible moves to arr
        visited_states.append(arr[0])
        print("Level {} : {}".format(g, arr[0]))
        arr.pop(0)  # remove checked move from arr
        g += 1
    return False


def possible_moves(state, visited_states):  # Add inputs if more are required
    ind = state.index(-1)
    d = []
    if ind + 3 in range(9):
        d.append("d")
    if ind - 3 in range(9):
        d.append("u")
    if ind not in [0, 3, 6]:
        d.append("l")
    if ind not in [2, 5, 8]:
        d.append("r")
    pos_moves = []
    for move in d:
        pos_moves.append(gen(state, move, ind))
    return [move for move in pos_moves if move not in visited_states]


def gen(state, direction, b):
    temp = state.copy()
    if direction == "d":
        a = temp[b + 3]
        temp[b + 3] = temp[b]
        temp[b] = a
    elif direction == "u":
        a = temp[b - 3]
        temp[b - 3] = temp[b]
        temp[b] = a
    elif direction == "l":
        a = temp[b - 1]
        temp[b - 1] = temp[b]
        temp[b] = a
    elif direction == "r":
        a = temp[b + 1]
        temp[b + 1] = temp[b]
        temp[b] = a
    return temp


# Test 1
src = [1, 2, 3, -1, 4, 5, 6, 7, 8]
target = [1, 2, 3, 4, 5, -1, 6, 7, 8]
astar(src, target)
# Test 2
src = [1, 2, 3, -1, 4, 5, 6, 7, 8]
target = [1, 2, 3, 6, 4, 5, -1, 7, 8]
astar(src, target)
# # Test 3
# src = [1,2,3,7,4,5,6,-1,8]
# target=[1,2,3,6,4,5,-1,7,8]
# astar(src, target)
