Starting from:
$29
HW07: Knight’s Move
HW07: Knight’s Move
1. Introduction In this assignment, we use graph traversal to solve an interesting chess problem. Specifically, we will use implement dfs and use it to solve the problem.
2. Objectives The purpose of this assignment is to give you experience in: • Understanding the dfs graph traversal • How to use dfs to solve some real world problems. • Understanding when to use dfs instead of bfs. Note: Before you start, if you are not familiar with graph and graph traversal algorithms, it is recommended you review the corresponding class notes.
3. Background 3.1. Knight’s Move This problem is from book “The Moscow puzzles”. The author of this book is Boris A. Kordemsky, and this book is edited by Martin Gardner. This problem appears in the chapter II Difficult Problems.
The following page displays the cover of the book, and the illustration and description of this problem from the book.
We will solve this problem using graph traversal. We consider the knight’s position on the chessboard as a vertex in a graph. At the beginning, the knight can capture one of the 16 pawns. Therefore, we can start from any of the 16 starting points. At the end, all the pawns will be gone. Hence, the end point is at one of the 16 vertices.
The key to solving this problem is to construct a graph that has 16 vertices, and define edges according to the rule of how knights move in chess.
Once we have the graph, we can traverse the graph and the goal is to traverse every single vertex without repeating.
There are multiple solutions to this problem. We will try to find a solution using DFS. Since it is not guaranteed that we can find a solution with one DFS traversal, we will do DFS multiple times. To make sure we traversal different paths when we do multiple DFS traversals, we change the original DFS algorithm a little bit to make it behave randomly. That is, when we push all the neighbors of a vertex on to the stack that is used for DFS, we randomly shuffle the order of the neighbors before we push them onto the stack. This ensures that for each DFS, the path traversed is random.
4. Assignment In the skeleton zip file, you will find a skeleton for your .py file named chess.py. All you need to do is to complete the skeleton code based on the instructions and submit it to the Mimir system. There are two places you need to fill in code. 4.1. Method randomdfs
We first copy code from dfs method and make necessary changes. The goal is to make sure that when we add neighbors to a stack, we add them in a random order. This way, every time we do this random dfs, the result is random. 4.2. Inverse DFS tree and display result
The randomdfs(v) method will return a depth-first search tree. This tree is implemented as a dictionary. For each key (vertex), the value is its parent vertex. Now we need to check whether this tree is actually linear. If this tree is linear (a straight line) then we have a solution. If this is true, we need to make a new dictionary that is the inverse of this dictionary tree. That is, the key and value is switched for each item. Using this inversed dictionary, we print out all the moves the knight takes, and return this inversed dictionary as the return value of the knightsmove function.
1. Introduction In this assignment, we use graph traversal to solve an interesting chess problem. Specifically, we will use implement dfs and use it to solve the problem.
2. Objectives The purpose of this assignment is to give you experience in: • Understanding the dfs graph traversal • How to use dfs to solve some real world problems. • Understanding when to use dfs instead of bfs. Note: Before you start, if you are not familiar with graph and graph traversal algorithms, it is recommended you review the corresponding class notes.
3. Background 3.1. Knight’s Move This problem is from book “The Moscow puzzles”. The author of this book is Boris A. Kordemsky, and this book is edited by Martin Gardner. This problem appears in the chapter II Difficult Problems.
The following page displays the cover of the book, and the illustration and description of this problem from the book.
We will solve this problem using graph traversal. We consider the knight’s position on the chessboard as a vertex in a graph. At the beginning, the knight can capture one of the 16 pawns. Therefore, we can start from any of the 16 starting points. At the end, all the pawns will be gone. Hence, the end point is at one of the 16 vertices.
The key to solving this problem is to construct a graph that has 16 vertices, and define edges according to the rule of how knights move in chess.
Once we have the graph, we can traverse the graph and the goal is to traverse every single vertex without repeating.
There are multiple solutions to this problem. We will try to find a solution using DFS. Since it is not guaranteed that we can find a solution with one DFS traversal, we will do DFS multiple times. To make sure we traversal different paths when we do multiple DFS traversals, we change the original DFS algorithm a little bit to make it behave randomly. That is, when we push all the neighbors of a vertex on to the stack that is used for DFS, we randomly shuffle the order of the neighbors before we push them onto the stack. This ensures that for each DFS, the path traversed is random.
4. Assignment In the skeleton zip file, you will find a skeleton for your .py file named chess.py. All you need to do is to complete the skeleton code based on the instructions and submit it to the Mimir system. There are two places you need to fill in code. 4.1. Method randomdfs
We first copy code from dfs method and make necessary changes. The goal is to make sure that when we add neighbors to a stack, we add them in a random order. This way, every time we do this random dfs, the result is random. 4.2. Inverse DFS tree and display result
The randomdfs(v) method will return a depth-first search tree. This tree is implemented as a dictionary. For each key (vertex), the value is its parent vertex. Now we need to check whether this tree is actually linear. If this tree is linear (a straight line) then we have a solution. If this is true, we need to make a new dictionary that is the inverse of this dictionary tree. That is, the key and value is switched for each item. Using this inversed dictionary, we print out all the moves the knight takes, and return this inversed dictionary as the return value of the knightsmove function.
1 file (722.5KB)
