Modify your program from assignment 1 to use the accessibility heuristic from the PDF linked above (Part C) and to attempt a tour starting from each square on the board. Make sure that you choose the move that targets the square with the lowest accessibility score. Also, be sure to update the accessibility scores for all affected squares after each move.

Please see half of the code below

(C++ Program)

#include #include #include

using namespace std; int main() { int board[8][8] = { 0 };

int moves[8][2] = { {2,-1}, {1,-2}, {-1,-2}, {-2,-1}, {-2,1}, {-1,2}, {1,2}, {2,1} };

int row = 0; int col = 0; int newRow = 0; int newCol = 0; int mover = 1;

setToZero(board);

board[row][col] = 1;

bool possible_to_move = true;

while (possible_to_move) { possible_to_move = false; for (int i = 0; i

if (newRow >= 0 && newRow = 0 && newCol

possible_to_move = true; break;

} } if (possible_to_move) { row = newRow; col = newCol; board[row][col] = ++mover; }

}

int i, j; for (i = 0; i

cin.get(); cin.get(); return 0; }

298 Arrays Chapter 4 Use a 20-by-20 array floor that is initialized to veros. Read commands from an array that contains them. Keep track of the current position of the turtle at all times and whether the pen is cur- rently up or down. Assume that the turtle always starts at position 0,0 of the floor with its pen up, The set of turtle commands your program must process are as follows: Command Meaning 1 1 2 3 4 Pen up Pen down Turn right Turn left Move forward 10 spaces (or a number other than 10) Print the 20-by-20 array End of data (sentinel) 5,10 6 9 Suppose that the turtle is somewhere near the center of the floor. The following "program" would draw and print a 12-by-12 square and end with the pen in the up position: 2 5,12 3 5,12 3 5,12 3 5,12 1 6 9 As the turtle moves with the pen down, set the appropriate elements of array floor to 1's. When the 6 command (print) is given, wherever there is a 1 in the array, display an asterisk or some other character you choose. Wherever there is a zero, display a blank. Write a program to implement the turtle graphics capabilities discussed here. Write several turtle graphics programs to draw interesting shapes. Add other commands to increase the power of your turtle graphics language. 4.24 (Knight's Tour) One of the more interesting puzzlers for chess buffs is the Knight's Tour problem originally proposed by the mathematician Euler. The question is this: Can the chess piece called the knight move around an empty chessboard and touch cach of the 64 squares once and only once? We study this intriguing problem in depth herc. The knight makes L-shaped moves (over two in one direction and then over one in a perpendic- ular direction). Thus, from a square in the middle of an empty chessboard, the knight can make eight different moves (numbered through 7) as shown in Fig. 4.29. a) Draw an 8-by-8 chessboard on a sheet of paper and attempt a Knight's Tour by hand. Put a 1 in the first square you move to a 2 in the second square, a 3 in the third, etc. Before starting the tour, estimate how far you think you will get, remembering that a full tour consists of 64 moves. How far did you get? Was this close to your estimate? b) Now let us develop a program that will move the knight around a chessboard. The board is represented by an 8-by-8 double-subscripted array board. Each of the squares is ini- Chapter 4 Chapter 4 Arrays 299 ids from an array that whether the pen is cur- floor with its pen up. tialized to zero, We describe each of the eight possible moves in terms of both their hor izontal and vertical components. For example, a move of type 0, as shown in Fig. 4.25, consists of moving two squares horizontally to the right and one square vertically up- ward. Move 2 consists of moving one squarc horizontally to the left and two squares ver- tically upward, Horizontal moves to the left and vertical moves upward are indicated with negative numbers. The cight moves may be described by two single-subscripted arrays, horizontal and vertical, as follows: horizontal[ 0 ] - 2 horizontal[ 1 ] = 1 horizontal[ 2 ] = -1 horizontal[ 3 ] = -2 horizontal[ 4 ] = -2 horizontal[ 5 ] = -1 horizontal[ 6 ] - 1 horizontal[ 7 ] = 2 10) following program in: vertical[ 0 ] = -1 vertical[ 1 ] = - vertical[ 2 ] = -2 vertical[ 3 ] = -1 vertical[ 4 ] = 1 vertical[ 5 ] = 2 vertical[ 6 ] = 2 vertical[ 7 ] = 1 Let the variables current Row and currentColumn indicate the row and col- umn of the knight's current position. To make a move of type moveNumber, where moveNumber is between 0 and 7 your program uses the statements 0 1 2 3 4 0 1 2 1 floor to l's. When asterisk or some other ram to implement the ms to draw interesting guage. i is the Knight's Tour s: Can the chess piece squares once and only 2 3 0 3 K 4 4 7 5 5 6 6 er one in a perpendic- knight can make eight ht's Tour by hand. Put the third, etc. Before bering that a full tour estimate? hessboard. The board of the squares is ini- 7 Fig. 4.29 The eight possible moves of the knight. 300 Arrays Chapter 4 current Row + vertical moveNumber : currentColumn += horizontal moveNumber ]; Keep a counter that varies from 1 to 64. Record the latest count in cach square the knight moves to Remember to test each potential move to see if the knight has already visited that square, and, of course, test every potential move to make sure that the knight does not land off the chessboard. Now write a program to move the knight around the chess- board. Run the program. How many moves did the knight make? c) After attempting to write and run a Knight's Tour program, you have probably developed some valuable insights. We will use these to develop a heuristic (or strategy) for moving the knight. Heuristics do not guarantee success, but a carefully developed heuristic great- ly improves the chance of success. You may have observed that the outer squares are more troublesome than the squares nearer the center of the board. In fact, the most trou- blesome, or inaccessible, squares are the four corner's. Intuition may suggest that you should attempt to move the knight to the most trou- blesame squares first and leave open those that are easiest to get to, so when the board gets congested near the end of the tour, there will be a greater chance of success We may develop an "accessibility heuristic" hy classifying each of the squares ac- cording to how accessible they are and then always moving the knight to the square (within the knight's L-shaped moves, of course) that is most inaccessible. We label double-subscripted array accessibility with numbers indicating from how many squares ench particular square is accessible. On a blank chessboard, cach center square 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: 2 3 4 4 4 4 3 2 3 4 6 6 6 6 4 3 4 6 8 8 8 8 6 4 3 4 6 6 6 6 4 3 2 3 4 4 4 4 3 2 Now write a version of the Knight's Tour program using the accessibility heuristic. At any time, the knight should 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 program should reduce the accessibility numbers as more and more squares become oc- cupied. In this way, at any given time during the tour, cach available square's accessibil- ity number will remain equal to precisely the number of squares from which that square may be reached.) Run this version of your program. Did you get a full tour? Now modify the program to run 64 tours, one starting from each square of the chessboard. How many full tours did you get? d) Write a version of the Knight's Tour program which, when encountering a tie between two or more squares, decides what square to choose by looking ahead to those squares reachable from the "tied" squares. Your program should move to the square for which the next move would arrive at a square with the lowest accessibility number. 4.25 (Knight's Tour: Brute Force Approaches) In Exercise 4.24, we developed a solution to the Knight's Tour problem. The approach used, called the accessibility heuristic," generates many so lutions and executes efficiently, AB Chapter 4 Chapter 4 Arrays 301 ach square the knight it has already visited that the knight does ht around the chess- probably developed strategy) for moving oped heuristic greal- he outer syuares are 1 Cact, the most trou- ght to the most trou- I, so when the board re of success. ch of the squares ae- knight to the square cessible. We label a ng from how many 1. each center square s have accessibility As computers continue increasing in power, we will be able to solve more problems with sheer computer power and relatively unsophisticated algorithms. Let us call this approach "brute force" problem solving. a) Use random-number generation to enable the knight to walk around the chessboard (in its legitimate L-shaped moves, of course) at random. Your program should run onc tour and print the final chessboard. How far did the knight get? b) Most likely, the preceding program produced a relatively short tour. Now modify your program to attempt 1000 tours. Use a single-subscripted array to keep track of the number of tours of each length. When your program finishes attempting the 1000 tours, it should print this information in neat tabular format. What was the best result? c) Most likely, the preceding program gave you some "respectable" tours, but no full tours. Now "pull all the stops out and simply let your program run until it produces a full tour. (Caution: This version of the program could run for hours on a powerful computer.) Once again, keep a table of the number of tours of each length, and print this table when the first full tour is found. How many tours did your program attempt before producing a full tour? How much time did it take? d) Compare the brute-force version of the Knight's Tour with the accessibility-heuristic version. Which required a more careful study of the problem? Which algorithm was more difficult to develop? Which required more computer power? Could we be certain (in ad- vance) of obtaining a full tour with the accessibility heuristic approach? Could we be cer- lain (in advance) of obtaining a full tour with the brute-force approach? Argue the pros and cons of brute-force problem solving in general. 4.26 (Eight Queens) Another puzzler for chess bulls is the Eight Queens problem. Simply stated: Is it possible to place eight queens on an empty chessboard so that no queen is "attacking" any other, i.c., no two queens are in the same row, the same column, or along the same diagonal? Use the think- ing developed i ercise 4.24 to formulate a heuristic for solving the Eight lem. Run your program. (Hint: It is possible to assign a value to each square of the chessboard indicating how many squares of an empty chessboard arc "climinated" if a quccn is placed in that square. Each of the corners would be assigned the value 22, as in Fig. 4.30.) Once these "elimination numbers" are placed in all 64 squares, an appropriate heuristic might be: Place the next queen in the square with the small- cst elimination number. Why is this strategy intuitively appealing? 4.27 (Light Queens: Brute Force Approaches) In this exercise, you will develop several brute- force approaches to solving the Eight Queens problem introduced in Exercise 4.26, a) Solve the Eight Queens exercise, using the random brute force technique developed in Exercise 4.25. b) Use an exhaustive technique, i.e., try all possible combinations of eight queens on the chessboard, cessibility heuristic, ccessibility number refore, the tour may he chessboard, your squares become oc- square's accessibil m which that square Il tour? Now modify ssboard. How many tering a tie between ad to those squares he squarc for which number. ed a solution to the generates many so- Fig. 4.30 The 22 squares eliminated by placing a queen in the upper-left corner 298 Arrays Chapter 4 Use a 20-by-20 array floor that is initialized to veros. Read commands from an array that contains them. Keep track of the current position of the turtle at all times and whether the pen is cur- rently up or down. Assume that the turtle always starts at position 0,0 of the floor with its pen up, The set of turtle commands your program must process are as follows: Command Meaning 1 1 2 3 4 Pen up Pen down Turn right Turn left Move forward 10 spaces (or a number other than 10) Print the 20-by-20 array End of data (sentinel) 5,10 6 9 Suppose that the turtle is somewhere near the center of the floor. The following "program" would draw and print a 12-by-12 square and end with the pen in the up position: 2 5,12 3 5,12 3 5,12 3 5,12 1 6 9 As the turtle moves with the pen down, set the appropriate elements of array floor to 1's. When the 6 command (print) is given, wherever there is a 1 in the array, display an asterisk or some other character you choose. Wherever there is a zero, display a blank. Write a program to implement the turtle graphics capabilities discussed here. Write several turtle graphics programs to draw interesting shapes. Add other commands to increase the power of your turtle graphics language. 4.24 (Knight's Tour) One of the more interesting puzzlers for chess buffs is the Knight's Tour problem originally proposed by the mathematician Euler. The question is this: Can the chess piece called the knight move around an empty chessboard and touch cach of the 64 squares once and only once? We study this intriguing problem in depth herc. The knight makes L-shaped moves (over two in one direction and then over one in a perpendic- ular direction). Thus, from a square in the middle of an empty chessboard, the knight can make eight different moves (numbered through 7) as shown in Fig. 4.29. a) Draw an 8-by-8 chessboard on a sheet of paper and attempt a Knight's Tour by hand. Put a 1 in the first square you move to a 2 in the second square, a 3 in the third, etc. Before starting the tour, estimate how far you think you will get, remembering that a full tour consists of 64 moves. How far did you get? Was this close to your estimate? b) Now let us develop a program that will move the knight around a chessboard. The board is represented by an 8-by-8 double-subscripted array board. Each of the squares is ini- Chapter 4 Chapter 4 Arrays 299 ids from an array that whether the pen is cur- floor with its pen up. tialized to zero, We describe each of the eight possible moves in terms of both their hor izontal and vertical components. For example, a move of type 0, as shown in Fig. 4.25, consists of moving two squares horizontally to the right and one square vertically up- ward. Move 2 consists of moving one squarc horizontally to the left and two squares ver- tically upward, Horizontal moves to the left and vertical moves upward are indicated with negative numbers. The cight moves may be described by two single-subscripted arrays, horizontal and vertical, as follows: horizontal[ 0 ] - 2 horizontal[ 1 ] = 1 horizontal[ 2 ] = -1 horizontal[ 3 ] = -2 horizontal[ 4 ] = -2 horizontal[ 5 ] = -1 horizontal[ 6 ] - 1 horizontal[ 7 ] = 2 10) following program in: vertical[ 0 ] = -1 vertical[ 1 ] = - vertical[ 2 ] = -2 vertical[ 3 ] = -1 vertical[ 4 ] = 1 vertical[ 5 ] = 2 vertical[ 6 ] = 2 vertical[ 7 ] = 1 Let the variables current Row and currentColumn indicate the row and col- umn of the knight's current position. To make a move of type moveNumber, where moveNumber is between 0 and 7 your program uses the statements 0 1 2 3 4 0 1 2 1 floor to l's. When asterisk or some other ram to implement the ms to draw interesting guage. i is the Knight's Tour s: Can the chess piece squares once and only 2 3 0 3 K 4 4 7 5 5 6 6 er one in a perpendic- knight can make eight ht's Tour by hand. Put the third, etc. Before bering that a full tour estimate? hessboard. The board of the squares is ini- 7 Fig. 4.29 The eight possible moves of the knight. 300 Arrays Chapter 4 current Row + vertical moveNumber : currentColumn += horizontal moveNumber ]; Keep a counter that varies from 1 to 64. Record the latest count in cach square the knight moves to Remember to test each potential move to see if the knight has already visited that square, and, of course, test every potential move to make sure that the knight does not land off the chessboard. Now write a program to move the knight around the chess- board. Run the program. How many moves did the knight make? c) After attempting to write and run a Knight's Tour program, you have probably developed some valuable insights. We will use these to develop a heuristic (or strategy) for moving the knight. Heuristics do not guarantee success, but a carefully developed heuristic great- ly improves the chance of success. You may have observed that the outer squares are more troublesome than the squares nearer the center of the board. In fact, the most trou- blesome, or inaccessible, squares are the four corner's. Intuition may suggest that you should attempt to move the knight to the most trou- blesame squares first and leave open those that are easiest to get to, so when the board gets congested near the end of the tour, there will be a greater chance of success We may develop an "accessibility heuristic" hy classifying each of the squares ac- cording to how accessible they are and then always moving the knight to the square (within the knight's L-shaped moves, of course) that is most inaccessible. We label double-subscripted array accessibility with numbers indicating from how many squares ench particular square is accessible. On a blank chessboard, cach center square 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: 2 3 4 4 4 4 3 2 3 4 6 6 6 6 4 3 4 6 8 8 8 8 6 4 3 4 6 6 6 6 4 3 2 3 4 4 4 4 3 2 Now write a version of the Knight's Tour program using the accessibility heuristic. At any time, the knight should 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 program should reduce the accessibility numbers as more and more squares become oc- cupied. In this way, at any given time during the tour, cach available square's accessibil- ity number will remain equal to precisely the number of squares from which that square may be reached.) Run this version of your program. Did you get a full tour? Now modify the program to run 64 tours, one starting from each square of the chessboard. How many full tours did you get? d) Write a version of the Knight's Tour program which, when encountering a tie between two or more squares, decides what square to choose by looking ahead to those squares reachable from the "tied" squares. Your program should move to the square for which the next move would arrive at a square with the lowest accessibility number. 4.25 (Knight's Tour: Brute Force Approaches) In Exercise 4.24, we developed a solution to the Knight's Tour problem. The approach used, called the accessibility heuristic," generates many so lutions and executes efficiently, AB Chapter 4 Chapter 4 Arrays 301 ach square the knight it has already visited that the knight does ht around the chess- probably developed strategy) for moving oped heuristic greal- he outer syuares are 1 Cact, the most trou- ght to the most trou- I, so when the board re of success. ch of the squares ae- knight to the square cessible. We label a ng from how many 1. each center square s have accessibility As computers continue increasing in power, we will be able to solve more problems with sheer computer power and relatively unsophisticated algorithms. Let us call this approach "brute force" problem solving. a) Use random-number generation to enable the knight to walk around the chessboard (in its legitimate L-shaped moves, of course) at random. Your program should run onc tour and print the final chessboard. How far did the knight get? b) Most likely, the preceding program produced a relatively short tour. Now modify your program to attempt 1000 tours. Use a single-subscripted array to keep track of the number of tours of each length. When your program finishes attempting the 1000 tours, it should print this information in neat tabular format. What was the best result? c) Most likely, the preceding program gave you some "respectable" tours, but no full tours. Now "pull all the stops out and simply let your program run until it produces a full tour. (Caution: This version of the program could run for hours on a powerful computer.) Once again, keep a table of the number of tours of each length, and print this table when the first full tour is found. How many tours did your program attempt before producing a full tour? How much time did it take? d) Compare the brute-force version of the Knight's Tour with the accessibility-heuristic version. Which required a more careful study of the problem? Which algorithm was more difficult to develop? Which required more computer power? Could we be certain (in ad- vance) of obtaining a full tour with the accessibility heuristic approach? Could we be cer- lain (in advance) of obtaining a full tour with the brute-force approach? Argue the pros and cons of brute-force problem solving in general. 4.26 (Eight Queens) Another puzzler for chess bulls is the Eight Queens problem. Simply stated: Is it possible to place eight queens on an empty chessboard so that no queen is "attacking" any other, i.c., no two queens are in the same row, the same column, or along the same diagonal? Use the think- ing developed i ercise 4.24 to formulate a heuristic for solving the Eight lem. Run your program. (Hint: It is possible to assign a value to each square of the chessboard indicating how many squares of an empty chessboard arc "climinated" if a quccn is placed in that square. Each of the corners would be assigned the value 22, as in Fig. 4.30.) Once these "elimination numbers" are placed in all 64 squares, an appropriate heuristic might be: Place the next queen in the square with the small- cst elimination number. Why is this strategy intuitively appealing? 4.27 (Light Queens: Brute Force Approaches) In this exercise, you will develop several brute- force approaches to solving the Eight Queens problem introduced in Exercise 4.26, a) Solve the Eight Queens exercise, using the random brute force technique developed in Exercise 4.25. b) Use an exhaustive technique, i.e., try all possible combinations of eight queens on the chessboard, cessibility heuristic, ccessibility number refore, the tour may he chessboard, your squares become oc- square's accessibil m which that square Il tour? Now modify ssboard. How many tering a tie between ad to those squares he squarc for which number. ed a solution to the generates many so- Fig. 4.30 The 22 squares eliminated by placing a queen in the upper-left corner