Question

Project 1 Due Date Problem Knight's Tour: The Knights Tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving acording to the rules of chess, must visit each square once. 06-JUN-2018 There are several billion solutions to the problem, of which about 122,000,000 have the knight finishing on the same square on which it begins. When this occurs the tour is said to be closed. Your assignment is to write a program that gives a solution to the Knight's Tour problem recursively. You must hand in a solution in C++ AND Java. The name of the C++ file should be "main.ce" and the name of the Java file should be Main,java".Output should look similar to: 1 34 3 18 49 32 13 16 4 19 56 33 14 17 50 31 57 2 35 48 5S 52 15 12 0 5 60 53 36 47 30 51 58 37 46 61 54 11 26 6 21 42 59 38 27 64 29 43 40 23 45 62 25 10 22 7 44 39 24 9 28 63 41

Answer 1

Main.java

import java.awt.Point;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main
{
int[][] chessBoard;

List<Point>[][] availableMoves;

final static int NOTUSED = -1;

final static Point[] DIRECTION = new Point[] { new Point( -1, -2 ), new Point( 1, -2 ), new Point( 2, -1 ), new Point( 2, 1 ), new Point( 1, 2 ),
new Point( -1, 2 ), new Point( -2, 1 ), new Point( -2, -1 ) };

int size;

public Main( int n )
{
size = n;
chessBoard = new int[n][n];
availableMoves = new List[n][n];
for ( int y = 0; y < n; y++ )
{
for ( int x = 0; x < n; x++ )
{
chessBoard[x][y] = NOTUSED;
availableMoves[x][y] = new ArrayList<>();
for ( Point d : DIRECTION )
{
//calculate the new position
int nx = x + d.x;
int ny = y + d.y;

//only process valid moves
if ( ( nx >= 0 && nx < size ) && ( ny >= 0 && ny < size ) )
{
availableMoves[x][y].add( new Point(nx,ny) );
}
}
}
}
//we need to sort the possiblemoves, so that the first move is the one that has the least possiblemoves
processedPossibleMoves( );
}

private void processedPossibleMoves()
{
for ( int y = 0; y < size; y++ )
{
for ( int x = 0; x < size; x++ )
{
List<Point> moves = availableMoves[x][y];

moves.sort( new Comparator<Point>()
{

@Override
public int compare( Point o1, Point o2 )
{
int o1Moves = availableMoves[o1.x][o1.y].size();
int o2Moves = availableMoves[o2.x][o2.y].size();
return o1Moves - o2Moves;
}
});
}
}
}

private void printBoard()
{
for ( int y = 0; y < size; y++ )
{
for ( int x = 0; x < size; x++ )
{
System.out.printf( "%2d ", chessBoard[x][y] );
}
System.out.println();
}
System.out.println();

}

private Main solve()
{
int x = 0;
int y = 0;
int current = 0;

discoverTour( x, y, current );
return this;
}

private boolean discoverTour( int x, int y, int current )
{
if ( chessBoard[x][y] != NOTUSED )
{
return false;
}

//Mark current positoin as 'current'
chessBoard[x][y] = current;

if ( current == size * size - 1 )
{
//done :)
return true;
}

for ( Point d : availableMoves[x][y])
{
if ( discoverTour( d.x, d.y, current + 1 ) )
{
return true;
}
}

//if we are here, all our options ran out :(
//reset the current cell and return false
chessBoard[x][y] = NOTUSED;

return false;
}

public static void main( String[] args )
{
new Main( 8 ).solve().printBoard();
}
}

SAMPLE OUTPUT:

CAWindows System321cmd.exe C:\UsersISAM\Desktoplcg javal1l>javac Main.java ote: Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details. :\UsersISAM\Desktoplcg javalll>java Main 0 15 38 31 2 17 48 21 39 30 1 16 49 20 3 18 14 37 50 55 32 61 22 47 29 40 63 60 51 54 19 4 36 13 56 53 62 33 46 23 1 28 59 34 57 52 5 8 12 35 26 43 10 7 24 45 27 42 11 58 25 44 9 6 C: \UsersISAM\Desktop\cg\java\ll>