API tools faq
paste
KDT85

8 puzzle

KDT85
Nov 16th, 2023
826
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 9.91 KB | None | 0 0
raw download clone embed print report
  1.  
  2. from string import printable
  3.  
  4.  
  5. start_state = [
  6.     ['1', '2', '3'],
  7.     ['7', '8', '4'],
  8.     ['_', '6', '5']
  9.     ]
  10. goal_state = [
  11.     ['1', '2', '3'],
  12.     ['4', '5', '6'],
  13.     ['7', '8', '_']
  14.     ]
  15.  
  16. """ the total manhatten distance for the starting state is
  17. 1+1+2+2+2 = 8
  18.  
  19. currint blank posistion = (2,0)
  20.  
  21.    ['1', '2', '3']
  22.    ['_', '8', '4'] = 1+2+2+2 = 7
  23.    ['7', '6', '5']
  24.  
  25.    ['1', '2', '3']
  26.    ['7', '8', '4'] = 1+1+2+3+2 = 9
  27.    ['6', '_', '5']
  28.  
  29.    
  30.  
  31. there for the first child state is the best
  32.  
  33. """
  34.  
  35. def print_board(given_state):
  36.     for i in range(3):
  37.         for j in range(3):
  38.             print(f"|{given_state[i][j]}", end='')
  39.  
  40.         print('|')
  41.  
  42. def calculate_manhattan_distance(node, given_state, goal_state):
  43.     # calculate h score / manhattan distance
  44.     #print(f"{given_state = }")
  45.     distance =  0
  46.     start_position = 0
  47.     final_position = 0
  48.  
  49.     for i in range(3):
  50.         for j in range(3):
  51.             if node == given_state[i][j]:
  52.                 start_position = (i, j)
  53.                 #print(start_position)
  54.             if node == goal_state[i][j]:
  55.                 final_position = (i,j)
  56.                 #print(f"{final_position = }")
  57.                 #print(f"{final_position[0] = }")
  58.     distance =+ abs(final_position[0] - start_position[0]) + abs(final_position[1] - start_position[1])
  59.     print(f"{distance = }")
  60.     return distance
  61.  
  62. def calculate_h_score(given_state):
  63.  
  64.     total = 0
  65.     for i in range(3):
  66.         for j in range(3):
  67.             if given_state[i][j] != '_': # dont calculate the empty space
  68.                 total += calculate_manhattan_distance(given_state[i][j], given_state, goal_state)
  69.     #print(f"{total = }")
  70.     heuristic = (total, given_state)
  71.     print(f"{heuristic = }")
  72.     return heuristic
  73.  
  74. """so far we have calculated the heuristic for a given state
  75.  
  76. next we need to expand the node to see the child nodes
  77.  
  78. we need to figure out where the blank node is and in which directions it can move, excluding any previous states.
  79.  
  80. """
  81.  
  82. def find_space(given_state):
  83.     #figure out where the blank is
  84.     for i in range(3):
  85.         for j in range(3):
  86.             if given_state[i][j] == '_':
  87.                 blank_position = (i, j)
  88.     #print(blank_position)
  89.     return blank_position
  90.  
  91. def possible_moves(blank_position):
  92.  
  93.     viable_moves = []
  94.  
  95.     # is up viable?
  96.     if blank_position[0] - 1 >= 0:
  97.         viable_moves.append('up')
  98.     # down?
  99.     if blank_position[0] + 1 <= 2:
  100.         viable_moves.append('down')
  101.     # left?
  102.     if blank_position[1] - 1 >= 0:
  103.         viable_moves.append('left')
  104.     #right?
  105.     if blank_position[1] + 1 <= 2:
  106.         viable_moves.append('right')
  107.  
  108.     return viable_moves
  109.  
  110.  
  111.  
  112.  
  113.  
  114. # def possible_moves(blank_position, given_state):
  115. #     #trying out dictionary
  116. #     viable_moves = {}
  117.  
  118. #     # is up viable?
  119. #     if blank_position[0] - 1 >= 0:
  120. #         viable_moves['up'] = calculate_h_score(given_state)
  121. #     # down?
  122. #     if blank_position[0] + 1 <= 2:
  123. #         viable_moves['down'] = calculate_h_score(given_state)
  124. #     # left?
  125. #     if blank_position[1] - 1 >= 0:
  126. #         viable_moves['left'] = calculate_h_score(given_state)
  127. #     #right?
  128. #     if blank_position[1] + 1 <= 2:
  129. #         viable_moves['right'] = calculate_h_score(given_state)
  130.  
  131. #     return viable_moves
  132.  
  133. """now we have the possilbe moves we need to move and move and generate a new grid and give each new grid a h score.
  134.  
  135. the h score so far is 0 but on the next level of grids it will increase by our g score.
  136.  
  137. our g score increases each level by one, we add this to the h score of the new grids and pick the one with lowest score to explore next
  138.  
  139. """
  140.  
  141. def generate_next_board(direction, given_state, space):
  142.     target = [9,9]
  143.     temp = []
  144.     #print(f"{direction, given_state, space = }")
  145.     new_state = [sub.copy() for sub in given_state]
  146.     if direction == 'up':
  147.         print("Moved space up")
  148.         #print(space[0] -1)
  149.         target[0] = space[0] -1
  150.         target[1] = space[1]
  151.         #print(space)
  152.         #print(target)
  153.         temp = given_state[target[0]][target[1]]
  154.         #print(f"up temp = {temp}")
  155.         #print(f"{temp = }")
  156.         new_state[target[0]][target[1]] = given_state[space[0]][space[1]]
  157.         new_state[space[0]][space[1]] = temp
  158.     if direction == 'down':
  159.         print("Moved space down")
  160.         target[0] = space[0] +1
  161.         target[1] = space[1]
  162.         #print(space)
  163.         #print(target)
  164.         temp = given_state[target[0]][target[1]]
  165.         #print(f"down temp = {temp}")
  166.         new_state[target[0]][target[1]] = given_state[space[0]][space[1]]
  167.         new_state[space[0]][space[1]] = temp
  168.     if direction == 'left':
  169.         print("Moved space left")
  170.         target[0] = space[0]
  171.         target[1] = space[1] -1
  172.         print(space)
  173.         print(target)
  174.         temp = given_state[target[0]][target[1]]
  175.         #print(f"left temp = {temp}")
  176.         new_state[target[0]][target[1]] = given_state[space[0]][space[1]]
  177.         new_state[space[0]][space[1]] = temp
  178.     if direction == 'right':
  179.         print("Moved space right")
  180.         target[0] = space[0]
  181.         target[1] = space[1] +1
  182.         print(space)
  183.         print(target)
  184.         temp = given_state[target[0]][target[1]]
  185.         #print(f"right temp = {temp}")
  186.         new_state[target[0]][target[1]] = given_state[space[0]][space[1]]
  187.         new_state[space[0]][space[1]] = temp
  188.  
  189.     print_board(new_state)
  190.  
  191.     return new_state
  192.  
  193. ## test cells ##
  194.  
  195. # print_board(start_state)
  196. # space = find_space(start_state)
  197. # print(f"{possible_moves(space) = }")
  198. # moves = possible_moves(space)
  199. # for key, value in moves.items():
  200. #     moves[key] = calculate_h_score(start_state)
  201. #     print(f"{moves[key] = }")
  202. # print(moves)
  203. # child_state = generate_next_board('up', start_state, space)
  204. # print_board(child_state)
  205. #h_score = calculate_h_score(start_state)
  206. #print(f"{h_score = }")
  207.  
  208. """function A*(start, goal)
  209.    closedSet := the empty set    // The set of nodes already evaluated.
  210.    openSet := set containing the initial node // The set of tentative nodes to be evaluated, initially containing the start node
  211.    cameFrom := the empty map    // The map of navigated nodes.
  212.  
  213.    gScore[start] := 0    // Cost from start along best known path.
  214.    // Estimated total cost from start to goal through y.
  215.    fScore[start] := gScore[start] + heuristic_cost_estimate(start, goal)
  216.  
  217.    while openSet is not empty
  218.        current := the node in openSet having the lowest fScore[] value
  219.        if current = goal
  220.            return reconstruct_path(cameFrom, goal)
  221.  
  222.        openSet.Remove(current)
  223.        closedSet.Add(current)
  224.  
  225.        for each neighbor of current
  226.            if neighbor in closedSet
  227.                continue    // Ignore the neighbor which is already evaluated.
  228.  
  229.            tentative_gScore := gScore[current] + dist_between(current, neighbor) // length of this path.
  230.            if neighbor not in openSet    // Discover a new node
  231.                openSet.Add(neighbor)
  232.            else if tentative_gScore >= gScore[neighbor]
  233.                continue    // This is not a better path.
  234.  
  235.            // This path is the best until now. Record it!
  236.            cameFrom[neighbor] := current
  237.            gScore[neighbor] := tentative_gScore
  238.            fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)
  239.  
  240.    return failure
  241.  
  242. """
  243.  
  244. def convert_to_tupple(lis):
  245.     tup = []
  246.     for i in range(3):
  247.  
  248.         inner_tupple = tuple(lis[i])
  249.     tup = tuple(inner_tupple)
  250.     print(tup)
  251.  
  252.     return tup
  253.  
  254. """Put node_start in the OPEN list with f(node_start) = h(node_start) (initialization)
  255.  
  256. while the OPEN list is not empty {
  257.  
  258. Take from the open list the node node_current with the lowest
  259. f(node_current)
  260. =
  261. g(node_current) + h(node_current)
  262.  
  263. if node_current is node_goal we have found the solution; break
  264. Generate each state node_successor that come after node_current
  265. for each node_successor of node_current {
  266. }
  267. }
  268. Set successor_current_cost = g(node_current) + w (node_current, node_successor) if node_successor is in the OPEN list {
  269.  
  270. if g(node_successor) successor_current_cost continue (to line 20)
  271. } else if node_successor is in the CLOSED list {
  272.    
  273. if g(node_successor)
  274. successor_current_cost continue (to line 20)
  275. Move node_successor from the CLOSED list to the OPEN list } else {
  276. Add node_successor to the OPEN list
  277. Set h(node_successor) to be the heuristic distance to node_goal
  278. Set g(node_successor) = successor_current_cost
  279. Set the parent of node_successor to node_current
  280. Add node_current to the CLOSED list
  281. if(node_current != node_goal) exit with error (the OPEN list is empty)
  282. """
  283.  
  284. open_list = []
  285. initial_state = (0, start_state) #give the start state a h score of 0
  286. open_list.append(initial_state)
  287. #print(f"{open_list = }")
  288.  
  289. while open_list:
  290.     #find smallest h_score
  291.     open_list.sort()
  292.     current_state = open_list.pop(0)
  293.     print_board(current_state[1])
  294.     #check if we found thw goal
  295.     if current_state == goal_state:
  296.         print("found it!")
  297.     #find next moves
  298.     space = find_space(current_state[1])
  299.     moves = possible_moves(space)
  300.     print(moves)
  301.     #expand moves
  302.     moves_expanded = []
  303.     #next_state_right = generate_next_board('right', current_state, space)
  304.     #next_state_down = generate_next_board('down', current_state, space)
  305.     #next_state_up = generate_next_board('up', current_state, space)
  306.     for i in range(len(moves)):
  307.          print(f"{moves[i] = }")
  308.  
  309.          moves_expanded.append(generate_next_board(moves[i], current_state[1], space))
  310.  
  311.          print(f"{moves_expanded[i] = }")
  312.     print(f"{moves_expanded = }")
  313.    
  314.     #calculate h_score for each move
  315.     calculated = []
  316.     for i in range(len(moves_expanded)):
  317.         calculated.append(calculate_h_score(moves_expanded[i]))
  318.     print(calculated)
  319.  
  320.     #print("start_state")
  321.     #print_board(start_state)
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!