//module knightstour.Miller;

import std.stdio: writefln;
//import d.func: fastSort; // not necessary, but speeds up

const N = 8;

int[N][N] board;
int moves_left;
ulong steps;

struct Loc {
    int x, y;

    // how many other tiles each tile may be accessed from
    static const int[N][N] access = [[2, 4, 6, 6, 6, 6, 4, 2],
                                     [4, 6, 8, 8, 8, 8, 6, 4],
                                     [6, 6, 8, 8, 8, 8, 6, 6],
                                     [6, 6, 8, 8, 8, 8, 6, 6],
                                     [6, 6, 8, 8, 8, 8, 6, 6],
                                     [6, 6, 8, 8, 8, 8, 6, 6],
                                     [4, 6, 8, 8, 8, 8, 6, 4],
                                     [2, 4, 6, 6, 6, 6, 4, 2]];

    int opCmp(typeof(*this) l) {
        return access[x][y] - access[l.x][l.y];
    }
}


Loc[] get_legal_moves(Loc position) {
    static const int vectors[2][N] = [[1, 1,-1,-1, 2, 2,-2,-2],
                                      [2,-2, 2,-2, 1,-1, 1,-1]];

    Loc[] legal_moves;
    Loc new_loc;

    for (int i = 0; i < N; i++) {
        new_loc.x = position.x + vectors[0][i];
        new_loc.y = position.y + vectors[1][i];
        if (isLegalLocation(new_loc) && board[new_loc.x][new_loc.y] < 0)
            legal_moves ~= new_loc;
    }
    return legal_moves.sort;
    // return legal_moves.fastSort();
}

bool isLegalLocation(Loc l) {
    return (l.x < N && l.x > -1) && (l.y < N && l.y > -1);
}

void clear_board() {
    foreach (ref row; board)
        row[] = -1;
}

int move(Loc myloc) {
    board[myloc.x][myloc.y] = moves_left++;
    steps++;
    if (moves_left == N * N)
        return 0;

    foreach (l; get_legal_moves(myloc))
        if (move(l) == 0)
            return 0;
    board[myloc.x][myloc.y] = -1;
    moves_left--;
    return -1;
}

void print_solution(int start_loc_x, int start_loc_y, int steps) {
    writefln("Found solution %d %d in %d steps", start_loc_x, start_loc_y, steps);
    foreach(r; board)
        writefln("%2d  %2d  %2d  %2d  %2d  %2d  %2d  %2d",r[0],r[1],r[2],r[3],r[4],r[5],r[6],r[7]);
    writefln();
}

void print_moves(int start_loc_x, int start_loc_y) {
    char[2 * N * N] moves;

    foreach(r, row; board)
        foreach(c, el; row) {
            moves[el * 2] = '0' + r;
            moves[el * 2 + 1] = '0' + c;
        }
    writefln(moves);
}

void main() {
    Loc moveloc;

    for (int start_loc_x = 0; start_loc_x < N; start_loc_x++)
        for (int start_loc_y = 0; start_loc_y < N; start_loc_y++) {
            clear_board();
            moves_left = 0;
            steps = 0;
            moveloc.x = start_loc_x;
            moveloc.y = start_loc_y;
            move(moveloc);
            print_solution(start_loc_x, start_loc_y, steps);
            //print_moves(start_loc_x, start_loc_y);
        }
}