package mayton;

import java.util.Random;

import static java.lang.System.out;

public class MaytonsKnightTour {

    int[][] desk;

    int width;
    int height;

    int size;

    Random random;

    long randomSeed;

    public void cleanDesk(){
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                desk[i][j] = 0;
            }
        }
    }

    public MaytonsKnightTour(int height,int width) {
        this.width  = width;
        this.height = height;
        this.size = width * height;
        desk = new int[height][width];
        random = new Random();
    }

    public void solve(int i1,int j1,long randomSeed) {
        this.randomSeed = randomSeed;
        random.setSeed(randomSeed);
        cleanDesk();
        findPath(i1, j1, 1);
    }

    public boolean findPath(int i, int j, int level) {

        final int[] istep = {2, 1,-1,-2,-2,-1, 1, 2};
        final int[] jstep = {1, 2, 2, 1,-1,-2,-2,-1};


        if (desk[i][j] != 0) {
            return false;
        }

        desk[i][j] = level;

        if (level == size) {
            print();
            desk[i][j]=0;
            return true;
        }

        int rot = random.nextInt(8);

        for (int k = 0; k < 8; k++) {
            int krot = (k + rot) & 0x7;
            int iv = i + istep[krot];
            if (iv >= 0 && iv < height) {
                int jv = j + jstep[krot];
                if (jv >= 0 && jv < width) {
                    if (findPath(iv, jv, level + 1)) {
                        return true;
                    }
                }
            }
        }

        desk[i][j] = 0;
        return false;

    }

    public void print() {
        out.printf("\n== Solution with seed = %08Xh, size = (%d,%d) \n\n",randomSeed,height,width);
        String formatExpr = size < 100 ? "%02d " : "%03d ";
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                out.printf(formatExpr, desk[i][j]);
            }
            out.println();
        }
        out.printf("\n===============================\n");
    }

    public static void main(String[] args) {
        MaytonsKnightTour mkt = new MaytonsKnightTour(5,7);
        mkt.solve(0,0,0L);
        mkt.solve(0,0,1L);
        mkt.solve(0,0,2L);
    }

}

package mayton;

import com.google.common.util.concurrent.ThreadFactoryBuilder;

import java.io.PrintStream;
import java.util.Random;
import java.util.concurrent.*;

import static java.lang.Long.numberOfLeadingZeros;
import static java.lang.System.out;
import static java.util.Arrays.fill;

public class MaytonsKnightTour {

    static final int KNIGHT_DIRECTIONS = 8;

    int i1;
    int j1;

    int[] desk;

    int width;
    int extendedWidth;
    int ws;
    int height;

    int size;

    Random random;

    long randomSeed;

    public void cleanDesk(){
        fill(desk,0);
    }

    public MaytonsKnightTour(int height,int width,int i1,int j1,long randomSeed) {
        this.width  = width;
        this.height = height;
        this.extendedWidth = Utuls.clp2(width);
        this.ws = Utuls.log2up(width);
        this.size = width * height;
        this.i1 = i1;
        this.j1 = j1;
        this.randomSeed = randomSeed;
        desk = new int[height * extendedWidth];
        random = new Random();
    }

    public void solve(){
        cleanDesk();
        findPath(i1, j1, 1);
    }

    public void solve(int i1,int j1,long randomSeed) {
        this.randomSeed = randomSeed;
        random.setSeed(randomSeed);
        cleanDesk();
        findPath(i1, j1, 1);
    }

    public boolean findPath(int i, int j, int level) {

        final int[] istep = {2, 1,-1,-2,-2,-1, 1, 2};
        final int[] jstep = {1, 2, 2, 1,-1,-2,-2,-1};

        int offset = (i<< ws) + j;

        if (desk[offset] != 0) {
            return false;
        }

        desk[offset] = level;

        if (level == size) {
            print(System.out);
            desk[offset]=0;
            return true;
        }

        int rot = random.nextInt(KNIGHT_DIRECTIONS);

        for (int k = 0; k < KNIGHT_DIRECTIONS; k++) {
            int krot = (k + rot) & 0x7;
            int iv = i + istep[krot];
            if (iv >= 0 && iv < height) {
                int jv = j + jstep[krot];
                if (jv >= 0 && jv < width) {
                    if (findPath(iv, jv, level + 1)) {
                        return true;
                    }
                }
            }
        }

        desk[offset] = 0;
        return false;

    }

    public void print(PrintStream out) {
        synchronized (out) {
            out.printf("\n== Solution with seed = %08Xh, size = (%d,%d) \n\n", randomSeed, height, width);
            String formatExpr = size < 100 ? "%02d " : "%03d ";
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    out.printf(formatExpr, desk[(i << ws) + j]);
                }
                out.println();
            }
            out.printf("\n===============================\n");
        }
    }

    public static void main(String[] args) {

        final int THREADS = 4;
        final int M = 100; // Integer.valueOf(args[0]);

        ThreadFactory knightTourThreadFactory = new ThreadFactoryBuilder()
                .setNameFormat("Knight-Tour-Thread-%d")
                .setDaemon(false)
                .build();

        ExecutorService executor = Executors.newFixedThreadPool(THREADS, knightTourThreadFactory);

        try {
            for (int i = 0; i < M; i++) {
                executor.execute(new MaytonsKnightTourThread(
                        new MaytonsKnightTour(5, 7, 0, 0, (long)i))); // 8x8 - Too slow...
            }
        } finally {
            executor.shutdown();
        }
    }

}