Problem # 3 At a student’s engineering convention the robotics challenge was pro
ID: 3348923 • Letter: P
Question
Problem # 3
At a student’s engineering convention the robotics challenge was provided by professor JB to build a smart algorithm for a car that can travel through to 12 rooms using the “knight’s tour”.
The problem of finding the knight’s tour around a chessboard is a sequence of moves made by a knight chess piece that visits each square on the board exactly once. In each move, the knight moves 2 squares horizontally then one vertically, or 2 squares vertically then 1 horizontally. (in a chess game, its move cannot be blocked by another piece).
The eight squares that a knight may reach in a single move from a particular square S are Marked K in the figure below. An example of a 5x5 board would look as such.
Of course if the knight piece starts at an edge, there may be fewer than eight reachable squares.
In this problem, you will attempt to produce an FSM model for knight’s tour machine that can travel a 4 by 3 board. Find or develop
An FSM model to describe a travel algorithm to cover all the squares (in our case it is the number of rooms in the puzzle). You can only visit a room once. The judge will shut the door to a room that has already been visited.
Derive a C structure for this model that you think can solve the puzzle in the shortest amount of time.
Extra credit : Program this algorithm to show the number of iterations it took for the robot car to visit all the rooms using this walk.
For Example: the optimal solution for the 3x4 is 12 moves. I looks as such:
Explanation / Answer
the Problem of finding the “knight’s tour” around a chessboard is a sequence of moves made by a knight chess piece that visits each square on the board exactly once.
{
private boolean moveIsPossible (Position pos) {
return (pos.x >= 0 && pos.x <= 7) && (pos.y >= 0 && pos.y <= 7);
}
int [] x = {1, 2, 2, 1, -1, -2, -2, -1};
int [] y = {2, 1, -1, -2, -2, -1, 1, 2};
private ArrayList<Position> reachableSet = new ArrayList<Position>();
@Override
public ArrayList<Position> getReachableSet(Position pos, int numberofMoves) {
if (!reachableSet.contains(pos)) reachableSet.add(pos);
if (numberofMoves == 0) return reachableSet;
ArrayList<Position> moves = new ArrayList<Position>();
for (int i = 0; i < 8; i++) {
Position candidate = new Position (pos.x+x[i], pos.y+y[i]);
if (!moveIsPossible(candidate)) continue;
if (!reachableSet.contains(candidate)) {
moves.add(candidate);
}
}
for (int j = 0; j < moves.size(); j++) {
reachableSet = getReachableSet(moves.get(j), numberofMoves-1);
}
return reachableSet;
}
}
public class Position implements Comparable<Position> {
//The row on the chess board
public int x;
//The column on the chess board
public int y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.