# Knight’s tour code

Posted on

Problem

Another one for some late night snack. – Knight’s tour!

``````package com.komal.backtracking;

import java.util.concurrent.TimeUnit;

public class KnightsTour {
static int size = 6;
static int[][] chessBoard = new int[size][size];
static int move;
static int noOfBacktrackCalls;

public boolean tourBackTrackRoutine(int row, int col) {
boolean flag = false;
noOfBacktrackCalls++;
if (!isMoveSafe(row, col)) {
return false;
}
move++;
chessBoard[row][col] = move;

if (move == size * size) {
return true;
}

flag = true;

int counter = 0;

for (int i[] : possibleMoves) {
counter++;
int newX = row + i[0];
int newY = col + i[1];
if (flag = tourBackTrackRoutine(newX, newY)) {
return true;
} else {
if (counter == possibleMoves.length) {
move--;
chessBoard[row][col] = 0;
return flag;
} else {
continue;
}
}
}
return flag;

}

public boolean isMoveSafe(int row, int col) {

if (row < 0 || col < 0 || !(row < size) || !(col < size)) {
return false;
}

if (row == size || col == size) {
return false;
}
if (chessBoard[row][col] > 0) {
return false;
} else {
return true;
}
}

int[][] possibleMoves = { { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 }, { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 } };

public static void main(String[] args) {
System.out.println("Solving...");
long startTime = System.nanoTime();
if (new KnightsTour().tourBackTrackRoutine(0, 0)) {
System.out.println("Solved!!");
} else {
System.out.println("Cannot be solved!!");
}
long timeTaken = TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - startTime);
System.out.println("nCompleted in :" + timeTaken + " milli sec");
System.out.println("nTook " + noOfBacktrackCalls + " backtrack calls for completion!");
for (int[] i : chessBoard) {
System.out.print("n{");
for (int i1 : i) {
System.out.print(i1 + ",t");
}
System.out.print("}");
}
}

}
``````

Output:

``````Solving...
Solved!!

Completed in :382 milli sec

Took 20092518 backtrack calls for completion!

{1, 12, 21, 28, 7,  10, }
{22,29, 8,  11, 20, 27, }
{13,2,  23, 4,  9,  6,  }
{30,35, 32, 17, 26, 19, }
{33,14, 3,  24, 5,  16, }
{36,31, 34, 15, 18, 25, }
``````

Solution

``````    static int size = 6;
``````

This should be `final`, as you don’t change it.

``````        boolean flag = false;
noOfBacktrackCalls++;
if (!isMoveSafe(row, col)) {
return false;
}
move++;
chessBoard[row][col] = move;

if (move == size * size) {
return true;
}

flag = true;
``````

You initialize `flag` and then set it to something else without ever using it. Why bother? You could just say

``````        noOfBacktrackCalls++;
if (!isMoveSafe(row, col)) {
return false;
}
move++;
chessBoard[row][col] = move;

if (move == size * size) {
return true;
}

boolean solved = true;
``````

I renamed it to `solved` after I figured out what it was. The name `flag` didn’t help me much with understanding what it did.

And the truth is that you don’t need it. I’d simplify down to

``````        noOfBacktrackCalls++;
move++;
chessBoard[row][col] = move;

if (move == size * size) {
return true;
}
``````

Note that other code will have to change to make this work.

``````        int counter = 0;

for (int i[] : possibleMoves) {
counter++;
int newX = row + i[0];
int newY = col + i[1];
if (flag = tourBackTrackRoutine(newX, newY)) {
return true;
} else {
if (counter == possibleMoves.length) {
move--;
chessBoard[row][col] = 0;
return flag;
} else {
continue;
}
}
}
return flag;
``````

First, that `continue` doesn’t do anything. You’re already at the end of the loop. You can just let it finish. And without the `continue`, you don’t need the `else` block.

As I said earlier, you don’t actually need `flag`. You never set it to `true` except initially. The first time that you `return flag`, it will always be `false`. You just set it to `false` before the `else` block. Otherwise the `else` wouldn’t run. The second `return` will only be reached if there are no possible moves or if `flag` is false. If you set `flag` to true in the loop, you always `return` immediately. And you know that `possibleMoves` is not empty, as you set it.

I’d write this block

``````        for (int i[] : possibleMoves) {
int newX = row + i[0];
int newY = col + i[1];
if (isMoveSafe(newX, newY) && tourBackTrackRoutine(newX, newY)) {
return true;
}
}

move--;
chessBoard[row][col] = 0;

return false;
``````

No `flag` needed.

I also removed `counter`. You were only using it to give a different behavior on the last iteration of the loop. But putting the code outside the loop accomplishes the same thing.

I moved the `isMoveSafe` to here so that it runs before the recursive call.

### Performance

The performance is determined by the algorithm here. These changes tweak performance a bit, but the algorithm is still the problem. You may want to check out some previous questions for more ideas. E.g.