Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 171 Assignment 4
Submission Instructions: Please submit the .java files to Canvas. Make sure download Java template files for each question before coding. Make sure that all Java files you submit can be compiled and run against Java Development Kit 8 (or higher). You can define a main method and test them before submit it. For question 1 and 3, you are free to submit it either in a separate document or as comments in the java files for other questions.
Honor Code: Solve this assignment individually; do not collaborate with classmates or look for online solutions. We check for code plagiarism. The assignment is governed by the College Honor Code and Departmental Policy. Remember, any code you submit must be your own; otherwise, you risk being investigated by the Honor Council and facing the consequences of that. Finally, please remember to have the following comment included at the top of each of your .java file:
/*
THIS CODE WAS MY OWN WORK, IT WAS WRITTEN WITHOUT CONSULTING
CODE WRITTEN BY OTHER STUDENTS OR COPIED FROM ONLINE RESOURCES.
_Your_Name_Here_
*/
1. Stack (10 pts). Suppose that an intermixed sequence of stack push and pop operations are performed. The pushes push the integers 0 through 9 in order; the pops print out the return value. Which of the following sequence could not occur?
A) 2 1 4 3 6 5 8 7 9 0
B) 4 3 2 1 0 9 8 7 6 5
C) 4 6 8 7 5 3 2 9 0 1
2. Queue with stack. (20 pts). Please download the MyQueue.java file and implement the following operations of a queue using stack.
• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid. You cannot call pop or peek operations on an empty queue.
3. LSD sort (10 pts). Use LSD radix sort to sort the following numbers: 245, 163, 207, 109, 243, 9, 26, 33, 3. Please write the sort trace.
4. Implementing Knight's Tour Using a Stack. (60 pts) You know the chess piece that looks like a horse? This is called a `knight.' Recall that the knight can move in the shape of the letter `L' in any direction; i.e., it can move two squares horizontally followed by one square vertically, or two squares vertically followed by one horizontally. For example, if the Knight is located at the position marked X in the figure on the right, it can move to any of the Y positions.
An interesting question is: can a knight move around the board, visiting each square once, and only once? This is called the `Knight's Tour' problem. Here is an example table on the right of a `tour' by a knight on a 3x3 board, starting at the top left corner, where the knight attempts to visit each square exactly once.
The numbers indicate how many positions the knight has already visited during its tour. For example, the number 3 in the position indexed (0,2) on this 2D array means this was the knight's 3rd step; i.e., the knight's path was (0,0) → (2,1) → (0,2) and so on. Note that the center position was never visited.
Indeed, it is impossible for a knight to reach the center of a 3x3 chess board, but this shown tour is still valid (for a 3x3 board) since the maximum number of squares was visited on the board, and each position was visited exactly once. Right figure is another example of a valid tour, but this time for a 5x5 board where the knight was able to visit every square on the board, and exactly once.
Goal: Your goal for this question is to write a Java program that searches for a valid knight's tour on a board (whose size is passed as a parameter), starting at the top left corner. Your solution should make the knight visit exactly once the maximum number of positions on the board. Note that there can be several distinct valid tours for a given board. Your job is NOT to find every possible valid tour; rather, you should stop at the first valid tour you discover. To get a sense of how many valid board configurations may exist for different board sizes, see “The Knight's Paths" table here: http://www.behnel.de/knight.html
Data Structures Your solution must use a stack to keep track of different possible sequences of moves made by the knight, until you discover (and return) a valid tour. This paradigm where you incrementally try different solutions until you identify one that works is called backtracking, since you `backtrack' from a candidate solution once you realize it doesn't work. Many backtracking problems can be approached using recursion, or iteratively using stacks since they easily help you keep track of your `most recent' moves. For this question, your solution must utilize a stack and not rely on recursion. Use Java's Stack implementation:
https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html
Knight's Tour Algorithm: Here is the pseudocode for the algorithm you should implement to find a valid knight's tour (some of the details are left for you to fill in). You will use a stack to push the next valid board when the knight makes a legal move, and to pop the next board at each
iteration. This helps you search through different sequences of movements. Think carefully about when a move is `valid' and how you can ensure that your implementation terminates.
Starter Code Description
(1) The Board (KnightBoard.java): This class models a chess board as a 2- dimensional array of integers, and has data members that help you keep track of the knight's movements on it, like its current (x,y) coordinates, number of moves made so far, etc. It also includes other important helper methods. The main method in this class will also give you hints on how to use the board's methods. Start by reading the code in KnightBoard.java carefully, including all of our comments there.
(2) The Knight's Tour (KnightTour.java): This is the only file you need to edit and submit.
Your program must use a stack of KnightBoard objects to search for (and return) a valid knight's tour. All of this will happen inside the method tour(int n). You can create other helper methods in this class if needed, but make sure they are all declared static.
Note: While exploring a tour, it is your job to move the knight in legal positions; i.e., the knight begins at (0,0), with one possible next move being (1,2) and another possible one being (2,1).
Make sure you explore all possible legal moves for a knight, but note that the method move in class KnightBoard also includes some checks to validate a move; read it carefully before you design your solution.
Getting Started
1. Your starting point is KnightBoard.java. Read this class carefully and run the test cases in its main method make sure you understand how the board works.
2. Now read KnightTour.java carefully and implement the method tour(int n), while referring to this handout's detailed instructions. To test your solution, run the class KnightTour. The main method will initialize a 3x3 board for you by default. Verify that the output is correct.
3. Test your solution for larger boards by passing `n' as a command line argument to class KnightTour. (To input a command line argument in Eclipse or IntelliJ, you can click “Run" – “Run Configurations"- “Arguments" and then type in the argument in the \Program Arguments" box.)
Here's an example of how a program run might look like, when passing 5 as a command line argument:
4. Submit only KnightTour.java on Canvas for this question.
5. Debugging Tip: You can call the method printChessBoard from class KnightBoard to help you visualize the board and debug intermediate steps in your solution. But please remember to remove or comment out any print calls you added to the code, since these can affect the performance of your program significantly (just leave the one existing call to printChessBoard in KnightTour's main method).