#include using namespace std; class node; int **chess_field = NULL; int chess_field_occupied = 0; class node { public: int row, col; int n; int goal_row, goal_col; int level; bool has_already_children; node *parent; int child_index; node *children[6]; node(int r, int c,int nn,int gr,int gc,int l, node *par, int ci) : row(r), col(c), n(nn), goal_row(gr), goal_col(gc), level(l), has_already_children(false), parent(par), child_index(ci) {} // may return NULL if out of the board node* create_child_in_direction(int dir_index); int create_children(); bool is_on_goal(); void print_sequence(); }; node* node::create_child_in_direction(int dir_index) { node *child = new node(row, col, n, goal_row, goal_col, level+1, this, dir_index); switch(dir_index) { case 0: // UL child->row -= 2; child->col -= 1; break; case 1: // UR child->row -= 2; child->col += 1; break; case 2: // R child->col += 2; break; case 3: // LR child->row += 2; child->col += 1; break; case 4: // LL child->row += 2; child->col -= 1; break; case 5: // L child->col -= 2; break; } if ((child->row < 0) || (child->col < 0) || (child->row >= n) || (child->col >= n)) { delete child; return NULL; } // check if field has already been reached if (chess_field[child->row][child->col] == 1) { delete child; return NULL; } for (int ii=0; iirow << ", " << child->col << ")" << endl; // the chess field is now occupied chess_field[child->row][child->col] = 1; chess_field_occupied++; return child; } int node::create_children() { int children_created = 0; int ret = 0; if (has_already_children) { for (int child=0; child<6; child++) { if (children[child]) { ret = children[child]->create_children(); if (ret < 0) { return -1; } children_created += ret; } } } else { // if this node does not have children yet for (int dir = 0; dir < 6; dir++) { node *child = create_child_in_direction(dir); children[dir] = child; if (children[dir]) { // check if the child is on the goal if (children[dir]->is_on_goal()) { //cout << "This child is on the goal :)" << endl; children[dir]->print_sequence(); return -1; } children_created++; //children[dir]->create_children(); } } has_already_children = true; } return children_created; return 0; } bool node::is_on_goal() { if ((row == goal_row) && (col == goal_col)) { return true; } return false; } void node::print_sequence() { cout << level << endl; int *directions = new int[level]; node *the_node = this; int ii = 0; while(true) { directions[level-ii-1] = the_node->child_index; ii++; the_node = the_node->parent; if (the_node == NULL) { break; } } for (int ii=0; ii