.py files containing your work.This homework assignment must be submitted in Gradescope by Noon central time on Tuesday February 21, 2023.
Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.
This assignment is about recursion with backtracking. It's a little shorter than usual as I know you're working on Project 2, and this assignment and that project cover some similar ground.
Most relevant:
Less likely to be relevant, but also allowed:
This homework assignment has 3 problems, numbered 2, 3, and 4. The grading breakdown is:
| Points | Item |
|---|---|
| 3 | Autograder |
| 6 | Problem 2 |
| 9 | Total |
The part marked "autograder" reflects points assigned to your submission based on some simple automated checks for Python syntax, etc. The result of these checks is shown immediately after you submit.
Ask your instructor or TA a question by email, in office hours, or on discord.
Like much of worksheet 6, this problem builds on the work we did in solvemaze.py.
Recall our convention is that the solution to a maze is a list of Point2 objects. The length of a solution to the maze is defined as the number of objects in that list. So if the start is at Point2(1,1) and the goal is at the adjacent location Point2(1,2), then the list [Point2(1,1), Point2(1,2)] would be a solution of length 2.
Write a function can_be_solved_maxlen(M,k) that takes a Maze object M, an integer k and returns a boolean value:
True if maze M has a solution of length k or less.False is returned otherwise (i.e. if M has no solution at all, or if all solutions to M have length greater than k).It would be reasonable to use depth_first_maze_solution from solvemaze.py as a starting point for your work, modifying it to do what is needed in this problem.
Put this function in a file called mcs275hwk6.py and upload it. You don't need to upload any other files (e.g. no need to include plane.py or maze.py).
A maze might have multiple solutions. Suppose you find a solution of length 30. There might be another solution of length 22, and so you can't necessarily determine the return value for can_be_solved_maxlen(M,25) on the basis of the length of the first solution that's found.