Problema de los tableros.

boards.cpp

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

struct Node {
  int tablero;
  int origin;
  int pz;
  Node *left, *rigth, *parent;
  bool color;
} mark[1000000];

stack<int> path;

// Definición RedBlackTree
Node *nill = &mark[0];
Node *root = &mark[0];
int lrbt;

void left_rotate(Node *x) {
  Node *y = x->rigth;
  x->rigth = y->left;
  
  if(y->left) y->left->parent = x;
  y->parent = x->parent;
  
  if(x->parent == nill) {
    root = y;
  } else if(x == x->parent->left) {
    x->parent->left = y;
  } else {
    x->parent->rigth = y;
  }
  
  y->left = x;
  x->parent = y;
}

void rigth_rotate(Node *x) {
  Node *y = x->left;
  x->left = y->rigth;
  
  if(y->rigth) y->rigth->parent = x;
  y->parent = x->parent;
  
  if(x->parent == nill) {
    root = y;
  } else if(x == x->parent->rigth) {
    x->parent->rigth = y;
  } else {
    x->parent->left = y;
  }
  
  y->rigth = x;
  x->parent = y;
}

void insertFixup(Node* z) {
  Node *y;
  
  while(z->parent->color) {
    if(z->parent == z->parent->parent->left) {
      y = z->parent->parent->rigth;
      if(y->color) {
        z->parent->color = BLACK;
        y->color = BLACK;
        z->parent->parent->color = RED;
        z = z->parent->parent;
      } else if(z == z->parent->rigth) {
        z = z->parent;
        left_rotate(z);
      } else {
        z->parent->color = BLACK;
        z->parent->parent->color = RED;
        rigth_rotate(z->parent->parent);
      }
    } else {
      y = z->parent->parent->left;
      if(y->color) {
        z->parent->color = BLACK;
        y->color = BLACK;
        z->parent->parent->color = RED;
        z = z->parent->parent;
      } else if(z == z->parent->left) {
        z = z->parent;
        rigth_rotate(z);
      } else {
        z->parent->color = BLACK;
        z->parent->parent->color = RED;
        left_rotate(z->parent->parent);
      }
    }
  }
  
  root->color = BLACK;
}

void insert(int& tbl, int& org, int& pz) {
  Node *z = &mark[++lrbt];
  z->tablero = tbl;
  z->origin = org;
  z->pz = pz;
  z->color = RED;
  z->parent = z->left = z->rigth = nill;
  
  Node *y = nill;
  Node *x = root;
  
  while(x != nill) {
    y = x;
    if(z->tablero < x->tablero) {
      x = x->left;
    } else {
      x = x->rigth;
    }
  }
  
  z->parent = y;
  if(y == nill) {
    root = z;
  } else if(z->tablero < y->tablero) {
    y->left = z;
  } else {
    y->rigth = z;
  }
  
  insertFixup(z);
}

Node* search(int& tbl) {
  Node *x = root;
  
  while(x->tablero != tbl && x != nill) {
    if(x->tablero < tbl) {
      x = x->rigth;
    } else {
      x = x->left;
    }
  }
  return x;
}

int searchParent(int& tbl) {
  Node *x = root;
  
  while(x->tablero != tbl && x != nill) {
    if(x->tablero < tbl) {
      x = x->rigth;
    } else {
      x = x->left;
    }
  }
  return x->origin;
}

// Algoritmo bfs
void bfs(int tbl, int pz) {
  int dig = 0, auxtbl;
  
  lrbt = 0;
  root = nill;
  nill->tablero = 0;
  nill->color = BLACK;
  nill->left = nill->rigth = nill->parent = 0;
  
  insert(tbl, dig, pz);
  
  Node *nd = root;
  queue<Node*> Q;
  Q.push(nd);
  
  int *mv;
  
  while(!Q.empty()) {
    nd = Q.front();
    Q.pop();
    
    tbl = nd->tablero;
    pz = nd->pz;
    
    for(mv = &moves[pz][0]; *mv; ++mv) {
      dig = (tbl / hex[*mv]);
      dig %= 16;
      
      auxtbl = tbl + calculation[dig][pz][*mv];
      nd = search(auxtbl);
      
      if(nd == nill && ) {
        insert(auxtbl, tbl, *mv);
        Q.push(&mark[lrbt]);
      }
    }
  }
  
  while(!Q.empty()) Q.pop();
  
  do {
    int s = tbl;
    path.push(s);
    tbl = searchParent(tbl);
  } while (tbl);
}

/* retorna "a - b" en segundos */
double timeval_diff(struct timeval *a, struct timeval *b)
{
  return
    (double)(a->tv_sec + (double)a->tv_usec/1000000) -
    (double)(b->tv_sec + (double)b->tv_usec/1000000);
}

int main(int argc, char** argv) {
  for(int i = 1;i < 16; ++i) {
    for(int j = 1;j < 16; ++j) {
      for(int k = 1;k < 16; ++k) {
        calculation[i][j][k] = i * (hex[j] - hex[k]);
      }
    }
  }
  
  if(argc == 3) {
    int tbl=goal, pz=9;
    
    //sscanf(argv[1], "%d", &tbl);
    //sscanf(argv[2], "%d", &pz);
    
    bfs(tbl, pz);
    
    printf("profundidad: %d\n", (int)path.size());
    // vaciar la pila que contiene el camino
    while(!path.empty()) {
      printf("   -> %d\n", path.top());
      path.pop();
    }
  } else {
    printf("No tiene argumentos suficientes para correr el algoritmo.\n");
  }
  
  //Generar archivo tableros.out
  FILE * pFile;
  pFile = fopen ("tableros.out","w");
  if(pFile!=NULL) {
    for(int i = 0; ;++i)sprintf(line, "%s;%x", line, /*fila de tablero*/);
    fputs(line, pFile);    
    fclose (pFile);
  }
  
  return 0;
}

boards.py

__author__ = 'tulipan'

from .resources import moves, hexa, mlen, lrbt


class Node(object):
    def __init__(self, parent, board, pz, origin, depth, dig):
        self._left = None
        self._right = None
        self._parent = parent
        self._red = False
        self._board = board
        self._pz = pz
        self._origin = origin
        self._depth = depth
        self._dig = dig

    left = property(fget=lambda self: self._left, doc="Node's left child")
    right = property(fget=lambda self: self._right, doc="Node's right child")
    parent = property(fget=lambda self: self._parent, doc="Node's parent")
    red = property(fget=lambda self: self._red, doc="Node's color is red(T) or black(F)")
    board = property(fget=lambda self: self._board, doc="Node's board screen")
    pz = property(fget=lambda self: self._pz, doc="Node's blank(0) position")
    origin = property(fget=lambda self: self._origin, doc="Node's origin")
    depth = property(fget=lambda self: self._depth, doc="Node's depth")
    dig = property(fget=lambda self: self._dig, doc="Node's digit")

    def __str__(self):
        return str(self._board)


mark = []
for i in range(1, mlen):
    mark.append(Node(parent=None, board=None, pz=None, origin=None, depth=None, dig=None))

nill = mark[0]
root = mark[0]

lrbt = 0


def left_rotate(x):
    y = x.right
    x._right = y.left

    if y.left != nill:
        y.left._parent = x
    y._parent = x.parent

    if x.parent == nill:
        root = y
    elif x == x.parent.left:
        x.parent._left = y
    else:
        x.parent._right = y

    y._left = x
    x._parent = y


def right_rotate(x):
    y = x.left
    x._left = y.right

    if y.right != nill:
        y.right._parent = x
    y._parent = x.parent

    if x.parent == nill:
        root = y
    elif x == x.parent.right:
        x.parent._right = y
    else:
        x.parent._left = y

    y._right = x
    x._parent = y


def insert_fix_up(z):
    while z.parent.red:
        if z.parent == z.parent.parent.left:
            y = z.parent.parent.right
            if y.red:
                z.parent._red = False
                y._red = False
                z.parent.parent._red = True
                z = z.parent.parent
            elif z == z.parent.right:
                z = z.parent
                left_rotate(z)
            else:
                z.parent._red = False
                z.parent.parent._red = True
                right_rotate(z.parent.parent)
        else:
            y = z.parent.parent.left
            if y.red:
                z.parent._red = False
                y._red = False
                z.parent.parent._red = True
                z = z.parent.parent
            elif z == z.parent.left:
                z = z.parent
                right_rotate(z)
            else:
                z.parent._red = False
                z.parent.parent._red = True
                left_rotate(z.parent.parent)
    root._red = False


def insert_node(z):
    y = nill
    x = root

    # for i in range(1, moves[z.pz][i]):
    i = 0
    while moves[z.pz][i] > 0:
        dig = (z.board / hexa[moves[z.pz][i]])
        z.dig[i] = dig % 16
        i += 1

    while x != nill:
        y = x
        if z.board < x.board:
            x = x.left
        else:
            x = x.right

    z.parent = y

    if y == nill:
        root = z
    elif z.board < y.board:
        y._left = z
    else:
        y._right = z

    z._left = nill
    z._right = nill
    z._red = True
    insert_fix_up(z)


def insert_values(board, pz, origin, depth, dig):
    lrbt += 1
    z = mark[lrbt]
    z._board = board
    z._pz = pz
    z._origin = origin
    z._depth = depth
    z._dig = dig
    insert_node(z)


def search(board, x=None):
    if None == x:
        x = root
    while x.board != board and x != nill:
        if x.board < board:
            x = x.right
        else:
            x = x.left

    return x


def search_parent(board, x=None):
    if None == x:
        x = root
    while x.board != board and x != nill:
        if x.board < board:
            x = x.right
        else:
            x = x.left

    return x.parent