#include <stdio.h>#include <time.h>#include "KnightsTour.h" /* Transformations for valid Knight Jumps */ const int fgValidKnightJumpX[] = { +1, +2, +2, +1, -1, -2, -2, -1 }; const int fgValidKnightJumpY[] = { -2, -1, +1, +2, +2, +1, -1, -2 }; /* Flag indicating that a field is occupied */ const int OCCUPIED = -1; /* Tour Setup */ const int fDimension = 5; const int fSize = 25; const int fStartX = 0; const int fStartY = 0; /* Number of total Solutions for given Problem */ int fSolutionsCount; /* Fields used by Algorithm */ int fFieldCounter[25]; int main(int argc, char **argv) { double time=0.0, tstart= 0.0; tstart = clock(); initFieldCounter(); solve(); time += clock() - tstart; time = time / CLOCKS_PER_SEC; printf("\nSolutions: %i", fSolutionsCount); printf("\nExecution took: %fsec\n\n", time); return 0; } /** * Solves the given Knight-Tour-Problem and returns the number of solutions * found. * * @return The number of solutions found for the given Problem. */ int solve() { position_t start; start.x = fStartX; start.y = fStartY; int startField = toInteger(&start); fFieldCounter[startField] = OCCUPIED; /* The first Move */ rJump(startField, 0); return fSolutionsCount; } /* Recursively performs the Knight's Tour */ void rJump(int position, int jumpCounter) { /* Increment jumpCounter */ jumpCounter++; /* Solution Found, return in this case */ if (jumpCounter == fSize) { fSolutionsCount++; if (fSolutionsCount%1000 == 0) printf("%i\n", fSolutionsCount); return; } /* Test wether its worth proceeding (Bound Part) */ if (isUnsolvable()) return; /* Calculate valid Jumps */ int i; int validJumps[MAX_VALID_JUMPS]; int validJumpsCount = calcValidJumps(position, validJumps, MAX_VALID_JUMPS); /* For each valid Jump, recursively proceed the Tour */ for (i = 0; i < validJumpsCount; i++) { int currentValidJump = validJumps[i]; int oldFieldCounterValue = fFieldCounter[currentValidJump]; /* Decrement Field Counter for other Valid Jumps */ updateFieldCounter(validJumps, validJumpsCount, currentValidJump, -1); /* Occupy the current Jump */ fFieldCounter[currentValidJump] = OCCUPIED; /* Perform recursive Jump */ rJump(currentValidJump, jumpCounter); /* Free the current Jump */ fFieldCounter[currentValidJump] = oldFieldCounterValue; /* Re-Increment Field Counter for other Valid Jumps */ updateFieldCounter(validJumps, validJumpsCount, currentValidJump, +1); } } /* Initially calculate valid Jumps for any Field of the Tour */ void initFieldCounter() { int i; for (i = 0; i < (sizeof(fFieldCounter) / sizeof(int)); i++) { fFieldCounter[i] = getValidJumpsCount(i); } } /* Add the given Value to the Array, ignoring the skipPosition entry */ void updateFieldCounter(int * positions, int positionsLength, int skipPosition, int value) { int j; for (j = 0; j < positionsLength; j++) { if (positions[j] != skipPosition) { int otherValidJump = positions[j]; fFieldCounter[otherValidJump] += value; } } } /* Checks if any Field counter has reached Zero */ int isUnsolvable() { int i; for (i = 0; i < (sizeof(fFieldCounter) / sizeof(int)); i++) if (fFieldCounter[i] == 0) return BTRUE; return BFALSE; } int calcValidJumps(int position, int * array, int length) { int index = 0; position_t pos; pos.x = 0; pos.y = 0; toPosition(position, &pos); /* Foreach possible Jump */ int i; for (i = 0; i < (sizeof(fgValidKnightJumpX) / sizeof(int)); i++) { position_t jump; jump.x = pos.x + fgValidKnightJumpX[i]; jump.y = pos.y + fgValidKnightJumpY[i]; int jumpXY = toInteger(&jump); if (inBounds(&jump) && fFieldCounter[jumpXY] != OCCUPIED && index < length) { array[index] = jumpXY; index++; } } return index; } int getValidJumpsCount(int position) { int index = 0; position_t pos; pos.x = 0; pos.y = 0; toPosition(position, &pos); /* Foreach possible Jump */ int i; for (i = 0; i < (sizeof(fgValidKnightJumpX) / sizeof(int)); i++) { position_t jump; jump.x = pos.x + fgValidKnightJumpX[i]; jump.y = pos.y + fgValidKnightJumpY[i]; int jumpXY = toInteger(&jump); if (inBounds(&jump) && fFieldCounter[jumpXY] != OCCUPIED) index++; } return index; } /* Tests if the X/Y values are in bounds for the given Dimension */ int inBounds(position_t *pos) { if (pos->x >= 0 && pos->x < fDimension && pos->y >= 0 && pos->y < fDimension) return BTRUE; return BFALSE; } /* Converts an X/Y Position to an Integer */ int toInteger(position_t *pos) { return pos->y * fDimension + pos->x; } /* Converts an Integer to a X/Y Position */ void toPosition(int val, position_t *pos) { pos->x = val % fDimension; pos->y = val / fDimension; }