Knight's tour code

Question

Another one for some late night snack. - Knight's tour! Please provide your suggestions/flaws/optimization to this knight's tour backtracking code..

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, }

Answer 1

    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.

• Knight's Tour with Heuristics
• Optimizing this Knight's Tour