
(Knight's Tour) One of the more interesting puzzlers for chess buffs is the Knight's Tour
problem. The question is this: Can the chess piece called the knight move around an empty chess-
board and touch each of the 64 squares once and only once? We study this intriguing problem in
depth in this exercise.
The knight makes L-shaped moves (over two in one direction then over one in a perpendicular
direction). Thus, from a square in the middle of an empty chessboard. the knight can make
eight different moves (numbered 0 through 7) as shown in Fig. 7.25.
- 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,
- Now let's develop a
program that will move the knight around a chessboard. The board Is represented by an 8-by-8 two-dimensional array board. Each of the squares is initialized
Before starting the tour, estimate how far you think you'll get, remembering that a full
tour consists of 64 moves. How Ear did you get? Was this close to your estimate?
zero. We describe each of the eight possible moves in terms of both their horizontal
and vertical components. For example, a move of type 0. as shown in Fig, 7.25,
consists of moving two squares horizontally to the right and one square vertically up-
ward. Move 2 consists of moving one square horizontally to the left and squares
0 1 2 3 4 5 6 7 0 1 2 1 2 3 0 3 K 4 4 7 5 5 6 6 7
Fig.7.25 The eight possible moves of the knight
Vertically upward. Horizontal moves to the left and vertical moves upward are indicated with negative numbers. The eight moves may be described by two one-dimensional arrays, horizontal and vertical, as follows:
Horizontal [0] =2 vertical [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 and currentCoIumn indicate the row and column of
the knight's current position. To make a move of type moveNumber, where is moveNumber is
between 0 and 7. your program uses the statements
CurrentRow += vertical [moveNumber];
currentColumn += horizontal [moveNumber];
Keep a counter that varies I to 64. Record latest in each square the knight moves to. Remember to test cach 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 "Tite a program to move the knight around the chessboard. Run the program. How many moves did the knight make?
c) After attempting to write and run a Knight's Tour program. you've probablv developed some value Insights. We'll use these develop a heuristic (or strategy) for moving the knight. Heuristics do not guarantee success, but a carefully developed heuristic greatly 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 troublesome, or inaccessible, squares arc the four corners.
Intuition may suggest that you should attempt to move the knight to the most troublesome squares first and leave open those that 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 may develop an "accessibility heuristic" by classifying each square according to how accessible it's then always moving the knight to the square (within the knight's L shaped moves, of course) that's least accessible. We label a two-dimensional array accessibility with numbers indicating from how many squares each particular square is accessible. On a blank chessboard, each 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
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
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 num ber. 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 chess- board, your program should reduce the accessibility numbers as more and 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 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.

Want to see the full answer?
Check out a sample textbook solution
Chapter 7 Solutions
C++ How to Program (10th Edition)
- using r language for integration theta = integral 0 to infinity (x^4)*e^(-x^2)/2 dx (1) use the density function of standard normal distribution N(0,1) f(x) = 1/sqrt(2pi) * e^(-x^2)/2 -infinity <x<infinity as importance function and obtain an estimate theta 1 for theta set m=100 for the estimate whatt is the estimate theta 1? (2)use the density function of gamma (r=5 λ=1/2)distribution f(x)=λ^r/Γ(r) x^(r-1)e^(-λx) x>=0 as importance function and obtain an estimate theta 2 for theta set m=1000 fir the estimate what is the estimate theta2? (3) use simulation (repeat 1000 times) to estimate the variance of the estimates theta1 and theta 2 which one has smaller variance?arrow_forwardusing r language A continuous random variable X has density function f(x)=1/56(3x^2+4x^3+5x^4).0<=x<=2 (1) secify the density g of the random variable Y you find for the acceptance rejection method. (2) what is the value of c you choose to use for the acceptance rejection method (3) use the acceptance rejection method to generate a random sample of size 1000 from the distribution of X .graph the density histogram of the sample and compare it with the density function f(x)arrow_forwardusing r language a continuous random variable X has density function f(x)=1/4x^3e^-(pi/2)^4,x>=0 derive the probability inverse transformation F^(-1)x where F(x) is the cdf of the random variable Xarrow_forward
- using r language in an accelerated failure test, components are operated under extreme conditions so that a substantial number will fail in a rather short time. in such a test involving two types of microships 600 chips manufactured by an existing process were tested and 125 of them failed then 800 chips manufactured by a new process were tested and 130 of them failed what is the 90%confidence interval for the difference between the proportions of failure for chips manufactured by two processes? using r languagearrow_forwardI want a picture of the tools and the pictures used Cisco Packet Tracer Smart Home Automation:o Connect a temperature sensor and a fan to a home gateway.o Configure the home gateway so that the fan is activated when the temperature exceedsa set threshold (e.g., 30°C).2. WiFi Network Configuration:o Set up a wireless LAN with a unique SSID.o Enable WPA2 encryption to secure the WiFi network.o Implement MAC address filtering to allow only specific clients to connect.3. WLC Configuration:o Deploy at least two wireless access points connected to a Wireless LAN Controller(WLC).o Configure the WLC to manage the APs, broadcast the configured SSID, and applyconsistent security settings across all APs.arrow_forwardA. What will be printed executing the code above?B. What is the simplest way to set a variable of the class Full_Date to January 26 2020?C. Are there any empty constructors in this class Full_Date?a. If there is(are) in which code line(s)?b. If there is not, how would an empty constructor be? (create the code lines for it)D. Can the command std::cout << d1.m << std::endl; be included after line 28 withoutcausing an error?a. If it can, what will be printed?b. If it cannot, how could this command be fixed?arrow_forward
- Cisco Packet Tracer Smart Home Automation:o Connect a temperature sensor and a fan to a home gateway.o Configure the home gateway so that the fan is activated when the temperature exceedsa set threshold (e.g., 30°C).2. WiFi Network Configuration:o Set up a wireless LAN with a unique SSID.o Enable WPA2 encryption to secure the WiFi network.o Implement MAC address filtering to allow only specific clients to connect.3. WLC Configuration:o Deploy at least two wireless access points connected to a Wireless LAN Controller(WLC).o Configure the WLC to manage the APs, broadcast the configured SSID, and applyconsistent security settings across all APs.arrow_forwardTransform the TM below that accepts words over the alphabet Σ= {a, b} with an even number of a's and b's in order that the output tape head is positioned over the first letter of the input, if the word is accepted, and all letters a should be replaced by the letter x. For example, for the input aabbaa the tape and head at the end should be: [x]xbbxx z/z,R b/b,R F ① a/a,R b/b,R a/a, R a/a,R b/b.R K a/a,R L b/b,Rarrow_forwardGiven the C++ code below, create a TM that performs the same operation, i.e., given an input over the alphabet Σ= {a, b} it prints the number of letters b in binary. 1 #include 2 #include 3 4- int main() { std::cout > str; for (char c : str) { if (c == 'b') count++; 5 std::string str; 6 int count = 0; 7 char buffer [1000]; 8 9 10 11- 12 13 14 } 15 16- 17 18 19 } 20 21 22} std::string binary while (count > 0) { binary = std::to_string(count % 2) + binary; count /= 2; std::cout << binary << std::endl; return 0;arrow_forward
- Considering the CFG described below, answer the following questions. Σ = {a, b} • NT = {S} Productions: P1 S⇒aSa P2 P3 SbSb S⇒ a P4 S⇒ b A. List one sequence of productions that can accept the word abaaaba; B. Give three 5-letter words that can be accepted by this CFG; C. Create a Pushdown automaton capable of accepting the language accepted by this CFG.arrow_forwardGiven the FSA below, answer the following questions. b 1 3 a a b b с 2 A. Write a RegEx that is equivalent to this FSA as it is; B. Write a RegEx that is equivalent to this FSA removing the states and edges corresponding to the letter c. Note: To both items feel free to use any method you want, including analyzing which words are accepted by the FSA, to generate your RegEx.arrow_forward3) Finite State Automata Given the FSA below, answer the following questions. a b a b 0 1 2 b b 3 A. Give three 4-letter words that can be accepted by this FSA; B. Give three 4-letter words that cannot be accepted by this FSA; C. How could you describe the words accepted by this FSA? D. Is this FSA deterministic or non-deterministic?arrow_forward
- C++ for Engineers and ScientistsComputer ScienceISBN:9781133187844Author:Bronson, Gary J.Publisher:Course Technology PtrC++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage LearningOperations Research : Applications and AlgorithmsComputer ScienceISBN:9780534380588Author:Wayne L. WinstonPublisher:Brooks Cole
- Programming Logic & Design ComprehensiveComputer ScienceISBN:9781337669405Author:FARRELLPublisher:CengageNew Perspectives on HTML5, CSS3, and JavaScriptComputer ScienceISBN:9781305503922Author:Patrick M. CareyPublisher:Cengage LearningMicrosoft Visual C#Computer ScienceISBN:9781337102100Author:Joyce, Farrell.Publisher:Cengage Learning,




