Knight’s Tour in Java Homework Sample

In chess a knight can move in a L shape that is 2 long and then 1, that means there are 8 possible locations for a knight to move to (assuming it is not too close to the edge of the board). The chess board has 64 squares on it, and there are a number of tours (a path around the board that visits each square once, and once only). You are not allowed to use a recursive algorithm, and need to use an iterative algorithm with backtracking and a stack. You should mark all the squares with -1, and when backtracking, and mark with 1, 2, 3, etc as you move around the tour. For more Java programming assignments contact us for details.

Solution:

GameState.java

package knighttour;

public class GameState {

/*
*
*Class to hold the state of the tour. This is useful in backtracking since the current position
*and the state of the boards needs to be saved in order to perform extensive calculations.
*
*/

int current_x;
int current_y;

int[][] board;

public GameState(int[][] board, int x, int y){
this.current_x=x;
this.current_y=y;
this.board=board;
}

public GameState clone(){
return new GameState(board,current_x,current_y);
}

}

KnightTour.java

package knighttour;

import java.util.Scanner;
import java.util.Stack;

public class KnightTour {

/*Array with posible knights move. Every movement is generated with the following formula:
* next_x=current_x+move1[i]
* next_y=current_y+move2[i]
*/
static int move1[] = {-2,-1,1,2,2,1,-1,-2};
static int move2[] = {1,2,2,1,-1,-2,-2,-1};

/*
*Board to hold the steps in order. Useful when using heuristic approach
*/
static int board[][]=new int[8][8];

/*
*The (x,y) position of the last step taken
*/
static int current_x=0;
static int current_y=0;

/*
*Variable to hold the last step taken
*/
static int step=1;

/*
*LinkedList to hold all initial positions entered by user
*/
static LinkedList initial_positions=new LinkedList();

public static void main(String[] args) {

//Initial ooption
String option=”Y”;

//Define all scanners to read input form user
Scanner option_scanner = new Scanner(System.in);
Scanner x_scanner=new Scanner(System.in);
Scanner y_scanner=new Scanner(System.in);

//Keep looping until the user enters an uppercase or lowercase letter “N”
while(!option.toUpperCase().equals(“N”)){

//Read initial position and insert it in the list
System.out.println(“Enter the x coord of the initial position: “);
int x = x_scanner.nextInt();
System.out.println(“Enter the y coord of the initial position: “);
int y = y_scanner.nextInt();
initial_positions.add(new Position(x,y));
System.out.println(“Do you wish to enter another initial position? (Y/N)”);
option = option_scanner.next();
}

//Calculate tour for all positions entered
for(int i=0;i<initial_positions.size();i++){
Position current_initial_pos=initial_positions.get(i);
current_x=current_initial_pos.x;
current_y=current_initial_pos.y;

System.out.println(“\n\nCalculating tour for initial pos: “+current_initial_pos.toString()+”\n”);
calculateTour();
System.out.println(“Board result: \n\n”);
print(board);
resetBoard();
step=1;
}

}
/*
*
*Method to calculate Knight’s tour. First 32 steps are calculated using Wandorff’s Heuristic
*The following steps are calculated using an iterative version of backtracking.
*
*/
public static void calculateTour(){
//Set first step
board[current_x][current_y]=step;

//Set remaining 31 steps using Wanrdorff’s heuristic
for(step=2;step<32;step++){

//Save the position with the minimum exits to compare later
int min_x=-1;
int min_y=-1;
int min_exits=9999;

for(int i=0;i<8;i++){

//Generate new move
int new_x=current_x+move1[i];
int new_y=current_y+move2[i];

//If it is valid, check if the number of exits if lower than the exist from the saved position
if(is_valid(new_x,new_y,board)){

int exits=countExits(new_x,new_y,board);
if(exits<min_exits){
//Save new position since it has less exits
min_x=new_x;
min_y=new_y;
min_exits=exits;
}
}
}

//Set step number in the board and save generated position as current position
current_x=min_x;
current_y=min_y;

board[current_x][current_y]=step;

}

/*
*
*Finished with Wandorff’s heuristic we must now roceed with iterative backtracking
*print the board here to see an intermediate state.
*
*/

/*
*Create a stack to hold all gamestates
*/
Stack<GameState> stack=new Stack<>();

/*
*Add as first GameState the information obtained after advancing 32 steps using Wandorff’s Heuristic
*/
stack.add(new GameState(board,current_x,current_y));

/*
*Proceed with bactracking calculation
*/
while(!stack.empty()){
GameState current=stack.pop();

if(isFinal(current.board))
{
return;
}

//Generate children boards:

for(int i=0;i<8;i++){
int new_x=current.current_x+move1[i];
int new_y=current.current_y+move2[i];

GameState toadd=current.clone();

if(is_valid(new_x,new_y,toadd.board)){
toadd.board[new_x][new_y]=step;
toadd.current_x=new_x;
toadd.current_y=new_y;
stack.add(toadd);
}
}

step++;

}
}

/*
*
*Method used to reset static board variable in order to use it in multiple calculations
*using different initial positions
*
*/
public static void resetBoard(){

for(int i=0;i<8;i++)
for(int j=0;j<8;j++)
board[i][j]=0;
}

/*
*Method to count the number of valid exits from a given position
*/
public static int countExits(int x, int y, int[][] board){
if(!is_valid(x,y,board))
return 9999;
int count=0;
int k;
for(k=0;k<8;k++)
if(is_valid(x+move1[k],y+move2[k],board))
count++;

if(count==0)
return 9999;
return count;
}

/*
*
*Method that checks wether a position is inside valid boundaries and it hasn’t been stepped
*
*/
public static boolean is_valid(int x,int y,int[][] board){

if(x>7 || x<0)
return false;
if(y>7 || y<0)
return false;
if(board[x][y]!=0)
return false;
return true;
}

/*
*Simple method to print the state of the board in a fashion way
*/
public static void print(int[][] board){

for(int i=0;i<8;i++){
for(int j=0;j<8;j++)
System.out.print(board[i][j]+”\t”);
System.out.println(“\n”);
}
}

public static boolean isFinal(int[][] board){
for(int i=0;i<8;i++)
for(int j=0;j<8;j++)
if(board[i][j]==0)
return false;
return true;
}

}

LinkedList.java

package knighttour;

public class LinkedList {

/*
*LinkedList implementation
*/

private Node head;

private int size;

public LinkedList(){
size=0;
head=null;
}

public void add(Position p){
if(head==null){
head=new Node(p);
head.next=null;
return;
}

Node cursor=head;

while(cursor.next!=null)
cursor=cursor.next;
cursor.next=new Node(p);
size++;
}

public Position get(int index){

if(index>=size)
return null;

Node cursor=head;
int cursor_counter=0;

while(cursor_counter<index){
cursor=cursor.next;
cursor_counter++;
}
return cursor.p;
}

public void print(){

Node cursor=head;

while(cursor!=null)
{
System.out.println(cursor.p.toString());
cursor=cursor.next;
}
}

public int size(){
return this.size;
}

public boolean empty(){
return this.size==0;
}

class Node{
Position p;
Node next;

public Node(Position p){
this.p=p;
}

public Position getPosition()
{
return this.p;
}

}

}

Position.java

package knighttour;

public class Position {

/*
*Basic class to hold a position. This class is widely used to hold the initial
*positions entered by the user.
*/

int x;
int y;

public Position(int x, int y){
this.x=x;
this.y=y;
}

public int getY(){
return this.y;
}

public int getX(){
return this.x;
}

public String toString(){
return “Pos: [“+x+”,”+y+”]”;
}
}