/**
 * Author: Jean-Michel Richer
 * Date: September 2025
 * 
 * Resolution of the Knight's Tour problem which consist in finding
 * a hamiltonian path that visits each cell of a chessboard of size NxN
 * only once.
 * 
 * 
 * Results on AMD Ryzen 5 9600X
 *   N #Solutions Time(s)
 *   4          0     0.002 s
 *   5        304     0.022 s
 *   6     524488   165.809 s
 */
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstring>
#include <cstdint>
using namespace std;
#include <getopt.h>


string b_green = "\033[32m";
string e_green = "\033[0m";
string b_red = "\033[31m";
string e_red = "\033[0m";

// chessboard dimension (N)
int dimension = 5;

// number of solutions found
uint64_t nbr_solutions = 0;


/**
 * Class represents a coordinate on the chessboard
 */
class Coordinate {
public:
    int y, x;

    /**
     * Default constructor
     */
    Coordinate() {
        y = x = 0;
    }

    /**
     * Constructor from coorindate y and x
     */
    Coordinate( int _y, int _x) {
        y = _y;
        x = _x;
    }

    /**
     * Copy constructor
     */
    Coordinate(const Coordinate& obj) {
        y = obj.y;
        x = obj.x;
    }

    /**
     * Overloading of assignment operator
     */
    Coordinate& operator=(const Coordinate& obj) {
        if (this != &obj) {
            y = obj.y;
            x = obj.x;
        }
        return *this;
    }

    /**
     * Overloading of addition operator
     */
    Coordinate operator+(const Coordinate& rhs) const {
        return Coordinate(this->y + rhs.y, this->x + rhs.x);
    }

    /**
     * Overloading of output operator
     */
    friend ostream& operator<<(ostream& out, Coordinate& obj) {
        out << '(' << obj.y << ',' << obj.x << ')';
        return out;
    }
};

// ------------------------------------------------------------------
// Definition of the moves of the knight from an initial position
const int MAX_MOVES = 8;
vector<Coordinate> moves = { Coordinate(1,2), Coordinate(2,1), 
    Coordinate(2,-1), Coordinate(1,-2), 
    Coordinate(-1,-2), Coordinate(-2,-1), 
    Coordinate(-2,1),  Coordinate(-1,2) };


/**
 * Class that represents the chessboard
 */
class Chessboard {
public:
    static const int EMPTY = 0;

    // dimension of chessboard
    int dim;
    // size = dimension * dimension
    size_t size;
    // allocated array of data
    int *data;

    /**
     * Default constructor
     * @param rows number of rows or number of columns
     */
    Chessboard(int rows) {
        dim = rows; 
        size = dim * dim;
        data = new int [ size ];
        for (size_t i = 0; i < size; ++i) {
            data[i] = EMPTY;
        }
    }

    /**
     * Copy constructor
     */
    Chessboard(Chessboard& obj) {
        dim = obj.dim;
        size = dim * dim;
        data = new int [ size ];
        memcpy(data, obj.data, sizeof(int) * size);
    }

    /**
     * Overloading of assignment operator
     */
    Chessboard& operator=(const Chessboard& obj) {
        if (&obj != this) {
            dim = obj.dim;
            size = dim * dim;
            memcpy(data, obj.data, sizeof(int) * size);
        }
        return *this;
    }

    /**
     * Overloading of operator [] to access a cell given
     * its coordinates
     */
    int& operator[](Coordinate& c) {
        return data[c.y * dim + c.x];
    }

    /**
     * Tells if coordinate c is inside [0,dimension-1]
     * and if cell of coordinate c is EMPTY
     */
    bool is_valid(Coordinate& c) {
        if ((0 <= c.x) and (0 <= c.y) and (c.x < dim) and (c.y < dim)) {
            return data[c.y * dim + c.x ] == EMPTY;
        } else {
            return false;
        }
    }

    /**
     * Overloading of output operator
     */
    friend ostream& operator<<(ostream& out, Chessboard& obj) {
        for (int y = 0; y < obj.dim; ++y) {
            for (int x = 0; x < obj.dim; ++x) {
                int value = obj.data[y * obj.dim + x] ;

                if (value == 1) {
                    out << b_green << setw(4) << value << e_green;
                } else if (value == static_cast<int>(obj.size)) {
                    out << b_red << setw(4) << value << e_red;
                } else {
                    out << setw(4) << value;
                }
                
                out << ' ';
            }
            out << endl;
        }
        return out;
    }
};

/**
 * procedure used to recursively solve the problem.
 * Given a chessboard 'board' and a coordinate 'c' and the 'iteration'
 * we try to move the knight from 'c' to another valid position and 
 * continue the search until we have visited all the cells
 */
void solve(Chessboard& board, Coordinate c, int iteration) {

    if (iteration == static_cast<int>(board.size)) {
        // we have visited all the cells, so we have a new solution
        board[c] = iteration;
        ++nbr_solutions;
        if (nbr_solutions == 1) {
            cout << board << endl;
        }
        board[c] = Chessboard::EMPTY;
    } else {
        // otherwise try to move the knight to another cell
        // that has not been visited
        board[c] = iteration;
        for (auto m : moves) {
            Coordinate d = c + m;
            if (board.is_valid(d)) {
                //cout  << "goto " << d << endl;
                //cout << board << endl << endl;
                solve(board, d, iteration+1);
            }
        }
        board[c] = Chessboard::EMPTY;
    }
}

/**
 * Main function
 */
int main(int argc, char *argv[]) {

    int opt;

    while ((opt = getopt(argc, argv, "n:")) != -1) {
        switch (opt) {
        case 'n':
            dimension = std::stoi(optarg);
            break;
        
        default: /* '?' */
            cerr << "Usage: " << argv[0] << "[-n dimension]" << endl;
            exit(EXIT_FAILURE);
        }
    }

    // create chessboard
    Chessboard chessboard(dimension);

    // start from this position to find paths
    Coordinate top_left(0,0);

    // find the hamiltonian paths
    solve(chessboard, top_left, 1);
    
    // report number of paths found
    cout << "nbr_solutions=" << nbr_solutions << endl;

    return EXIT_SUCCESS;

}