7.24 Python - Just Code Answers

1.24 (AI Project: Introducing Heuristic Programming with the Knight's Tour) An in- teresting puzzler for chess buffs is the Knight's Tour problem, originally proposed by the mathematician Euler. Can the knight piece move around an empty chessboard and touch each of the 64 squares once and only once? We study this intriguing problem in depth here. The knight makes only L-shaped moves (two spaces in one direction and one space in a perpendicular direction). Thus, as shown in the figure below, from a square near the middle of an empty chessboard, the knight (labeled K) can make eight different moves (numbered 0 through 7). 0 1 2 3 4 5 6 7 O - 2. 1 2 3 0 3 K 4 4 7 5 5 6 6 7 Array-Oriented Programming with Nul this close to your estimate? a) Draw an eight-by-eight chessboard on a sheet of paper, and attempt a Knight's Tour by hand. Put a 1 in the scarting square, a 2 in the second square, 1 3 in the remembering that a full tour consists of 64 moves. How far did you get: Was third, and so on. Before starting the tour, estimate how far you think you'll get b) Now let's develop a script that will move che knight around a chessboard resented by an eight-by-eight two-dimensional array named board. Initialize each square to zero. We describe each of the eight possible moves in terms of its horizontal and vertical components. For example, a move of type 0, as the right and one square vertically upward. A move of type 2 consists of moving shown in the preceding figure, consists of moving two squares horizontally to tal moves to the left and vertical moves upward are indicated with negative one square horizontally to the left and two squares vertically upward. Horizon- numbers. The eight moves may be described by two one-dimensional arrays, horizontal and vertical, as follows: horizonta7[0] = 2 vertica7[0] = -1 horizontal[1] = 1 vertical[1] = -2 horizontal[2] = -1 vertical[2] = -2 horizontal[3] = -2 vertical[3] = -1 horizontal [4] = -2 vertical[4] = 1 horizontal[5] = -1 vertical[5] = 2 horizontal[6] = 1 vertical[6] = 2 horizontal[7] = 2 vertical[7] = 1 Let the variables current_row and current_column indicate the row and column, respectively, of the knight's current position. To make a move of type move_number (a value 0-7), your scripe should use the statements current_row += vertical[move_number] current_column += horizontal[move_number] Write a script to move the knight around the chessboard. Keep a counter that varies from 1 to 64. Record the latest count in each square the knight moves to. Test each potential move to see if the knight has already visited that square. Test every potential move to ensure that the knight does not land off the chessboard. Run the application. How many moves did the knight make? c) After attempting to write and run a Knight's Tour script, you've probably developed some valuable insights. We'll use these insights to develop a heuristic 6.e., a common-sense rule) for moving the knight. Heuristics do not guarantee success , but a carefully developed heuristic greatly improves the chance of suc- cess. You may have observed that the outer squares are more troublesome than the squares nearer the center of the board. In fact, the most troublesome or in- accessible squares are the four corners. Intuition may suggest that you should attempt to move the knight to the that when the board gets congested near the end of the tour, there will be a most troublesome squares first and leave open those that are easiest to get to so greater chance of success. squares according to how accessible it is and always moving the knight (using We could develop an "accessibility heuristic" by classifying each of the the knight's L-shaped moves to the most inaccessible square. We fill two- dimensional array accessibility with numbers indicating from how many accessible. On a blank chessboard, each of the 16 squares nearest the center is rated as 8, each corner square is rated as 2, and the other squares have accessibility numbers of 3, 4 or 6 as follows: squares each particular square Nm 4 4 4 4 3 2 3 4 6 6 6 6 4 3 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 AO OO OO OO O A WA O O O O AW 2 3 4 4 4 4 3 2 Write a new version of the Knight's Tour, using the accessibility heuristic. The knight should always move to the square with the lowest accessibility number. In case of a tie, the knight may move to any of the tied squares. Therefore, the tour may begin in any of the four corners. [Note: As the knight moves around the chessboard, your application should reduce the accessibility numbers as more squares become occupied. In this way, at any given time during the tour, each available square's accessibility number will remain equal to precisely the number of squares from which that square may be reached.] Run this version of your script. Did you get a full tour? Modify the script to run 64 tours, one starting from each square of the chessboard. How many full tours did you get? 1.24 (AI Project: Introducing Heuristic Programming with the Knight's Tour) An in- teresting puzzler for chess buffs is the Knight's Tour problem, originally proposed by the mathematician Euler. Can the knight piece move around an empty chessboard and touch each of the 64 squares once and only once? We study this intriguing problem in depth here. The knight makes only L-shaped moves (two spaces in one direction and one space in a perpendicular direction). Thus, as shown in the figure below, from a square near the middle of an empty chessboard, the knight (labeled K) can make eight different moves (numbered 0 through 7). 0 1 2 3 4 5 6 7 O - 2. 1 2 3 0 3 K 4 4 7 5 5 6 6 7 Array-Oriented Programming with Nul this close to your estimate? a) Draw an eight-by-eight chessboard on a sheet of paper, and attempt a Knight's Tour by hand. Put a 1 in the scarting square, a 2 in the second square, 1 3 in the remembering that a full tour consists of 64 moves. How far did you get: Was third, and so on. Before starting the tour, estimate how far you think you'll get b) Now let's develop a script that will move che knight around a chessboard resented by an eight-by-eight two-dimensional array named board. Initialize each square to zero. We describe each of the eight possible moves in terms of its horizontal and vertical components. For example, a move of type 0, as the right and one square vertically upward. A move of type 2 consists of moving shown in the preceding figure, consists of moving two squares horizontally to tal moves to the left and vertical moves upward are indicated with negative one square horizontally to the left and two squares vertically upward. Horizon- numbers. The eight moves may be described by two one-dimensional arrays, horizontal and vertical, as follows: horizonta7[0] = 2 vertica7[0] = -1 horizontal[1] = 1 vertical[1] = -2 horizontal[2] = -1 vertical[2] = -2 horizontal[3] = -2 vertical[3] = -1 horizontal [4] = -2 vertical[4] = 1 horizontal[5] = -1 vertical[5] = 2 horizontal[6] = 1 vertical[6] = 2 horizontal[7] = 2 vertical[7] = 1 Let the variables current_row and current_column indicate the row and column, respectively, of the knight's current position. To make a move of type move_number (a value 0-7), your scripe should use the statements current_row += vertical[move_number] current_column += horizontal[move_number] Write a script to move the knight around the chessboard. Keep a counter that varies from 1 to 64. Record the latest count in each square the knight moves to. Test each potential move to see if the knight has already visited that square. Test every potential move to ensure that the knight does not land off the chessboard. Run the application. How many moves did the knight make? c) After attempting to write and run a Knight's Tour script, you've probably developed some valuable insights. We'll use these insights to develop a heuristic 6.e., a common-sense rule) for moving the knight. Heuristics do not guarantee success , but a carefully developed heuristic greatly improves the chance of suc- cess. You may have observed that the outer squares are more troublesome than the squares nearer the center of the board. In fact, the most troublesome or in- accessible squares are the four corners. Intuition may suggest that you should attempt to move the knight to the that when the board gets congested near the end of the tour, there will be a most troublesome squares first and leave open those that are easiest to get to so greater chance of success. squares according to how accessible it is and always moving the knight (using We could develop an "accessibility heuristic" by classifying each of the the knight's L-shaped moves to the most inaccessible square. We fill two- dimensional array accessibility with numbers indicating from how many accessible. On a blank chessboard, each of the 16 squares nearest the center is rated as 8, each corner square is rated as 2, and the other squares have accessibility numbers of 3, 4 or 6 as follows: squares each particular square Nm 4 4 4 4 3 2 3 4 6 6 6 6 4 3 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 AO OO OO OO O A WA O O O O AW 2 3 4 4 4 4 3 2 Write a new version of the Knight's Tour, using the accessibility heuristic. The knight should always move to the square with the lowest accessibility number. In case of a tie, the knight may move to any of the tied squares. Therefore, the tour may begin in any of the four corners. [Note: As the knight moves around the chessboard, your application should reduce the accessibility numbers as more squares become occupied. In this way, at any given time during the tour, each available square's accessibility number will remain equal to precisely the number of squares from which that square may be reached.] Run this version of your script. Did you get a full tour? Modify the script to run 64 tours, one starting from each square of the chessboard. How many full tours did you get