#include <curses.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 9
#define MAXSECS 1
#define NUMBENDS 8

enum Direction {NONE, UP, LEFT, DOWN, RIGHT, END, CHECK};
enum Direction board[SIZE * SIZE];
int start, end;

enum Direction bends[NUMBENDS][2][2][2] = {      /* [type][before/after][y][x]*/
{{{ NONE, DOWN},{ NONE,  END}},{{ DOWN, LEFT},{RIGHT,  END}}},
{{{ NONE, NONE},{  END, LEFT}},{{ DOWN, LEFT},{  END,   UP}}},
{{{  END, NONE},{   UP, NONE}},{{  END, LEFT},{RIGHT,   UP}}},
{{{RIGHT,  END},{ NONE, NONE}},{{ DOWN,  END},{RIGHT,   UP}}},
{{{ NONE,  END},{ NONE,   UP}},{{RIGHT,  END},{   UP, LEFT}}},
{{{ NONE, NONE},{RIGHT,  END}},{{RIGHT, DOWN},{   UP,  END}}},
{{{ DOWN, NONE},{  END, NONE}},{{RIGHT, DOWN},{  END, LEFT}}},
{{{  END, LEFT},{ NONE, NONE}},{{  END, DOWN},{   UP, LEFT}}}
};
int step[4] = {-SIZE, -1, SIZE, 1};
time_t timer, secs;

int debug=0;
int SIZEindex = 0;
void drawboard (int index) {
    int c;

  if (index > SIZEindex) SIZEindex = index;
  mvprintw(8,20,"Index: %d", index);
  mvprintw(9,20,"Max Index: %d", SIZEindex);
  for (c = 0; c < SIZE*SIZE; c++) {
    move (c/SIZE,(c%SIZE)*2);
    if (c == start) attron (COLOR_PAIR(2));
    else if (c == end) attron (COLOR_PAIR(3));
    else attron (COLOR_PAIR(1));
    switch (board[c]) {
      case NONE : addch('.'); break;;
      case UP   : addch(ACS_UARROW); break;
      case DOWN : addch(ACS_DARROW); break;
      case LEFT : addch(ACS_LARROW); break;
      case RIGHT: addch(ACS_RARROW); break;
      case END  : addch ('E'); break;
      default : printw("%2d",board[c]);
    }
  }
  c = start;
  attrset(COLOR_PAIR(4));
  while(c != end) {
    if (c != start) move (c/SIZE,(c%SIZE)*2);
    switch (board[c]) {
      case UP   : addch(ACS_UARROW); c -= SIZE; break;
      case LEFT : addch(ACS_LARROW); c -= 1; break;
      case DOWN : addch(ACS_DARROW); c += SIZE; break;
      case RIGHT: addch(ACS_RARROW); c += 1; break;
    }
  }
  attrset(COLOR_PAIR(1));
  refresh();
}

void init () {
    initscr ();
    start_color();
    init_pair(1, COLOR_WHITE, COLOR_BLACK);
    init_pair(2, COLOR_WHITE, COLOR_GREEN);
    init_pair(3, COLOR_WHITE, COLOR_RED);
    init_pair(4, COLOR_WHITE, COLOR_YELLOW);
    noecho();
}
        /* The funciton change() is the meat of the space-filling unicursal maze
                             generation that is manditory in Numbrix generation.
       It works by recursively trying different options to build the pattern. */
int change () {
  int xy, c, d, index, mods[50][2]; /* mods[][location/type] */

            /* We perform a checks for completeness and for isolated squares. */
drawboard(0);
  time(&timer);
  if (difftime(timer, secs) > MAXSECS) return 0;
  d = 0;
  for (xy = 0; xy < (SIZE * SIZE); xy++) {
    if (board[xy] == NONE) {
      c = 0; d++;
      for (d = 0; d < 4; d++) {                  /* check for going off edges */
        if (((xy + step[d]) >= 0) && (xy + step[d] < (SIZE * SIZE))/* up & down */
          && ((xy % SIZE) || ((xy + step[d] + 1) % SIZE))           /* left and */
          && (((xy + step[d]) % SIZE) || ((xy + 1) % SIZE)))           /* right */
            if ((board[xy + step[d]] == NONE) /* see if empty sqaure is alone */
              || (xy + step[d] == start) || (xy + step[d] == end))
              c++;
      }
      if (c == 0) return 0;
    }
  }
  if (d == 0) return 1;
       /* Now we make a list of all possible modifications. First the bends...*/
  index = 0;
  for (xy = 0; xy < (SIZE * SIZE) - SIZE; xy++) {
    if ((xy % SIZE) == (SIZE - 1)) continue;
    for (c = 0; c < NUMBENDS; c++) {
      if ((bends[c][0][0][0] != END) && (bends[c][0][0][0] != board[xy])) continue;
      if ((bends[c][0][0][1] != END) && (bends[c][0][0][1] != board[xy + 1])) continue;
      if ((bends[c][0][1][0] != END) && (bends[c][0][1][0] != board[xy + SIZE])) continue;
      if ((bends[c][0][1][1] != END) && (bends[c][0][1][1] != board[xy + SIZE + 1])) continue;
      mods[index][0] = xy; mods[index][1] = c; index++;
    }
  }
  for (d = 0; d < 4; d++) {           /* ...then extending the beginning... */
    if (((start + step[d]) >= 0) && (start + step[d] < (SIZE * SIZE))/* up & down */
      && ((start % SIZE) || ((start + step[d] + 1) % SIZE))           /* left and */
      && (((start + step[d]) % SIZE) || ((start + 1) % SIZE)))           /* right */
      if (board[start + step[d]] == NONE) {
        mods[index][0] = start + step[d];
        mods[index][1] = 100;
        index++;
      }
  }
  for (d = 0; d < 4; d++) {                     /* ...then extending the end. */
    if (((end + step[d]) >= 0) && (end + step[d] < (SIZE * SIZE))  /* up & down */
      && ((end % SIZE) || ((end + step[d] + 1) % SIZE))             /* left and */
      && (((end + step[d]) % SIZE) || ((end + 1) % SIZE)))             /* right */
        if (board[end + step[d]] == NONE) {
          mods[index][0] = end + step[d]; mods[index][1] = 101; index++;
        }
  }
  if (index == 0) return 0; /* no possbile moves */

  for (c = 0; c < index; c++) {                        /* randomize the list. */
    d = rand () % index;
    mods[index][0] = mods[c][0]; mods[index][1] = mods[c][1];
    mods[c][0] = mods[d][0];     mods[c][1] = mods[d][1];
    mods[d][0] = mods[index][0]; mods[d][1] = mods[index][1];
  }
  for (c = 0; c < index; c++) {                  /* iterate through the list. */
mvprintw(debug % 24,40 + 6 * (debug / 24),"%d:%d ",debug++,index-c);
    if(mods[c][1] < 100) {                          /* apply the modification */
      if (bends[mods[c][1]][0][0][0] != END) board[mods[c][0]]           = bends[mods[c][1]][1][0][0];
      if (bends[mods[c][1]][0][0][1] != END) board[mods[c][0] + 1]       = bends[mods[c][1]][1][0][1];
      if (bends[mods[c][1]][0][1][0] != END) board[mods[c][0] + SIZE]     = bends[mods[c][1]][1][1][0];
      if (bends[mods[c][1]][0][1][1] != END) board[mods[c][0] + SIZE + 1] = bends[mods[c][1]][1][1][1];
    } else if (mods[c][1] == 100) {
      if ((mods[c][0] - start) == -1) board[mods[c][0]] = RIGHT;
      if ((mods[c][0] - start) == 1) board[mods[c][0]] = LEFT;
      if ((mods[c][0] - start) == -SIZE) board[mods[c][0]] = DOWN;
      if ((mods[c][0] - start) == SIZE) board[mods[c][0]] = UP;
      d = mods[c][0];
      mods[c][0] = start;
      start = d;
    } else {
      if ((mods[c][0] - end) == -1) board[end] = LEFT;
      if ((mods[c][0] - end) == 1) board[end] = RIGHT;
      if ((mods[c][0] - end) == -SIZE) board[end] = UP;
      if ((mods[c][0] - end) == SIZE) board[end] = DOWN;
      d = mods[c][0];
      mods[c][0] = end;
      end = d; board[end] = END;
    }
drawboard (index); refresh ();/*debug*/
    if (change()) return 1;                         /* recursive call to self */
debug--;
           /* If that didn't work, undo the modification and try the next one */
    if(mods[c][1] < 100) {
      if (bends[mods[c][1]][1][0][0] != END) board[mods[c][0]]           = bends[mods[c][1]][0][0][0];
      if (bends[mods[c][1]][1][0][1] != END) board[mods[c][0] + 1]       = bends[mods[c][1]][0][0][1];
      if (bends[mods[c][1]][1][1][0] != END) board[mods[c][0] + SIZE]     = bends[mods[c][1]][0][1][0];
      if (bends[mods[c][1]][1][1][1] != END) board[mods[c][0] + SIZE + 1] = bends[mods[c][1]][0][1][1];
    } else if (mods[c][1] == 100) {
      board[start] = NONE;
      start = mods[c][0];
    } else {
      board[end] = NONE;
      end = mods[c][0];
      board[end] = END;
    }
refresh ();
  } /* end of loop through list */

  return 0;    /* None of the modifications worked, so back up and try again. */
}

void start_generating () {
  int c;

  do {
    time(&secs);
    for (c = 0; c < SIZE * SIZE; c++) board[c] = NONE;     /* Clear the board */
    start = rand() % (SIZE * SIZE);
    do {
      switch (rand() % 4) {
        case 0 : if (start - SIZE >= 0) {
                   board[start] = UP;
                   end = start - SIZE;
                } break;
        case 1 : if (start % SIZE) {
                   board[start] = LEFT;
                   end = start - 1;
                 } break;
        case 2 : if (start + SIZE < SIZE * SIZE) {
                   board[start] = DOWN;
                   end = start + SIZE;
                 } break;
        case 3 : if ((start + 1) % SIZE) {
                   board[start] = RIGHT;
                   end = start + 1;
                 } break;
      }
    } while (board[start] == NONE);
    board[end] = END;
  } while (change () == 0);
}

int main () {
  init();
  srand (time (NULL));
  start_generating ();
  drawboard (0);
  move (20,0);getch();
  endwin();
  return 0;
}

int*& array()
{
 int test_array = new int[25];
 return test_array;
}

#include <iostream>
#include <cstdlib>
#include <ctime>

class Position {
private:
    int xp, yp;
public:
    Position(int xp, int yp) : xp(xp), yp(yp) {}
    
    void add_xp(int add) { xp += add; }
    void add_yp(int add) { yp += add; }
    
    int add_direction(int add, int dir);
    int get_dirs() { return 4; }
    
    void set_xp(int xp) { this->xp = xp; }
    void set_yp(int yp) { this->yp = yp; }
    
    int get_xp() { return xp; }
    int get_yp() { return yp; }
};

int Position::add_direction(int add, int dir) {
    switch(dir) {
    case 0:
        xp += add;
        break;
    case 1:
        xp -= add;
        break;
    case 2:
        yp += add;
        break;
    case 3:
        yp -= add;
        break;
    }
}

class Map {
private:
    static const int WIDTH = 6, HEIGHT = 6;
    char cell[WIDTH][HEIGHT];
public:
    Map() { clear(); }
    
    void set_cell(int x, int y, char c) { cell[x][y] = c; }
    char get_cell(int x, int y);
    
    bool is_empty(int x, int y) { return get_cell(x, y) == get_empty_char(); }
    
    char get_empty_char() { return '-'; }
    int get_width() { return WIDTH; }
    int get_height() { return HEIGHT; }
    
    void clear();
    void display();
    bool map_is_full();
};

char Map::get_cell(int x, int y) {
    if(x < 0 || y < 0 || x >= get_width() || y >= get_height()) {
        return -1;
    }
    
    return cell[x][y];
}

void Map::clear() {
    for(int x = 0; x < get_width(); x ++) {
        for(int y = 0; y < get_height(); y ++) {
            set_cell(x, y, get_empty_char());
        }
    }
}

void Map::display() {
    for(int x = 0; x < get_width(); x ++) {
        for(int y = 0; y < get_height(); y ++) {
            std::cout << get_cell(x, y);
        }
        
        std::cout << '\n';
    }
}

bool Map::map_is_full() {
    for(int x = 0; x < get_width(); x ++) {
        for(int y = 0; y < get_height(); y ++) {
            if(get_cell(x, y) == get_empty_char()) return false;
        }
    }
    
    return true;
}

void trace_labyrinth(Map &map, Position &pos);

int main() {
    std::srand((unsigned)std::time(0));
    
    Map map;
    Position start(
        std::rand() % map.get_width(),
        std::rand() % map.get_height());
    
    map.set_cell(start.get_xp(), start.get_yp(), '@');
    
    trace_labyrinth(map, start);
    
    return 0;
}

void trace_labyrinth(Map &map, Position &pos) {
    Position next = pos;
    
    int startdir = rand() % next.get_dirs();
    int dir = startdir;
    bool found_move = false;
    do {
        next = pos;
        next.add_direction(1, dir);
        
        if(map.is_empty(next.get_xp(), next.get_yp())) {
            map.set_cell(next.get_xp(), next.get_yp(), "v^><"[dir]);
            
            trace_labyrinth(map, next);
            found_move = true;
        }
        
        dir ++;
        dir %= next.get_dirs();
    } while(dir != startdir);
    
    if(!found_move) {
        map.set_cell(pos.get_xp(), pos.get_yp(), '$');
        
        if(map.map_is_full()) {
            map.display();
            std::cout << std::endl;
        }
    }
    
    map.set_cell(pos.get_xp(), pos.get_yp(), map.get_empty_char());
}