Chess Knights Tour implementation in java.

A knight’s tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight’s move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open.

package com.test.graph;

import java.util.Stack;

public class KnightsTour {
	
	private int [][]chess;
	private int size;
	private static int count=0; // to maintain matrix type printing format
	public KnightsTour(int size){
		this.size=size;
		chess = new int[size][size];
	}
	
	/*
	 * This function print knight tour for a given starting point. knight will visit each vertex only once. 2-1/2 step at a time
	 */
	public void dfs(int knightLoc){
		
		int row, col,top,temp;
		Stack<Integer> stack = new Stack<Integer>();
		row = knightLoc/size;
		col = knightLoc%size;
		chess[row][col]=1;
		System.out.print("["+(row*8+col)+"]");
		count++;
		//System.out.println("Chess["+row+"]["+col+"]="+1);
		stack.push(knightLoc);
		
		while (!stack.isEmpty()) {
			top = stack.peek();
			
			if ( (temp = getAdjUnvistedVertex(top)) != -1) {
				row = temp/size;
				col = temp%size;
				chess[row][col]=1;
				if (count % 8 == 0 )System.out.println(); // to print in matrix format
				System.out.print("["+(row*8+col)+"]");
				count++;
				//System.out.println("Chess["+row+"]["+col+"]="+1);
				stack.push(temp); // temp is knight next location
			} else {
				stack.pop();
			}
		}
	}
	
	/*
	 * At max each knight position can have 8 locations to move.
	 * ----LEFT------------,-------RIGHT-----------
	 * 1. [row - 2, col - 1],2. [row - 2, col + 1]
	 * 3. [row - 1, col - 2],4. [row - 1, col + 2]
	 * 5. [row + 1, col - 2],6. [row + 1, col + 2]
	 * 7. [row + 2, col - 1],8. [row + 2, col + 1]
	 * 
	 * If we have 0 based indexing then loc = row * size + col
	 * row = loc/size
	 * col = loc%size
	 * }
	 * else { // for indexing starting from 1.
	 * loc =  row * size
	 * 
	 * 		if (loc % size == 0){
	 *  		row = loc/size;
	 *  		col = loc/row;
	 *  	} else {
	 *  		row = loc/size + 1;
	 *  		col = loc%size;
	 * 
	 *  	}
	 *  }//else end
	 * 
	 */
	private int getAdjUnvistedVertex(int top) {
		int row, col, rowIndex, leftColIndex, rightColIndex, i, j, index;
		row = top/size;
		col = top%size;
		
		for (i=-2; i<=2; i++){
			if (i==0){
				continue; 
			}
			
			if (i%2==0) {
				index=1;
			} else {
				index=2;
			}
			
			rowIndex = row+i;
			leftColIndex = col-index;
			rightColIndex= col+index;
			
			if ( rowIndex >=0 && rowIndex < size){ // each 2 step forward has two moves 1.left n 2.right--which is 1/2 step
				
				if ( leftColIndex >=0 && leftColIndex < size) { // checking boundary conditions
					if (chess[rowIndex][leftColIndex] == 0)
						return (rowIndex*size + leftColIndex); // knight next step loc
				}
				if ( rightColIndex >=0 && rightColIndex < size) { // checking boundary conditions
					if (chess[rowIndex][rightColIndex] == 0)
						return (rowIndex*size + rightColIndex); // knight next step loc
				}
			}
			
		}
		return -1;
	}

	public static void main(String[] args) {
		KnightsTour knightsTour = new KnightsTour(8);
		knightsTour.dfs(0);
	}
}