• 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), distance%len(state)
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)):
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)):
88.        goal.append(range(glstcounter, glstcounter + len(state)))
89.        glstcounter += len(state)
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] > pathstorage[j]:
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 + 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, 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