Stuff

#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() {
    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 */
    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;
  	int x = 0;
    int y = 0;
    toPosition(position, &x, &y);

    /* Foreach possible Jump */
    int i;
    for (i = 0; i < (sizeof(fgValidKnightJumpX) / sizeof(int)); i++) {
      int jumpX = x + fgValidKnightJumpX[i];
      int jumpY = y + fgValidKnightJumpY[i];

      int jumpXY = toInteger(jumpX, jumpY);

      if (inBounds(jumpX, jumpY) && fFieldCounter[jumpXY] != OCCUPIED && index < length) {
        array[index] = jumpXY;
        index++;
      }
    }
    
    return index;
  }
  
  int getValidJumpsCount(int position) {
  	int index = 0;
    int x = 0;
    int y = 0;
    toPosition(position, &x, &y);

    /* Foreach possible Jump */
    int i;
    for (i = 0; i < (sizeof(fgValidKnightJumpX) / sizeof(int)); i++) {
      int jumpX = x + fgValidKnightJumpX[i];
      int jumpY = y + fgValidKnightJumpY[i];

      int jumpXY = toInteger(jumpX, jumpY);

      if (inBounds(jumpX, jumpY) && fFieldCounter[jumpXY] != OCCUPIED)
        index++;
    }
    
    return index;
  }

  /* 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 val, int * x, int * y) {
  	*x = val % fDimension;
  	*y = val / fDimension;
  }