Module $5$ Homework $-$ Recursion

Use recursion to determine if a knight starting in a given square on a chessboard can capture all pawns on that board using only moves that capture a pawn $($moves to spaces without a pawn, or spaces with pawns that have already been captured, are not allowed$).$

Consider an $8$x$8$ chessboard with a knight and some pawns:$$# $01234567$

#$0--------$ Row $0$: $(0,0),(0,1),(0,2),...(0,7)$ #$1---$ p $----$

#$2-$ p $---$ p $--$

#$3---$ k $----$

#$4--$ p $-----$

#$5-----$ p $--$

#$6---$ p $----$

#$7--------$Row $7$: $(7,0),(7,1),(7,2),...(7,7)$

k$\_$idx $=(3,3)$

p$\_$idxs $=\{(1,3),(2,1),(2,5),(4,2),(5,5),(6,3)\}$

# Initial knight index

# Set of pawn indices

This board is solveable. Our knight can capture all $6$ pawns with $6$ consecutive moves:

$(2,5),(1,3),(2,1),(4,2),(6,3),(5,5)$ However, the following board is not solveable:$$# $01234567$

#$0--------$ Row $0$: $(0,0),(0,1),(0,2),...(0,7)$ #$1--------$

#$2-$ p $---$ p $--$

#$3---$ k $----$

#$4--$ p $-----$

#$5-----$ p $--$

#$6---$ p $----$

#$7--------$Row $7$: $(7,0),(7,1),(7,2),...(7,7)$

k$\_$idx $=(3,3)$ # Initial knight index p$\_$idxs $=\{(2,1),(2,5),(4,2),(5,5),(6,3)\}$ # Set of pawn indices

There is no way for our knight to capture all $5$ pawns in just $5$ moves.

Deliverables

$1)$ Write Unittests

Use TDD on this assignment$-$ write a test, run it$,$ then implement functionality. You will be graded on your tests. Starter code for TestHw$5.$py includes some guidance on tests. Do not use the examples above as boards in your tests.

There are no $($visible$)$ autograder tests on this assignment. We have a few hidden tests to help speed up manual grading, but they will not directly impact your grade.

$1$

$2)$ Implment valid$\_$moves$($k$\_$idx$)$

valid$\_$moves$($k$\_$idx$)$ returns a set of tuples representing all valid moves for a knight at k$\_$idx.

$3)$ Implement solveable$($p$\_$idxs, k$\_$idx$)$:

$$ p$\_$idxs $-$ a set of tuples representing pawn locations

$$ k$\_$idx $-$ a tuple representing the starting position of a knight

$$ Return a boolean denoting whether the passed in p$\_$idxs and k$\_$idx represent a solveable board

Submission

At a minimum, submit the following files: $$ TestHw$5.$py

$$ hw$5.$py

Students must submit individually by the due date $($typically Tuesday at $11$:$59$ pm EST$)$ to receive credit.

Grading

This homework is $100\%$ manually graded.

Feedback

If you have any feedback on this assignment, please leave it here.

$2$