#include <stdio.h>#include <time.h> /* Methods */ void initFieldCounter(); int solve(); int isUnsolvable(); void rJump(int position, int jumpCounter); void calcValidJumps(int position); void updateFieldCounter(int positions[], int skipPosition, int value); int inBounds(int x, int y); int toInteger(int x, int y); void toPosition(int * array, int val); /* Transformations for valid Knight Jumps */ int fgValidKnightJumpX[] = { +1, +2, +2, +1, -1, -2, -2, -1 }; int fgValidKnightJumpY[] = { -2, -1, +1, +2, +2, +1, -1, -2 }; int BTRUE = 1; int BFALSE = 0; /* Flag indicating that a field is occupied */ int OCCUPIED = -1; /* Number of total Solutions for given Problem */ int fSolutionsCount; /* Tour Setup */ int fDimension = 5; int fSize = 25; int fStartX = 0; int fStartY = 0; /* Fields used by Algorithm */ int fFieldCounter[25]; int fValidJumps[8]; int fValidJumpIndex = 0; 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("Solutions: %i", fSolutionsCount); printf("\nExecution took: %fs", 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() { int startField = toInteger(fStartX, fStartY); 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 */ calcValidJumps(position); /* Copy them into local array since the result is shared */ int validJumps[fValidJumpIndex]; int i; for (i = 0; i < fValidJumpIndex; i++) validJumps[i] = fValidJumps[i]; /* For each valid Jump, recursively proceed the Tour */ for (i = 0; i < (sizeof(validJumps) / sizeof(int)); i++) { int currentValidJump = validJumps[i]; int oldFieldCounterValue = fFieldCounter[currentValidJump]; /* Decrement Field Counter for other Valid Jumps */ updateFieldCounter(validJumps, 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, 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++) { calcValidJumps(i); fFieldCounter[i] = fValidJumpIndex; } } /* Add the given Value to the Array, ignoring the skipPosition entry */ void updateFieldCounter(int positions[], int skipPosition, int value) { int j; for (j = 0; j < (sizeof(positions) / sizeof(int)); 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; } /* Adds the valid Jumps from the given Position to the shared Array */ void calcValidJumps(int position) { int xy[2]; toPosition(xy, position); fValidJumpIndex = 0; /* Foreach possible Jump */ int i; for (i = 0; i < (sizeof(fgValidKnightJumpX) / sizeof(int)); i++) { int jumpX = xy[0] + fgValidKnightJumpX[i]; int jumpY = xy[1] + fgValidKnightJumpY[i]; int jumpXY = toInteger(jumpX, jumpY); if (inBounds(jumpX, jumpY) && fFieldCounter[jumpXY] != OCCUPIED) { fValidJumps[fValidJumpIndex] = jumpXY; fValidJumpIndex++; } } } /* Tests if the X/Y values are in bounds for the given Dimension */ int inBounds(int x, int y) { if (x >= 0 && x < fDimension && y >= 0 && y < fDimension) return BTRUE; return BFALSE; } /* Converts an X/Y Position to an Integer */ int toInteger(int x, int y) { return y * fDimension + x; } /* Converts an Integer to a X/Y Position */ void toPosition(int * array, int val) { array[0] = val % fDimension; array[1] = val / fDimension; }