#include <stdlib.h>

unsigned short * tour(unsigned short);

unsigned move(unsigned, unsigned, unsigned char);
unsigned short * findTour(unsigned short, unsigned, unsigned (*) (unsigned, unsigned, unsigned short));
unsigned char degree(unsigned, unsigned char *, unsigned short);
unsigned changeOrdering(unsigned, unsigned, unsigned short);

// just a way to convert the coordinates into one single value, and back
#define row(A) ((A) & 65535)
#define column(A) (((A) >> 16) & 65535)
#define cellNumber(ROW, COL) (((ROW) & 65535) | (((COL) & 65535) << 16))

#define offset(CELL, SIZE) ((row(CELL) - 1) + ((column(CELL) - 1) * (SIZE)))

unsigned orderings[20] = {
    076543210,
    076543201,
    076543102,
    076543120,
    076543021,
    076543012,
    076542013,
    076542031,
    076542130,
    076542103,
    076542301,
    076542310,
    076541320,
    076541302,
    076541203,
    076541230,
    076541032,
    076541023,
    076540123,
    0 // just to indicate the list ends
};

unsigned short * tour (unsigned short boardSize) {
  // returns an array with the cells, first row then column. Returns NULL if no tour is found
  if (boardSize < 5) return NULL; // no tours on smaller boards
  if (boardSize < 112) {
    unsigned * nextOrdering;
    unsigned short * result;
    for (nextOrdering = orderings; *nextOrdering; nextOrdering ++) {
      result = findTour(boardSize, *nextOrdering, NULL);
      if (result) return result;
    }
    return NULL;
  }
  return findTour(boardSize, changeOrdering(0, 0, boardSize), &changeOrdering);
}


unsigned move (unsigned initialCell, unsigned boardSize, unsigned char moveType) {
  if (!initialCell) return 0;
  switch (moveType) {
    case 0:
      if (row(initialCell) < 3) return 0;
      if (column(initialCell) >= boardSize) return 0;
      return initialCell + 65534; // 2 up, 1 right
    case 1:
      if (row(initialCell) < 2) return 0;
      if (column(initialCell) >= (boardSize - 1)) return 0;
      return initialCell + 131071; // 1 up, 2 right
    case 2:
      if (row(initialCell) >= boardSize) return 0;
      if (column(initialCell) >= (boardSize - 1)) return 0;
      return initialCell + 131073; // 1 down, 2 right
    case 3:
      if (row(initialCell) >= (boardSize - 1)) return 0;
      if (column(initialCell) >= boardSize) return 0;
      return initialCell + 65538; // 2 down, 1 right
    case 4:
      if (row(initialCell) >= (boardSize - 1)) return 0;
      if (column(initialCell) < 2) return 0;
      return initialCell - 65534; // 2 down, 1 left
    case 5:
      if (row(initialCell) >= boardSize) return 0;
      if (column(initialCell) < 3) return 0;
      return initialCell - 131071; // 1 down, 2 left
    case 6:
      if (row(initialCell) < 2) return 0;
      if (column(initialCell) < 3) return 0;
      return initialCell - 131073; // 1 up, 2 left
    case 7:
      if (row(initialCell) < 3) return 0;
      if (column(initialCell) < 2) return 0;
      return initialCell - 65538; // 2 up, 1 left
    default:
      return 0;
  }
}

unsigned short * findTour (unsigned short boardSize, unsigned ordering, unsigned (* orderingChangingCallback) (unsigned, unsigned, unsigned short)) {
  unsigned char * cells = calloc(boardSize * boardSize, 1);
  if (!cells) return NULL; // if there's no memory...
  unsigned * moves = calloc(boardSize * boardSize * sizeof(unsigned), 1);
  unsigned char neighbours[9];
  unsigned char scores[8];
  unsigned char a, b, min;
  unsigned cell;
  if (!moves) {
    free(cells);
    return NULL;
  }
  unsigned * finish = moves + boardSize * boardSize;
  unsigned * nextMove = moves;
  *(nextMove ++) = cellNumber(1, 1); // we always start here
  *cells = 1; // so we take the cell away
  for (; nextMove < finish; nextMove ++) {
    for (a = b = 0; a < 8; a ++) {
      cell = move(nextMove[-1], boardSize, a);
      if (cell && !cells[offset(cell, boardSize)])
        neighbours[b ++] = a;
      else
        scores[a] = 255;
    }
    if (!b) { // no moves
      free(moves);
      free(cells);
      return NULL;
    }
    neighbours[b] = 255;
    for (a = 0; neighbours[a] != 255; a ++)
      scores[neighbours[a]] = degree(move(nextMove[-1], boardSize, neighbours[a]), cells, boardSize);
    min = 255;
    for (a = 0; a < 8; a ++)
      if (scores[a] < min)
        min = scores[a];
    for (a = 0, b = 0; a < 8; a ++)
      if (scores[a] == min)
        neighbours[b ++] = a;
    if (!b) { // shouldn't happen
      free(moves);
      free(cells);
      return NULL;
    }
    if (b == 1)
      cell = move(nextMove[-1], boardSize, *neighbours);
    else {
      neighbours[b] = 255;
      unsigned current;
      unsigned char search;
      for (a = 0, current = ordering; a < 8; a ++, current >>= 3) {
        search = current & 7;
        for (b = 0; neighbours[b] != 255; b ++)
          if (neighbours[b] == search)
            break;
        if (neighbours[b] != 255) break;
      }
      if (neighbours[b] == 255) { // shouldn't happen
        free(moves);
        free(cells);
        return NULL;
      }
      cell = move(nextMove[-1], boardSize, neighbours[b]);
    }
    *nextMove = cell;
    cells[offset(cell, boardSize)] = 1;
    if (orderingChangingCallback)
      ordering = (*orderingChangingCallback)(ordering, cell, boardSize);
  }
  free(cells);
  unsigned short * result = malloc(2 * boardSize * boardSize * sizeof(unsigned short));
  if (!result) { // no memory!
    free(moves);
    return NULL;
  }
  unsigned short * nextResult = result;
  for (nextMove = moves; nextMove < finish; nextMove ++) {
    *(nextResult ++) = row(*nextMove);
    *(nextResult ++) = column(*nextMove);
  }
  free(moves);
  return result;
}

unsigned char degree (unsigned cell, unsigned char * cells, unsigned short boardSize) {
  if (!cell) return 9;
  unsigned char moveNumber, total;
  unsigned neighbour;
  for (moveNumber = total = 0; moveNumber < 8; moveNumber ++) {
    neighbour = move(cell, boardSize, moveNumber);
    if (neighbour) total += !cells[offset(neighbour, boardSize)];
  }
  return total;
}

unsigned changeOrdering (unsigned ordering, unsigned cell, unsigned short boardSize) {
  unsigned char type = boardSize & 7;
  switch (type) {
    case 0:
      if (!cell) return 076405132;
      if (cell == cellNumber(boardSize - 1, boardSize - 2)) return 042013567;
      if (cell == cellNumber(2, 2)) return 013265704;
      if (cell == cellNumber(boardSize - 8, 1)) return 076513204;
      if (cell == cellNumber(7, boardSize - 3)) return 076542301;
      return ordering;
    case 1:
      if (!cell) return 076405132;
      if (cell == cellNumber(boardSize - 1, boardSize - 2)) return 042013567;
      if (cell == cellNumber(2, 2)) return 076531204;
      if (cell == cellNumber(boardSize - 6, (boardSize + 9) / 2)) return 045607312;
      return ordering;
    case 2:
      if (!cell) return 076405132;
      if (cell == cellNumber(6, 1)) return 042013567;
      if (cell == cellNumber(3, 1)) return 076512034;
      if (cell == cellNumber(boardSize - 15, 4)) return 076502314;
      if (cell == cellNumber(10, boardSize - 2)) return 021063547;
      if (cell == cellNumber(5, (boardSize - 6) / 2)) return 021753640;
      return ordering;
    case 3:
      if (!cell) return 070641532;
      if (cell == cellNumber(boardSize - 1, boardSize - 2)) return 064207513;
      if (cell == cellNumber(boardSize - 6, boardSize)) return 063210457;
      if (cell == cellNumber(2, 5)) return 013265704;
      if (cell == cellNumber(boardSize - 10, 3)) return 062341705;
      if (cell == cellNumber((boardSize + 1) / 2, boardSize - 2)) return 072413506;
      return ordering;
    case 4:
      if (!cell) return 076405132;
      if (cell == cellNumber(boardSize - 1, boardSize - 2)) return 042013567;
      if (cell == cellNumber(2, 2)) return 013265704;
      if (cell == cellNumber(boardSize - 8, 1)) return 076513204;
      if (cell == cellNumber(10, boardSize - 5)) return 01324657;
      if (cell == cellNumber(13, (boardSize + 2) / 2)) return 01325476;
      return ordering;
    case 5:
      if (!cell) return 076405132;
      if (cell == cellNumber(boardSize - 1, boardSize - 2)) return 042013567;
      if (cell == cellNumber(2, 2)) return 076531204;
      if (cell == cellNumber(boardSize - 2, (boardSize & ~15) / 2)) return 076532140;
      return ordering;
    case 6:
      if (!cell) return 076405132;
      if (cell == cellNumber(6, 1)) return 042013567;
      if (cell == cellNumber(3, 1)) return 076512034;
      if (cell == cellNumber(boardSize - 10, 1)) return 076502314;
      if (cell == cellNumber(10, boardSize - 2)) return 021063547;
      if (cell == cellNumber(3, (boardSize + 8) / 2)) return 076524310;
      return ordering;
    case 7:
      if (!cell) return 070641532;
      if (cell == cellNumber(boardSize - 1, boardSize - 2)) return 064207513;
      if (cell == cellNumber(boardSize - 6, boardSize)) return 063210457;
      if (cell == cellNumber(2, 5)) return 013265704;
      if (cell == cellNumber(boardSize - 6, 3)) return 062341705;
      if (cell == cellNumber((boardSize + 1) / 2, boardSize - 2)) return 037164205;
      return ordering;
  }
}