Due date: Wednesday, October 1, 2025.

Ex. 1. Search Algorithms

Download the following Python program implementing a grid application with a target and a player:
Grid.py

The module contains an implementation of a class called Grid that stores a 2D table and displays it. A function for the breadth-first search is implemented as model. 

a. Complete the implementation of the functions key_press and neighbors with the other 3 directions. For both of them, use self.rows() and self.cols() to make sure that the player doesn't go outside the table. Add 3 more functions similar to move_up for the other 3 directions. In the function open_window, add the remaining needed keys in the tuple in the for loop containing the function call to the function bind. 

b. Implement two functions  depth_first(self) and astar(self). Add corresponding buttons to the interface in the function open_window.

The depth-first search has the following outline:

depth_first_search(origin):
    flag(origin)
    if origin is target: return success
    for child in neighbors(origin):
        if child is not flagged:
            parent(child) = origin
            flag(child)
            if depth_first_search(child): return success
    return failure

You will need the function depth_first(self) to be a wrapper function around a recursive function with this outline, because functions connected to buttons cannot have extra parameters. Use self.player_pos as the parameter origin in the recursive function. 

The A* algorithm is based on the breadth-first search with the following modifications:

• You should not flag the children before adding them to the queue, nor the origin at the top. Instead, flag the node being removed from the queue (pos). Also, check if the node removed from the queue has been flagged before, and discard it if it has. 
• You need an extra dictionary called cost that contains the number of steps from the player to the target. After setting the parent of a child, you should set its cost as 1 plus the cost of the parent. This is the function g(child).
• Define a function manhattan_dist(self, pos) taking the current position as parameter (this will be the child) and computing the Manhattan distance to the target. This distance is define as the absolute value of the difference in rows of the two positions plus the absolute value of the difference in columns between the positions:
       dist(r₁, c₁, r₂, c₂) = |r₁-r₂| + |c₁-c₂|
  This is the function h(child).
• When inserting the child to the queue, make sure to keep the queue ordered by the value of the function f(n) = g(n) + h(n). You may need to write a separate function for this operation. 

Turn in:

Submit the modified file Grid.py to Canvas, Homework 5.