Q$6.(50$ points$)$

For the $3$ queens problem, how many different arrangements of $3$ queens $($Q$1,$ Q$2,$ Q$3)$ are possible in a $3$ X $3$ chessboard under the following conditions:

Queens in the same rows, columns or diagonals as other queens are considered under attack. The arrangements you are counting should be such that no queens should be under attack.

Q$1$ should be in row $1,$ Q$2$ should be in row $2,$ Q$3$ should be in row $3.$

Derive the arrangement$/$s by drawing a state space tree and illustrating backtracking. Finally list out the arrangements.

For the $5$ queens problem, derive only the first possible arrangement by drawing a state space tree and illustrating backtracking in a $5$ X $5$ chessboard, when Q$1$ starts at column $4.$ Finally list out the arrangement. Q$1$ should be in row $1,$ Q$2$ should be in row $2,$ etc.

Note: The graph $($tree$)$ that we worked on in class, is called the state space tree. The queens can be represented by Q$1,$ Q$2,$ Q$3$ or x$1,$ x$2,$ x$3$