SHARE
TWEET

Untitled

a guest Jan 24th, 2020 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class PuzzleNode:
  2.    def __init__(self, n, state):
  3.        self.n = n
  4.        self.tablesize = n**2
  5.        self.goal = []
  6.        self.state = state
  7.  
  8.    def __str__(self, state):
  9.    #Visualizes the table
  10.        t = " | "
  11.        s = " ----"
  12.        print s * (self.n)
  13.        for i in self.state:
  14.            counter , u = 0, t
  15.            while counter < len(i):
  16.                u += str(i[counter]) + t
  17.                counter += 1
  18.            print u
  19.            print s * (self.n)
  20.  
  21. def place_heuristic(state):
  22.    #A heuristic function which is based on the number of tiles in their misplaced place.
  23.    #It first checks the type of data which the input comes in(string or list of list), and then works with it accordingly.
  24.    if type(state) == str:
  25.        state = eval(state)
  26.    elif type(state) == list:
  27.        pass
  28.  
  29.    # We know an element is misplaced when the index of that element is not equal to that element
  30.    flat_statelist = [item for sublist in state for item in sublist]
  31.    misplacedcounter = 0
  32.    for element in flat_statelist:
  33.        if flat_statelist.index(element) != element:
  34.            misplacedcounter += 1
  35.    return misplacedcounter
  36.  
  37. def Manhattan_heuristic(state):
  38.    #A heuristic function which is based on the manhattan distance of a tile from it's ideal position
  39.    #Again, it first checks the type of data which the input comes in(string or list of list), and then works with it accordingly.
  40.    if type(state) == str:
  41.        state = eval(state)
  42.    elif type(state) == list:
  43.        pass
  44.    flat_statelist = [item for sublist in state for item in sublist]
  45.    flat_goallist = range(0, len(flat_statelist))
  46.    mandistance = 0
  47.  
  48.    #We use it's modular arthmetic to get it's x and y coordinates in the grid. The manhattan distance is the sum of all these x
  49.    #and y coordinates for each of the tiles
  50.    for element in flat_statelist:
  51.        distance = abs(flat_goallist.index(element) - flat_statelist.index(element))
  52.        xcoord, ycoord = distance//len(state[0]), distance%len(state[0])
  53.        mandistance += xcoord + ycoord
  54.    return mandistance
  55.  
  56. def myheuristic(state):
  57.    #This is my attempt at the linear conflict heuristic function. It is a type of heuristic that incorporates the manhattan distance and increases it based
  58.    #on whether or not a condition is satisfied. It's better than the Manhattan heuristic in principle because it incorporates it in it's design, and thus can't be
  59.    #worse than it.
  60.    #Again, it first checks the type of data which the input comes in(string or list of list), and then works with it accordingly.
  61.    if type(state) == str:
  62.        state = eval(state)
  63.    elif type(state) == list:
  64.        pass
  65.    flat_statelist = [item for sublist in state for item in sublist]
  66.    flat_goallist = range(0, len(flat_statelist))
  67.    mydistance = 0
  68.  
  69.    #It checks for two tiles whether or not they are in the same row in the goal state, and the present state, and
  70.    # adds 2 to the manhattan distance if they are across each other as they would have been in the goal state
  71.    for i in range(len(state[0])):
  72.        for j in state[i]:
  73.            for k in state[i]:
  74.                if j and k in goalstate(state)[i] and (flat_goallist.index(j) - flat_statelist.index(j) > 0 and flat_goallist.index(k) - flat_statelist.index(k) < 0) or (flat_goallist.index(j) - flat_statelist.index(j) < 0 and flat_goallist.index(k) - flat_statelist.index(k) > 0):
  75.                    mydistance += 2
  76.    return mydistance/2 + Manhattan_heuristic(state)
  77.  
  78.  
  79. #Creating list heuristics which is a pointer to both heuristics created
  80. heuristics = [place_heuristic, Manhattan_heuristic, myheuristic]
  81.  
  82. def goalstate(state):
  83.    flat_statelist = [item for sublist in state for item in sublist]
  84.    flat_goallist = range(0, len(flat_statelist))
  85.    goal = []
  86.    glstcounter = 0
  87.    for j in range(len(state[0])):
  88.        goal.append(range(glstcounter, glstcounter + len(state[0])))
  89.        glstcounter += len(state[0])
  90.    return goal
  91.  
  92. def moves(inputs, n):
  93.    #Move generator, takes in a state and the different possible next moves
  94.  
  95.    storage  =  []
  96.    inputs = str(inputs)
  97.    move = eval(inputs)
  98.  
  99.    i = 0
  100.    while 0 not in move[i]: i += 1
  101.    j = move[i].index(0);  # blank space (zero)
  102.  
  103.    # Sets boundary for the topmost cells. Allows for downward movement of adjacent cells if they aren't at the topmost edge.
  104.    if i > 0:
  105.        move[i][j], move[i - 1][j] = move[i - 1][j], move[i][j];
  106.        storage.append(str(move))
  107.        move[i][j], move[i - 1][j] = move[i - 1][j], move[i][j];
  108.  
  109.    # Sets boundary for the bottommost cells. Allows for upward movement of adjacent cells if they aren't at the bottommost edge.
  110.    if i < n-1:
  111.        move[i][j], move[i + 1][j] = move[i + 1][j], move[i][j]
  112.        storage.append(str(move))
  113.        move[i][j], move[i + 1][j] = move[i + 1][j], move[i][j]
  114.  
  115.    # Sets boundary for the rightmost cells. Allows for upward movement of adjacent cells if they aren't at the rightmost edge.
  116.    if j > 0:
  117.        move[i][j], move[i][j - 1] = move[i][j - 1], move[i][j]
  118.        storage.append(str(move))
  119.        move[i][j], move[i][j - 1] = move[i][j - 1], move[i][j]
  120.  
  121.    # Sets boundary for the leftmost cells. Allows for upward movement of adjacent cells if they aren't at the leftmost edge.
  122.    if j < n-1:
  123.        move[i][j], move[i][j + 1] = move[i][j + 1], move[i][j]
  124.        storage.append(str(move))
  125.        move[i][j], move[i][j + 1] = move[i][j + 1], move[i][j]
  126.  
  127.    return storage
  128.  
  129. def Astar(start, finish, heuristic):
  130.    #The A star part of the algorithm
  131.    n = len(start)
  132.    start , finish = str(start), str(finish)
  133.    pathstorage = [[heuristic(start), start]]  # optional: heuristic_1
  134.    expanded = []
  135.    expanded_nodes = 0
  136.    while pathstorage:
  137.        i = 0
  138.        for j in range(1, len(pathstorage)):
  139.            if pathstorage[i][0] > pathstorage[j][0]:
  140.                i = j
  141.        path = pathstorage[i]
  142.        pathstorage = pathstorage[:i] + pathstorage[i + 1:]
  143.        finishnode = path[-1]
  144.        if finishnode == finish:
  145.            break
  146.        if finishnode in expanded: continue
  147.        for b in moves(finishnode, n):
  148.            if b in expanded: continue
  149.            newpath = [path[0] + heuristic(b) - heuristic(finishnode)] + path[1:] + [b]
  150.            pathstorage.append(newpath)
  151.            expanded.append(finishnode)
  152.        expanded_nodes += 1
  153.    return expanded_nodes,  len(path), path
  154.  
  155.  
  156. def solvePuzzle(n, state, heuristic, prnt):
  157.    flat_statelist = [item for sublist in state for item in sublist]
  158.    flat_goallist = range(0, len(flat_statelist))
  159.    #Part that returns the error code -1
  160.    #It checks if the length of the input is a perfect square, and then if all the leements int
  161.    #  he goal state is in the start sstate.
  162.    if len(flat_statelist) != n**2:
  163.        steps, frontierSize, err = 0, 0, -1
  164.    elif True in [i not in flat_statelist for i in range(0,n**2-1)]:
  165.        steps, frontierSize, err = 0, 0, -1
  166.    else:
  167.        steps, frontierSize, solutions = Astar(state,goalstate(state), heuristic)
  168.        err = 0
  169.  
  170.    #Prints the solutions if the prnt = True
  171.    if prnt == True:
  172.        for i in solutions[1:]:
  173.            t = PuzzleNode(n, eval(i))
  174.            t.__str__(i)
  175.            print "The next step is :"
  176.  
  177.  
  178.    return "The frontier size, number of steps and error code are :" , steps, frontierSize, err,
  179.  
  180. puzzle =  [[7,0,8],[4,6,1],[5,3,2]]
  181. print solvePuzzle(3, puzzle, heuristics[2], True)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top