knight.java

package com.gavlak;

import java.awt.*;

/**
 * Created by gavlak on 06/03/17.
 */
public class KnightsTour {

    static final Point[] moves = new Point[]{
        new Point(2, 1),
        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)
    };

    int[][] steps;
    int size;
    boolean solutionFound = false;

    public KnightsTour(int size)
    {
        this.size = size;
        steps = new int[size][size];

        for (int x = 0; x < size; x++)
            for (int y = 0; y < size; y++)
                steps[x][y] = -1;
    }

    public void solve(int x, int y)
    {
        this.steps[x][y] = 1;

        if (backtrack(x, y, 2))
            solutionFound = true;
    }

    private boolean inBounds(int x, int y, int size)
    {
        return ((x >= 0 && x < size) && (y >= 0 && y < size) && steps[x][y] == -1);
    }

    private boolean backtrack(int x, int y, int move_index)
    {
        if (move_index > this.size * this.size)
            return true;

        for (Point move : moves)
        {
            int next_x = x + move.x;
            int next_y = y + move.y;

            if (inBounds(next_x, next_y, size))
            {
                steps[next_x][next_y] = move_index;

                if (backtrack(next_x, next_y, move_index + 1))
                    return true;
                else
                    steps[next_x][next_y] = -1;
            }
        }

        return false;
    }

    @Override
    public String toString()
    {
        String s = "";

        for (int x = 0; x < steps.length; x++)
        {
            for (int y = 0; y < steps.length; y++)
                s += String.format(" %2d", steps[x][y]);

            s += "\n";
        }

        return s;
    }

    public void print()
    {
        if (solutionFound)
            System.out.println(this);
        else
            System.out.println("Nenasla sa ziadna cesta");
    }

    public static void main(String[] args)
    {
        int size = 8;
        KnightsTour k = new KnightsTour(size);
        k.solve(0, 0);
        k.print();
    }
}