Knights

#include <iostream>using namespace std;struct Node {    Node* parent;    bool board[8][8];    char x, y;    unsigned short int level;    int children;};static Node* leaf;static int leaves_count = 0;static int MAX_LEAVES = 500000;bool inBounds(char i, char j){    return (i >= 0) && (i < 8) && (j >= 0) && (j < 8);}bool move(int dir, char x, char y, char* i, char* j, bool board[8][8]){    static int moves[16][2] = { {1,2},{1,2},{2,1},{2,1},{2,-1},{2,-1},{1,-2},{1,-2},{-1,-2},{-1,-2},{-2,-1},{-2,-1},{-2,1},{-2,1},{-1,2},{-1,2} };    static int trails[16][4] = { {0,1,0,2},{1,0,1,1},{0,1,1,1},{1,0,2,0},{1,0,2,0},{0,-1,1,-1},{1,0,1,-1},{0,-1,0,-2},                                 {0,-1,0,-2},{-1,0,-1,-1},{0,-1,-1,-1},{-1,0,-2,0},{-1,0,-2,0},{0,1,-1,1},{-1,0,-1,1},{0,1,0,2} };    *i = x + moves[dir][0];    *j = y + moves[dir][1];    if (!inBounds(*i, *j)) {      return false;    }    int x1, x2, y1, y2;    x1 = x + trails[dir][0];    y1 = y + trails[dir][1];    x2 = x + trails[dir][2];    y2 = y + trails[dir][3];    if (!board[x1][y1] && !board[x2][y2] && !board[*i][*j]) {        board[x1][y1] = true;        board[x2][y2] = true;        board[*i][*j] = true;        return true;    } else {        return false;    }}void copyBoard(bool from[8][8], bool to[8][8]){  for (int i = 0; i < 8; i++)    for (int j = 0; j < 8; j++)      to[i][j] = from[i][j];  return;}void freemem(Node* node){    Node* tmp;    while (node->parent != 0) {        tmp = node;        node = tmp->parent;        if (tmp->children = 0) {            tmp->parent->children--;            delete tmp;        }    }}void generate(Node* node){    bool board[8][8];    char i, j, c;    if (leaves_count > MAX_LEAVES) return;    c = 0;    for (int dir = 0; dir < 16; dir++) {        copyBoard(node->board, board);        if (move(dir, node->x, node->y, &i, &j, board)) {            node->children++;            Node* child = new Node;            copyBoard(board, child->board);            child->parent = node;            child->x = i;            child->y = j;            child->level = node->level + 1;            child->children = 0;            generate(child);            c++;        }    }    if (!c) {        if (node->level >= leaf->level) {            leaf = node;        } else {            freemem(node);        }                leaves_count++;    }    return;}int main(int argc, char** argv){    Node root;    if (argc > 2) {        root.x = atoi(argv[1]);        root.y = atoi(argv[2]);    }    if (!inBounds(root.x, root.y)) {        root.x = 0;        root.y = 0;    }    root.level = 0;    root.parent = 0;    root.children = 0;    leaf = &root;    int i, j;    for (i = 0; i < 8; i++)      for (j = 0; j < 8; j++)        root.board[i][j] = false;    root.board[root.x][root.y] = true;    if (argc > 3) MAX_LEAVES = atoi(argv[3]);    generate(&root);    cout << "Moves: " << leaf->level << endl;    char board[8][8];    for (i = 0; i < 8; i++)      for (j = 0; j < 8; j++)        board[i][j] = '0';    Node* cur;    i = 1;    cur = leaf;    while( cur->parent != 0) {        board[cur->x][cur->y] = (char)('A' + leaf->level - i);        i++;        cur = cur->parent;    }    board[root.x][root.y] = '*';    for (i = 0; i < 8; i++) {      for (j = 0; j < 8; j++) {            cout << board[i][j] << ' ';      }      cout << endl;    }    return 0;}