Assignment-1:
Knight’s Tour Application Development in Chess Game:
Deliverable:
1. Report
2. Source file(.java)
Problem Description:
An interesting puzzler for chess game is the Knight’s Tour problem, originally proposed by the
mathematician Euler. Can the knight piece move around an empty chessboard and touch each of the 64
squares once and only once? We study this intriguing problem in depth here.
The knight makes only L-shaped moves (two spaces in one direction and one space in a perpendicular
direction). Thus, as shown in the Fig. 1, from a square near the middle of an empty chessboard, the knight
(labeled K) can make eight different moves (numbered 0 through 7).
XXXXXXXXXX
0
XXXXXXXXXX
XXXXXXXXXX
3 K
XXXXXXXXXX
XXXXXXXXXX
6
7
Fig.1. The eight possible moves of the knight
A. Draw an eight-by-eight chessboard on a sheet of paper and attempt a Knight’s Tour by hand. Put
a 1 in the starting square, a 2 in the second square, a 3 in the third, and so on. Before starting the
tour, estimate how far you think you’ll get, remembering that a full tour consists of 64 moves.
How far did you get? Was this close to your estimate? (5 Marks)
B. Now let’s develop an application that will move the knight around a chessboard. The board is
epresented by an eight-by-eight two-dimensional a
ay board. Each square is initialized to zero.
We describe each of the eight possible moves in terms of its horizontal and vertical components.
For example, a move of type 0, as shown in Fig. 1, consists of moving two squares horizontally to
the right and one square vertically upward. A move of type 2 consists of moving one square
horizontally to the left and two squares vertically upward. Horizontal moves to the left and vertical
moves upward are indicated with negative numbers. The eight moves may be described by two
one-dimensional a
ays, horizontal and vertical, as follows:
horizontal[0] = 2 vertical[0] = -1
horizontal[1] = 1 vertical[1] = -2
horizontal[2] = -1 vertical[2] = -2
horizontal[3] = -2 vertical[3] = -1
horizontal[4] = -2 vertical[4] = 1
horizontal[5] = -1 vertical[5] = 2
horizontal[6] = 1 vertical[6] = 2
horizontal[7] = 2 vertical[7] = 1
Let the variables cu
entRow and cu
entColumn indicate the row and column, respectively, of
the knight’s cu
ent position. To make a move of type moveNumber, where moveNumber is
etween 0 and 7, your application should use the statements
cu
entRow += vertical[moveNumber];
cu
entColumn += horizontal[moveNumber];
Write an application to move the knight around the chessboard. Keep a counter that varies from
1 to 64. Record the latest count in each square the knight moves to. Test each potential move to
see if the knight has already visited that square. Test every potential move to ensure that the
knight does not land off the chessboard. [Continue until knight can no longer move, i.e., if no valid
moves, knight can no longer move; if 64 moves have been made, a full tour is complete]
• Run the application with randomize initial board position
• How many moves did the knight make?
• Show your output in a table representation as shown below. (25 Marks)
Sample Output:
package com.mycompany.knighttour;
**
*
* @author bakht
*
import java.util.Random;
public class KnightTour {
public static void main(String[] args)
designing board, size of each a
ay = required size + 1
{
XXXXXXXXXXint[][] chessBoard = new int[6][6];
XXXXXXXXXXint [] horizontal = {2,1,-1,-2,-2,-2,-1,1,2};
column
XXXXXXXXXXint [] vertical = {-1,-2,-2,-1,1,2,2,1};
ow
XXXXXXXXXXRandom randX = new Random();
XXXXXXXXXXRandom randY = new Random();
XXXXXXXXXXint x = 1+randX.nextInt((chessBoard.length-1));
XXXXXXXXXXint y = 1+randY.nextInt((chessBoard.length-1));
XXXXXXXXXXSystem.out.println(x);
XXXXXXXXXXSystem.out.println(y);
XXXXXXXXXXint count = 1;
XXXXXXXXXXboolean isPossible = false;
XXXXXXXXXXchessBoard[x][y] = 1;
count = count +1;
XXXXXXXXXXfor ( int i =0; i
{
1
XXXXXXXXXXfor ( int j =0; j
{
2
XXXXXXXXXXif ( i == 0)
first row
{
3
XXXXXXXXXXchessBoard[i][j] = j ;
}
3
XXXXXXXXXXelse
{
4
XXXXXXXXXXif(j==0)
first column
{
5
XXXXXXXXXXchessBoard[i][j] = i ;
}
5
XXXXXXXXXXelse
XXXXXXXXXXif(i != 0 && j!=0 && chessBoard[i][j]==count)
{
7
XXXXXXXXXXfor ( int k = 0; k< 8 ; k++)
{
8
XXXXXXXXXXswitch(k)
{
switch
XXXXXXXXXXcase 0:
{
case0
XXXXXXXXXXy = y + horizontal[k] ;
XXXXXXXXXXx = x + vertical[k] ;
XXXXXXXXXXif((x>0 && x<(chessBoard.length)) &&
XXXXXXXXXXy>0 && y<(chessBoard.length)) &&
XXXXXXXXXXcount<= (chessBoard.length-1)* (chessBoard.length-1)))
{
111
XXXXXXXXXXi = x;
XXXXXXXXXXj = y;
XXXXXXXXXXcount++;
XXXXXXXXXXchessBoard[i][j] = count ;
XXXXXXXXXXisPossible = true;