Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
Given a chess board, your job is to write a program that takes two squares x and y as input and then determines the number of knight moves on a shortest route from x to y. a b c d e f g h 8 e2 e4 al b2 b2 c3 al h8 al h7 h8 al b1 c3 f6 f6 7 6 5 4 3 2 1 a b c d e f g h 87 6 5 4 3 2 1 Input Specification Your program should read from an input file, which will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard. Sample Input Output Specification For each test case, print one line saying To get from xx to yy takes ?? knight moves. in console. Sample Output Below is the correct output for the previous sample input. To get from e2 to e4 takes 2 knight moves. To get from a1 to b2 takes 4 knight moves. To get from b2 to c3 takes 2 knight moves. To get from al to h8 takes 6 knight moves. To get from al to h7 takes 5 knight moves. To get from h8 to al takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes knight moves. Hint • According to the problem description, the grid is 8 by 8, therefore there are 64 squares. We can then model the chessboard as a graph with 64 vertices; and an edge between two vertices exists if and only if we can make a knight move from one vertex to another. • When moving to the next position, a knight can have at most eight possible directions, as shown in the above figure for the black knight, without getting out of the chess board boundary. • The problem becomes a graph traversal problem! • DFS or BFS? Which one will work?

Given a chess board, your job is to write a program that takes two squares x and y as input and then determines the number of knight moves on a shortest route from x to y. a b c d e f g h 8 e2 e4 al b2 b2 c3 al h8 al h7 h8 al b1 c3 f6 f6 7 6 5 4 3 2 1 a b c d e f g h 87 6 5 4 3 2 1 Input Specification Your program should read from an input file, which will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard. Sample Input Output Specification For each test case, print one line saying To get from xx to yy takes ?? knight moves. in console. Sample Output Below is the correct output for the previous sample input. To get from e2 to e4 takes 2 knight moves. To get from a1 to b2 takes 4 knight moves. To get from b2 to c3 takes 2 knight moves. To get from al to h8 takes 6 knight moves. To get from al to h7 takes 5 knight moves. To get from h8 to al takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes knight moves. Hint • According to the problem description, the grid is 8 by 8, therefore there are 64 squares. We can then model the chessboard as a graph with 64 vertices; and an edge between two vertices exists if and only if we can make a knight move from one vertex to another. • When moving to the next position, a knight can have at most eight possible directions, as shown in the above figure for the black knight, without getting out of the chess board boundary. • The problem becomes a graph traversal problem! • DFS or BFS? Which one will work?

Database System Concepts
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
See similar textbooks
icon
Related questions
Question
Given a chess board, your job is to write a program that takes two squares x and y as input and then determines the number of knight moves on a shortest route from x to y. a b c d e f g h 8 e2 e4 al b2 b2 c3 al h8 al h7 h8 al b1 c3 f6 f6 7 6 5 4 3 2 1 a b c d e f g h 87 6 5 4 3 2 1 Input Specification Your program should read from an input file, which will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard. Sample Input
Transcribed Image Text:Given a chess board, your job is to write a program that takes two squares x and y as input and then determines the number of knight moves on a shortest route from x to y. a b c d e f g h 8 e2 e4 al b2 b2 c3 al h8 al h7 h8 al b1 c3 f6 f6 7 6 5 4 3 2 1 a b c d e f g h 87 6 5 4 3 2 1 Input Specification Your program should read from an input file, which will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard. Sample Input
Output Specification For each test case, print one line saying To get from xx to yy takes ?? knight moves. in console. Sample Output Below is the correct output for the previous sample input. To get from e2 to e4 takes 2 knight moves. To get from a1 to b2 takes 4 knight moves. To get from b2 to c3 takes 2 knight moves. To get from al to h8 takes 6 knight moves. To get from al to h7 takes 5 knight moves. To get from h8 to al takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes knight moves. Hint • According to the problem description, the grid is 8 by 8, therefore there are 64 squares. We can then model the chessboard as a graph with 64 vertices; and an edge between two vertices exists if and only if we can make a knight move from one vertex to another. • When moving to the next position, a knight can have at most eight possible directions, as shown in the above figure for the black knight, without getting out of the chess board boundary. • The problem becomes a graph traversal problem! • DFS or BFS? Which one will work?
Transcribed Image Text:Output Specification For each test case, print one line saying To get from xx to yy takes ?? knight moves. in console. Sample Output Below is the correct output for the previous sample input. To get from e2 to e4 takes 2 knight moves. To get from a1 to b2 takes 4 knight moves. To get from b2 to c3 takes 2 knight moves. To get from al to h8 takes 6 knight moves. To get from al to h7 takes 5 knight moves. To get from h8 to al takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes knight moves. Hint • According to the problem description, the grid is 8 by 8, therefore there are 64 squares. We can then model the chessboard as a graph with 64 vertices; and an edge between two vertices exists if and only if we can make a knight move from one vertex to another. • When moving to the next position, a knight can have at most eight possible directions, as shown in the above figure for the black knight, without getting out of the chess board boundary. • The problem becomes a graph traversal problem! • DFS or BFS? Which one will work?
Expert Solution
steps

Step by step

Solved in 2 steps with 3 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Time complexity
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.
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS