Python 3

Question 6: (9 marks) This question is about backtracking and brute force solutions to problems. For this question we will be considering a variation of the knight's tour problem called the knight-time. This is a 3x3 grid with a black square in the centre and a nyctophobic knight (they are afraid of the dark) must find a path visiting each of the outside squares precisely once. The key point is that the knight can only visit squares as a knight would be able to on a chessboard (see figure 1 below) and the knight must start in the left column (See figures 2a and 2b below) lk lk lk Figure 1: a chessboard showing a knight K and valid moves for that knight* 4 (a) Blank board for knight-time problem (b) knight-time problem with cells labelled with order visited Figure 2: the knight-time problem Figure 1a shows the board as it would be before any solution is found, 1b shows one possible solution where the knight starts at the top left corner and squares are labeled with the order they are visited. This is a solution as all outside squares are used and numbered (a) (2 marks) Describe how you might represent partial solutions in this situation. (b) (4 marks) Draw a backtracking tree for this problem; Note that when you get to the point of only having a single choice in a branch you may write out the full solution for that branch instead Question 6: (9 marks) This question is about backtracking and brute force solutions to problems. For this question we will be considering a variation of the knight's tour problem called the knight-time. This is a 3x3 grid with a black square in the centre and a nyctophobic knight (they are afraid of the dark) must find a path visiting each of the outside squares precisely once. The key point is that the knight can only visit squares as a knight would be able to on a chessboard (see figure 1 below) and the knight must start in the left column (See figures 2a and 2b below) lk lk lk Figure 1: a chessboard showing a knight K and valid moves for that knight* 4 (a) Blank board for knight-time problem (b) knight-time problem with cells labelled with order visited Figure 2: the knight-time problem Figure 1a shows the board as it would be before any solution is found, 1b shows one possible solution where the knight starts at the top left corner and squares are labeled with the order they are visited. This is a solution as all outside squares are used and numbered (a) (2 marks) Describe how you might represent partial solutions in this situation. (b) (4 marks) Draw a backtracking tree for this problem; Note that when you get to the point of only having a single choice in a branch you may write out the full solution for that branch instead