$($Challenge problem $-$ to turn in again for homework $3)$ Let kinN be a natural number. Consider a $2^($k$)$ times $2^($k$)$ square board divided into equal square tiles of $1$ times $1$ size, like a chess board. $($So the $2^($k$)$ times $2^($k$)$ board is covered by $2^(2^($k$))$ tiles.$)$ Remove one tile from the $2^($k$)$ times $2^($k$)$ board. Prove using induction that the remaining part of the board can be covered with triomino pieces, i$.$e$.$ pieces made of three unit tiles with an L$-$shape.Task $2.[50$ Points $]$ Superknight's Tour on a $(102^k)(102^k)$ Chessboard

Suppose that you are given an $nn$ chessboard for $n=102^k$ for some integer $k0.$ Each cell is

identified with a pair $(r,c),$ where rin$[1,n]$ is its row number and cin$[1,n]$ is its column number.

A superknight is similar to the standard chess piece called a knight but it makes bigger jumps when

it moves around the chessboard. Indeed, like a standard knight, it moves in an $\text{'}L\text{'}$ shape in any

direction as shown in Figure $2($a$),$ except that a superknight's $\text{'}L\text{'}$ is bigger than a knight's $\text{'}L\text{'}.$

A superknight's tour on a chessboard is a sequence of moves made by the superknight starting from

any cell and touching every other cell exactly once. If the last cell on the tour is reachable from

the first cell in a single move of the superknight, we call the tour closed. Figure $2($b$)$ shows a closed

tour on a $1010$ chessboard. The tour starts from any given cell and moves along the arrows to

land on every other cell exactly once before coming back to the starting cell. Flipping the direction

of every arrow will produce another valid tour but in the opposite direction.

$($a$)[40$ Points $]$ Design and explain a recursive divide$-$and$-$conquer algorithm to find a closed

superknight's tour on an $nn$ chessboard with $n=102^k$ for some integer $k0$ using the

solution to the $1010$ board given in Figure $2(b)$ as the base case. What data structure will

you use to store the final tour as well as all tours computed by your algorithm recursively?

$($b$)[10$ Points $]$ Write down a recurrence relation that describes the running time of your

algorithm from part $($a$),$ and solve it$.$

$($b$)$ A closed superknight's tour on

a $1010$ chessboard