TO PREPARE AND SUBMIT HOMEWORK

Follow these steps exactly, so the Gradescope autgrader can grade your homework. Failure to do so will result in a zero grade:

1. You *must* download the homework template file homework3_cmpsc442.py from Canvas. Each  template file is a python file that gives you a headstart in creating your homework python script   with the correct function names for autograding. For this homework (Homework 3), you will also need to download these files from Canvas:

homework3_dominoes_game_gui.py

homework3_grid_navigation_gui.py

homework3_tile_puzzle_gui.py

2. You *must* rename the file by replacing cmpsc442 with your PSU id from your official PSU. For example, if your PSU email id is abcd1234, you would rename your file as                                           homework3_abcd1234.py to submit to Gradescope.

3. Upload your *py file to Gradescope by its due date. It is your responsibility to upload on time.

4. Make sure your file can import before you submit; the autograder imports your file. If it won't import, Gradescope will give you a zero.

Instructions

In this assignment, you will explore a number of games and puzzles from the perspectives of informed and adversarial search.

A skeleton file homework3_cmpsc442.py containing empty definitions for each question has been provided. Since portions of this assignment will be graded automatically, none of the names or     function signatures in this file should be modified. However, you are free to introduce additional  variables or functions if needed.

You may import definitions from any standard Python library, and are encouraged to do so in case you find yourself reinventing the wheel. If you are unsure where to start, consider taking a look at the data structures and functions defined in the collections, itertools, Queue, and random modules.

You will find that in addition to a problem specification, most programming questions also include a  pair of examples from the Python interpreter. These are meant to illustrate typical use cases to clarify the assignment, and are not comprehensive test suites. In addition to performing your own testing,    you are strongly encouraged to verify that your code gives the expected output for these examples       before submitting.

You are strongly encouraged to follow the Python style guidelines set forth in PEP 8, which was written in part by the creator of Python. However, your code will not be graded for style.

1. Tile Puzzle [40 points]

Recall from class that the Eight Puzzle consists of a 3 x 3 board of sliding tiles with a single empty space. For each configuration, the only possible moves are to swap the empty tile with one of its   neighboring tiles. The goal state for the puzzle consists of tiles 1-3 in the top row, tiles 4-6 in the   middle row, and tiles 7 and 8 in the bottom row, with the empty space in the lower-right corner.

In this section, you will develop two solvers for a generalized version of the Eight Puzzle, in which the board can have any number of rows and columns. We have suggested an approach similar to the one used to create a Lights Out solver in Homework 2, and indeed, you may find that this pattern can be  abstracted to cover a wide range of puzzles. If you wish to use the provided GUI for testing, described in more detail at the end of the section, then your implementation must adhere to the recommended interface. However, this is not required, and no penalty will imposed for using a different approach.

A natural representation for this puzzle is a two-dimensional list of integer values between 0 and r · c - 1 (inclusive), where r and c are the number of rows and columns in the board, respectively. In this        problem, we will adhere to the convention that the 0-tile represents the empty space.

1. [o points] In the TilePuzzle class, write an initialization method __init__(self, board)  that stores an input board of this form described above for future use. You additionally may wish to store the dimensions of the board as separate internal variables, as well as the location of the   empty tile.

2. [o points] Suggested infrastructure.

In the TilePuzzle class, write a method get_board(self) that returns the internal representation of the board stored during initialization.

Write a top-level function create_tile_puzzle(rows, cols) that returns a new TilePuzzle of the specified dimensions, initialized to the starting configuration. Tiles 1 through r · c - 1 should be arranged starting from the top-left corner in row-major order, and tile 0 should be     located in the lower-right corner.

In the TilePuzzle class, write a method perform_move(self, direction) that attempts to     swap the empty tile with its neighbor in the indicated direction, where valid inputs are limited to the strings "up", "down", "left", and "right". If the given direction is invalid, or if the move cannot be performed, then no changes to the puzzle should be made. The method should return a Boolean value indicating whether the move was successful.

In the TilePuzzle class, write a method scramble(self, num_moves) which scrambles the    puzzle by calling perform_move(self, direction) the indicated number of times, each time  with a random direction. This method of scrambling guarantees that the resulting configuration will be solvable, which may not be true if the tiles are randomly permuted. Hint: The random module contains afunction random.choice(seq)which returns a random elementfrom its input sequence.

In the TilePuzzle class, write a method is_solved(self) that returns whether the board is in its starting configuration.

In the TilePuzzle class, write a method copy(self) that returns a new TilePuzzle object       initialized with a deep copy of the current board. Changes made to the original puzzle should not be reflected in the copy, and vice versa.

In the TilePuzzle class, write a method successors(self) that yields all successors of the     puzzle as (direction, new-puzzle) tuples. The second element of each successor should be a new TilePuzzle object whose board is the result of applying the corresponding move to the current board. The successors may be generated in whichever order is most convenient, as long as          successors corresponding to unsuccessful moves are not included in the output.

3. [20 points] In the TilePuzzle class, write a method find_solutions_iddfs(self) that          yields all optimal solutions to the current board, represented as lists of moves. Valid moves            include the four strings "up", "down", "left", and "right", where each move indicates a            single swap of the empty tile with its neighbor in the indicated direction. Your solver should be     implemented using an iterative deepening depth-first search, consisting of a series of depth-first  searches limited at first to 0 moves, then 1 move, then 2 moves, and so on. You may assume that  the board is solvable. The order in which the solutions are produced is unimportant, as long as all optimal solutions are present in the output.

Hint: This method is most easily implemented using recursion. First define a recursive helper method idfs_helper(self, limit, moves)that yields all solutions to the current board of length no more than limitwhich are continuations of the provided move list. Your main method will then call this helperfunction in a loop, increasing the depth limit by one at each iteration, until one or more solutions have beenfound.

4. [20 points] In the TilePuzzle class, write a method find_solution_a_star(self) that       returns an optimal solution to the current board, represented as a list of direction strings. If       multiple optimal solutions exist, any of them may be returned. Your solver should be                   implemented as an A* search using the Manhattan distance heuristic, which is reviewed below. You may assume that the board is solvable. During your search, you should take care not to add positions to the queue that have already been visited. It is recommended that you use the            PriorityQueue class from the Queue module.

Recall that the Manhattan distance between two locations (r_1, c_1) and (r_2, c_2) on a board is defined to be the sum of the componentwise distances: |r_1 - r_2 | + |c_1 - c_2 |. The Manhattan distance heuristic for an entire puzzle is then the sum of the Manhattan distances between each   tile and its solved location.

If you implemented the suggested infrastructure described in this section, you can play with an   interactive version of the Tile Puzzle using the provided GUI by running the following command:

The arguments rows and cols are positive integers designating the size of the puzzle.

In the GUI, you can use the arrow keys to perform moves on the puzzle, and can use the side menu to scramble or solve the puzzle. The GUI is merely a wrapper around your implementations of the           relevant functions, and may therefore serve as a useful visual tool for debugging.

2. Grid Navigation [15 points]

In this section, you will investigate the problem of navigation on a two-dimensional grid with          obstacles. The goal is to produce the shortest path between a provided pair of points, taking care to maneuver around the obstacles as needed. Path length is measured in Euclidean distance. Valid      directions of movement include up, down, left, right, up-left, up-right, down-left, and down-right.

Your task is to write a function find_path(start, goal, scene) which returns the shortest path       from the start point to the goal point that avoids traveling through the obstacles in the grid. For this      problem, points will be represented as two-element tuples of the form (row, column), and scenes will    be represented as two-dimensional lists of Boolean values, with False values corresponding empty       spaces and True values corresponding to obstacles. Your output should be the list of points in the          path, and should explicitly include both the start point and the goal point. Your implementation should consist of an A* search using the straight-line Euclidean distance heuristic. If multiple optimal                solutions exist, any of them may be returned. If no optimal solutions exist, or if the start point or goal   point lies on an obstacle, you should return the sentinal value None.

Once you have implemented your solution, you can visualize the paths it produces using the provided GUI by running the following command:

The argument scene_path is a path to a scene file storing the layout of the target grid and obstacles. We use the following format for textual scene representation: "." characters correspond to empty    spaces, and "X" characters correspond to obstacles.