#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;
  }