$(2+2+4+4)$ In this problem we consider the movement of the knight in a game of

chess. If you are unfamiliar with this, please see the reference material for this problem,

Figure $10\mathrm{.}6\mathrm{.}5.$ The knight we are considering is on the standard $88$ chessboard. We

use the standard notation to references the spaces on this board.

For example, a knight located at d$4$ can move to any of the spaces, c$2,$ e$2,$ f$3,$ b$3,$ b$5,$

f$5,$ c$6,$ e$6.$

We may make a graph as follows. The vertices of this graph correspond to the $64$

spaces on the chessboard. Two vertices are connected whenever a knight on one space

may move to the other space. For example we see that there is an edge between $d4$

and $c2.$ Use this graph to answer the following questions.

$($a$)$ Use Matlab to make a vertex matrix for this problem. Discuss how you made

your matrix in Matlab. How do you know your matrix is correct?

When you hand in this matrix, give it the name knight and name your file

Q$3$a$.$mat. Please be sure to do this exactly as described, otherwise the program

which tests your matrix will not be able to execute and you will be given no credit.

$($See Lab $2$ for details.$)$

$($b$)$ Can a knight that begins on b$1,$ after a series of moves, end on c$1?$ If so$,$ what is

the minimum number of moves that this would take? Explain.

$($c$)$ For a knight that begins on b$1$ is there any space on the board that it cannot

occupy after any series of moves?

More generally, for any starting position is there any position to which a knight

cannot move to from there?

$($d$)$ Let the distance between two spaces $x,y$ on the board $($relative to a knight's

travel$)$ be the minimum number of moves for a knight to move from $x$ to $y.$

Starting at b$1,$ which space$($s$)$ is$/$are the "farthest away" from here?

More generally, what is the largest distance between any two spaces on the chess$-$

board for a knight?