#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 }; /* Tour Setup (TODO Make dynamic via Commandline) */ 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]; /* Main Entry Point */ 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; } /* Initially calculate valid Jumps for any Field of the Tour */ void initFieldCounter() { int field; int tmp[MAX_VALID_JUMPS]; for (field = 0; field < (sizeof(fFieldCounter) / sizeof(int)); field++) { fFieldCounter[field] = calcValidJumps(field, tmp, MAX_VALID_JUMPS); } } /** * 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() { /* Start Position */ position_t start; start.x = fStartX; start.y = fStartY; /* Occupy this Field */ int startField = toField(&start); fFieldCounter[startField] = OCCUPIED; /* The first Move */ rJump(startField, 0); return fSolutionsCount; } /* Recursively performs the Knight's Tour */ void rJump(int field, 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 validJumps[MAX_VALID_JUMPS]; int validJumpsCount = calcValidJumps(field, validJumps, MAX_VALID_JUMPS); /* For each valid Jump, recursively proceed the Tour */ int i; 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); } } /* Add the given Value to the Array, ignoring the skipField entry */ void updateFieldCounter(int * fields, int fieldsLength, int skipField, int value) { int i; for (i = 0; i < fieldsLength; i++) { if (fields[i] != skipField) { int otherValidJump = fields[i]; 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 field, int * validJumps, int length) { int index = 0; /* Convert Field to Position */ position_t position; position.x = 0; position.y = 0; toPosition(field, &position); /* Foreach possible Jump */ int i; for (i = 0; i < (sizeof(fgValidKnightJumpX) / sizeof(int)); i++) { position_t validJump; validJump.x = position.x + fgValidKnightJumpX[i]; validJump.y = position.y + fgValidKnightJumpY[i]; int validField = toField(&validJump); /* Check if this Field is actually valid */ if (inBounds(&validJump) && fFieldCounter[validField] != OCCUPIED && index < length) { validJumps[index] = validField; index++; } } return index; } /* Tests if the X/Y values are in bounds for the given Dimension */ int inBounds(position_t *position) { if (position->x >= 0 && position->x < fDimension && position->y >= 0 && position->y < fDimension) return BTRUE; return BFALSE; } /* Converts an X/Y Position to an Integer */ int toField(position_t *position) { return position->y * fDimension + position->x; } /* Converts an Integer to a X/Y Position */ void toPosition(int index, position_t *position) { position->x = index % fDimension; position->y = index / fDimension; }