Advanced Topics in Programming Language (WXGA6109) Date: 6/10/2015 Assignment 1

Question

Advanced Topics in Programming Language (WXGA6109)

Date: 6/10/2015

Assignment 1

N-knights problem

In this assignment, the N-Knight's problem must attempt to move around the chess board so that the Knights must visit the maximum number of board positions without attacking each other.

You are asked to write a Java program that can allocate the knights on the chessboard based on the following conditions:

1)The Knight can move in the shape of the letter, 'L', over two in one direction and then over one in a perpendicular direction.

2)If the Knight rests at the square marked X.

3)The board is represented by an 8-by-8 two-dimensional array.

4)The Knights can be placed on the board as specified above so that no two Knights are attacking each other.

Your program should be well documented, and you should turn in the following in hard copy:

1)An external documentation describing the knight formulation, the program structure, global variables, the function/procedure to compute the heuristic function, and other functions/procedures, etc.

2)your program source codes (with necessary comments);

3)The execution results printed in a hard copy as required above as well as a soft copy must be presented.

Explanation / Answer

// Java program for Knight Tour problem
class NKnight {
static int N = 8;

/* A utility function to check if i,j are
valid indexes for N*N chessboard */
static boolean isSafe(int x, int y, int sol[][]) {
return (x >= 0 && x < N && y >= 0 &&
y < N && sol[x][y] == -1);
}

/* A utility function to print solution
matrix sol[N][N] */
static void print(int sol[][]) {
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
System.out.print(sol[x][y] + " ");
System.out.println();
}
}

/* This function solves the Knight Tour problem
using Backtracking. This function mainly
uses solveKTUtil() to solve the problem. It
returns false if no complete tour is possible,
otherwise return true and prints the tour.
Please note that there may be more than one
solutions, this function prints one of the
feasible solutions. */
static boolean solveKT() {
int sol[][] = new int[8][8];

/* Initialization of solution matrix */
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
sol[x][y] = -1;

/* xMove[] and yMove[] define next move of Knight.
xMove[] is for next value of x coordinate
yMove[] is for next value of y coordinate */
int xMove[] = {2, 1, -1, -2, -2, -1, 1, 2};
int yMove[] = {1, 2, 2, 1, -1, -2, -2, -1};

// Since the Knight is initially at the first block
sol[0][0] = 0;

/* Start from 0,0 and explore all tours using
solveKTUtil() */
if (!solveKTUtil(0, 0, 1, sol, xMove, yMove)) {
System.out.println("Solution does not exist");
return false;
} else
print(sol);

return true;
}

/* A recursive utility function to solve Knight
Tour problem */
static boolean solveKTUtil(int x, int y, int movei,
int sol[][], int xMove[],
int yMove[]) {
int k, next_x, next_y;
if (movei == N * N)
return true;

/* Try all next moves from the current coordinate
x, y */
for (k = 0; k < 8; k++) {
next_x = x + xMove[k];
next_y = y + yMove[k];
if (isSafe(next_x, next_y, sol)) {
sol[next_x][next_y] = movei;
if (solveKTUtil(next_x, next_y, movei + 1,
sol, xMove, yMove))
return true;
else
sol[next_x][next_y] = -1;// backtracking
}
}

return false;
}

/* Driver program to test above functions */
public static void main(String args[]) {
solveKT();
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.