Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement