// -*- c++ -*-

// Problema calului de sah, rezolvare prin metoda greedy.
// Author: Mihai BAZON <mishoo@infoiasi.ro>, 2000
//                     <mbazon@websci.ro>

// Algoritm:  la fiecare pas se alege acel camp din care avem cele mai putine
//            mutari mai departe (dar totusi, din care avem macar o mutare).
// Implementare:  * clasa Table contine tabla in "m_", unde m_[i][j] este nenul
//                  daca am parcurs pozitia (i,j).  Daca m_[i][j] != 0 atunci
//                  m_[i][j] = numarul de pasi facuti pana la campul (i,j) + 1.
//                  Aceasta foloseste la reconstruirea drumului.
//                * variabila statica moves[8][2] retine toate deplasarile
//                  relative pe care le poate efectua calul de sah.
//                * o pozitie pe tabla de sah este un intreg (x * n + y), unde
//                  n x n este dimensiunea tablei iar 0 <= x,y < n sunt
//                  coordonatele campului respectiv.  Pentru simplificarea
//                  calculelor sunt disponibile macrourile X, Y:
//                             X(pos) = coordonata x a pozitiei pos
//                             Y(pos) =            y
//                  aceste macrouri se bazeaza pe existenta variabilei n_ din
//                  cadrul clasei, deci se pot folosi doar in cadrul clasei.
//                * macroul CELL(x, y) returneaza pozitia campului (x,y)
//                *         CHECK(x, y) testeaza daca pozitia specificata este
//                          in cadrul tablei de sah.
//                * clasa Table contine functiile:
//                    - void allowed(IntArray &a, int pos)
//                         umple tabloul de intregi a cu pozitiile in care
//                         calul poate muta plecand din pos.
//                    - void choosw(IntArray &a, int pos)
//                         alege din aceste pozitii pe cea din care vom putea
//                         efectua cele mai putine mutari in continuare
//                    - int nr_moves_from(int pos)
//                         returneaza numarul de mutari valide care se pot face
//                         din pozitia pos
//                    - bool solve()
//                         rezolva problema si intoarce true daca s-a gasit o
//                         solutie valida, sau false daca nu exista solutie
//                         prin metoda greedy.  Prin "rezolva problema"
//                         intelegem ca tabloul m_ va fi umplut cu valorile
//                         respective, descrise mai sus.

// TREBUIE RULAT SUB LINUX

#include <stdio.h>
#include <unistd.h>

#include <list>
#include <iostream>
#include <string>

using namespace std; // using std::list;

#define X(x) (x % n_)
#define Y(y) (y / n_)

#define CELL(x, y) (y * n_ + x)

#define MOVE(x, y) {x, y}

#ifdef DEBUG
#define DEBUG_FUNC_OUT \
cerr << __PRETTY_FUNCTION__ << endl;
#else
#define DEBUG_FUNC_OUT
#endif

static int moves[8][2] = {
    MOVE(-2, -1),
    MOVE(-1, -2),
    MOVE( 1, -2),
    MOVE( 2, -1),
    MOVE( 2,  1),
    MOVE( 1,  2),
    MOVE(-1,  2),
    MOVE(-2,  1)
};

#define CHECK(x, y) ((x >= 0) && (x < n_) && (y >= 0) && (y < n_))

typedef list<int> IntArray;

class Table
{
  protected:
    int n_;

    int **m_;

  public:
    Table(int n);
    ~Table();

    void allowed(IntArray &a, int from);
    int choose(IntArray &a, int from);
    int nr_moves_from(int from);
    int n();
    bool solve();

    int* operator [] (int index);
};

Table::Table(int n)
{
    n_ = n;

    m_ = new int*[n_];
    for (int i = 0; i < n_; i++) {
        m_[i] = new int[n_];
        for (int j = 0; j < n_; j++) {
            m_[i][j] = 0;
        }
    }
}

Table::~Table()
{
    for (int i = 0; i < n_; i++) {
        delete[] m_[i];
    }
    delete[] m_;
}

int
Table::nr_moves_from(int from)
{
    DEBUG_FUNC_OUT;
    
    int count = 0;
    int x = X(from);
    int y = Y(from);

    for (int i = 0; i < 8; i++) {
        int xx = x + moves[i][0];
        int yy = y + moves[i][1];
        if (CHECK(xx, yy) && (m_[xx][yy] == 0)) {
            count++;
        }
    }

    return count;
}

void
Table::allowed(IntArray &a, int from)
{
    DEBUG_FUNC_OUT;
    
    a.clear();

    int x = X(from);
    int y = Y(from);

    for (int i = 0; i < 8; i++) {
        int xx = x + moves[i][0];
        int yy = y + moves[i][1];
        if (CHECK(xx, yy) && (m_[xx][yy] == 0)) {
            a.push_back(CELL(xx, yy));
        }
    }
}

int
Table::choose(IntArray &a, int from)
{
    int min = 9;
    int pos = from;
    
    if (a.empty()) return -1;
    if (a.size() == 1) return *(a.begin());

    for (IntArray::iterator i = a.begin(); i != a.end(); i++) {
        int n = nr_moves_from(*i);
        if (n != 0 && n < min) {
            pos = *i;
            min = n;
        }
    }

    if (min == 9) return -1;
    return pos;
}

bool
Table::solve()
{
    int nr = 0;
    int pos = 0;

    while (pos >= 0) {
        m_[X(pos)][Y(pos)] = ++nr;
        IntArray a;
        allowed(a, pos);
        pos = choose(a, pos);
    }

    return (nr == n_ * n_);
}

int
Table::n()
{
    return n_;
}

int*
Table::operator [] (int index)
{
    return m_[index];
}

int main(int argc, char **argv)
{
    cout << "\033[H\033[2J";
    fflush(stdout);
    
    int n_;
    
    if (argc >= 2) {
        n_ = atoi(argv[1]);
    } else {
        n_ = 8;
    }
    
    Table t(n_);
    bool solved = t.solve();

    if (!solved) {
        cout << "problema nu are solutie folosind greedy" << endl;
    }

    int *p = new int[t.n() * t.n()];
    
    for (int i = 0; i < t.n(); i++) {
        for (int j = 0; j < t.n(); j++) {
            cout.width(5);
            cout << t[i][j];
            p[t[i][j] - 1] = CELL(i, j);
        }
        cout << endl << endl;
    }

    cout << "\033[1;32m";
    fflush(stdout);
    
    if (solved) {
        for (int i = 0; i < t.n() * t.n(); i++) {
            cout << "\033[" << 1 + 2 * X(p[i]) << ';' << 1 + 5 * Y(p[i]) << "H";
            fflush(stdout);
            cout.width(5);
            cout << i + 1;
            usleep(250000);
        }
    }

    cout << "\033[0m" << endl << endl;
    fflush(stdout);

    cout << "\033[20;1H";
    fflush(stdout);
}