C++ How to Program (10th Edition)
C++ How to Program (10th Edition)
10th Edition
ISBN: 9780134448237
Author: Paul J. Deitel, Harvey Deitel
Publisher: PEARSON
bartleby

Videos

Textbook Question
Book Icon
Chapter 7, Problem 7.22E

(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.

  1. Draw an 8-by-8 chessboard on a sheet of paper and attempt a Knight's Tour by hand'
  2. Put a 1 in the first square you move to. a 2 in the second square, A 3 in the third,
    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?
  3. Now let's develop a program that will move the knight around a chessboard. The board
  4. Is represented by an 8-by-8 two-dimensional array board. Each of the squares is initialized
    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.

Blurred answer
Students have asked these similar questions
Tiling: The precondition to the problem is that you are given threeintegers n, i, j, where i and j are in the range 1 to 2n. You have a 2n by 2n squareboard of squares. You have a sufficient number of tiles each with the shape . Your goalis to place nonoverlapping tiles on the board to cover each of the 2n × 2n tiles except forthe single square at location i, j. Give a recursive algorithm for this problem in whichyou place one tile yourself and then have four friends help you. What is your base case?
Can you help me with this code because I am struggling. The Lights Out puzzle consists of an m x n grid of lights, each of which has two states: on and off. The goal of the puzzle is to turn all the lights off, with the caveat that whenever a light is toggled, its neighbors above, below, to the left, and to the right will be toggled as well. If a light along the edge of the board is toggled, then fewer than four other lights will be affected, as the missing neighbors will beignored. In this section, you will investigate the behavior of Lights Out puzzles of various sizes by implementing a LightsOutPuzzle class. Once you have completed the problems in this section, you can test your code in an interactive setting using the provided GUI. See the end of the section for more details. Task: A natural representation for this puzzle is a two-dimensional list of Boolean values, where True corresponds to the on state and False corresponds to the off state. In the LightsOutPuzzle class, write an…
2, Towers of Hanoi Problem. (10 points) The Towers of Hanoi is a famous problem for studying recursion in computer science and searching in artificial intelligence. We start with N discs of varying sizes on a peg (stacked in order according to size), and two empty pegs. We are allowed to move a disc from one peg to another, but we are never allowed to move a larger disc on top of a smaller disc. The goal is to move all the discs to the rightmost peg (see figure). To solve the problem by using search methods, we need first formulate the problem. Supposing there are K pegs and N disk. Answer the following questions. (1) Determine a state representation for this problem. (4points) (2) What is the size of the state space? (3 points) (3) Supposing K=3, N=4, what is the start state by using your proposed state representation method and what is the goal state? (3 points)
Knowledge Booster
Background pattern image
Computer Science
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
SEE MORE QUESTIONS
Recommended textbooks for you
Text book image
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Text book image
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Text book image
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
Text book image
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Text book image
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Text book image
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education
Program to find HCF & LCM of two numbers in C | #6 Coding Bytes; Author: FACE Prep;https://www.youtube.com/watch?v=mZA3cdalYN4;License: Standard YouTube License, CC-BY