• API
• FAQ
• Tools
• Archive
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.
Top