code: package com.knight.tour;
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.Comparator;
  import java.util.List;
  
  public class KT {
  
  	private int baseSize = 12; // virtual board size including unreachable out-of-board nodes. i.e. base 12 = 8X8 board	
  	int actualBoardSize = baseSize - 4;
  	private static final int[][] moves = { { 1, -2 }, { 2, -1 }, { 2, 1 }, { 1, 2 }, { -1, 2 }, { -2, 1 }, { -2, -1 },
  			{ -1, -2 } };
  	private static int[][] grid;
  	private static int totalNodes;
  	private ArrayList<int[]> travelledNodes = new ArrayList<>();
  	public KT(int baseNumber) {
  		this.baseSize = baseNumber;
  		this.actualBoardSize = baseSize - 4;
  	}
  
  	public static void main(String[] args) {
  		new KT(12).tour(); // find a solution for 8X8 board
  //		new KT(24).tour(); // then for 20X20 board
  //		new KT(104).tour(); // then for 100X100 board
  	}
  
  	private void tour() {
  		totalNodes = actualBoardSize * actualBoardSize;
  		travelledNodes.clear();
  		grid = new int[baseSize][baseSize];
  		for (int r = 0; r < baseSize; r++)
  			for (int c = 0; c < baseSize; c++) {
  				if (r < 2 || r > baseSize - 3 || c < 2 || c > baseSize - 3) {
  					grid[r][c] = -1; // mark as out-of-board nodes
  				} else {
  					grid[r][c] = 0; // nodes within chess board.
  				}
  			}
  		// start from a random node
  		int startRow = 2 + (int) (Math.random() * actualBoardSize);
  		int startCol = 2 + (int) (Math.random() * actualBoardSize);
  		int[] start = { startRow, startCol, 0, 1 };
  		grid[startRow][startCol] = 1; // mark the first traveled node
  		travelledNodes.add(start); // add to partial solution chain, which will only have one node.
  
  		// Start traveling forward
  		autoKnightTour(start, 2);
  	}
  
  	// non-backtracking touring methods. Re-chain the partial solution when all neighbors are traveled to avoid back-tracking.
  	private void autoKnightTour(int[] start, int nextCount) {
  		List<int[]> nbrs = neighbors(start[0], start[1]);
  		if (nbrs.size() > 0) {
  			Collections.sort(nbrs, new Comparator<int[]>() {
  				public int compare(int[] a, int[] b) {
  					return a[2] - b[2];
  				}
  			}); // sort the list
  			int[] next = nbrs.get(0); // the one with the less available neighbors - Warnsdorff's algorithm
  			next[3] = nextCount;
  			travelledNodes.add(next);
  			grid[next[0]][next[1]] = nextCount;
  			if (travelledNodes.size() == totalNodes) {
  				System.out.println("Found a path for " + actualBoardSize + " X " + actualBoardSize + " chess board.");
  				StringBuilder sb = new StringBuilder();
  				sb.append(System.lineSeparator());
  				for (int idx = 0; idx < travelledNodes.size(); idx++) {
  					int[] item = travelledNodes.get(idx);
  					sb.append("->(" + (item[0] - 2) + "," + (item[1] - 2) + ")");
  					if ((idx + 1) % 15 == 0) {
  						sb.append(System.lineSeparator());
  					}
  				}
  				System.out.println(sb.toString() + "\n");
  			} else { // continuing the travel
  				autoKnightTour(next, ++nextCount);
  			}
  		} else { // no travelable neighbors next - need to rechain the partial chain
  			int[] last = travelledNodes.get(travelledNodes.size() - 1);
  			travelledNodes = reChain(travelledNodes);
  			if (travelledNodes.get(travelledNodes.size() - 1).equals(last)) {
  				travelledNodes = reChain(travelledNodes);
  				if (travelledNodes.get(travelledNodes.size() - 1).equals(last)) {
  					System.out.println("Re-chained twice but no travllable node found. Quiting...");
  				} else {
  					int[] end = travelledNodes.get(travelledNodes.size() - 1);
  					autoKnightTour(end, nextCount);
  				}
  			} else {
  				int[] end = travelledNodes.get(travelledNodes.size() - 1);
  				autoKnightTour(end, nextCount);
  			}
  		}
  	}
  
  	private ArrayList<int[]> reChain(ArrayList<int[]> alreadyTraveled) {
  		int[] last = alreadyTraveled.get(alreadyTraveled.size() - 1);
  		List<int[]> candidates = neighborsInChain(last[0], last[1]);
  		int cutIndex;
  		int[] randomPicked = candidates.get((int) Math.random() * candidates.size());
  		cutIndex = grid[randomPicked[0]][randomPicked[1]] - 1;
  		ArrayList<int[]> result = new ArrayList<int[]>(); //create empty list to copy already traveled nodes to
  		for (int k = 0; k <= cutIndex; k++) {
  			result.add(result.size(), alreadyTraveled.get(k));
  		}
  		for (int j = alreadyTraveled.size() - 1; j > cutIndex; j--) {
  			alreadyTraveled.get(j)[3] = result.size();
  			result.add(result.size(), alreadyTraveled.get(j));
  		}
  		return result; // re-chained partial solution with different end node
  	}
  
  	private List<int[]> neighborsInChain(int r, int c) {
  		List<int[]> nbrs = new ArrayList<>();
  		for (int[] m : moves) {
  			int x = m[0];
  			int y = m[1];
  			if (grid[r + y][c + x] > 0 && grid[r + y][c + x] != grid[r][c] - 1) {
  				int num = countNeighbors(r + y, c + x);
  				nbrs.add(new int[] { r + y, c + x, num, 0 });
  			}
  		}
  		return nbrs;
  	}
  
  	private static List<int[]> neighbors(int r, int c) {
  		List<int[]> nbrs = new ArrayList<>();
  		for (int[] m : moves) {
  			int x = m[0];
  			int y = m[1];
  			if (grid[r + y][c + x] == 0) {
  				int num = countNeighbors(r + y, c + x);
  				nbrs.add(new int[] { r + y, c + x, num, 0 }); // not-traveled neighbors and number of their neighbors
  			}
  		}
  		return nbrs;
  
  	}
  
  	private List<int[]> extendableNeighbors(List<int[]> neighbors) {
  		List<int[]> nbrs = new ArrayList<>();
  		for (int[] node : neighbors) {
  			if (node[2] > 0)
  				nbrs.add(node);
  		}
  		return nbrs;
  	}
  
  	private static int countNeighbors(int r, int c) {
  		int num = 0;
  		for (int[] m : moves) {
  			if (grid[r + m[1]][c + m[0]] == 0) {
  				num++;
  			}
  		}
  		return num;
  	}
  }
  