#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;
}
}
Comments