/* Lösung des Springerproblems */
#include <stdlib.h>
#include <stdio.h>


#define GROESSE 6

int schachbrett[GROESSE][GROESSE];
long int zurueck;

void zeigebrett() {
	int y,x;
	for (y=0;y<GROESSE;y++) {
		for (x=0;x<GROESSE;x++) {
			printf("%2d ",schachbrett[x][y]);
		}
		printf("\n");
	}
}

int gueltig(int x, int y) {
	if ((x>=0) && (x<GROESSE) && (y>=0) && (y<GROESSE))
		return (schachbrett[x][y]==0);
	else
		return 0;
}

void springe(int x, int y, int s) {
	schachbrett[x][y] = s;

	/* printf ("Zug %2d: %d %d\n",s,x,y); */

	if (s==GROESSE*GROESSE) {
		printf("yeah! %ld Züge zurückgenommen!\n", zurueck);
		zeigebrett();
		exit(0);
	}

	if (gueltig(x-1,y+2)) springe(x-1,y+2,s+1);
	if (gueltig(x+1,y+2)) springe(x+1,y+2,s+1);
	if (gueltig(x+2,y+1)) springe(x+2,y+1,s+1);
	if (gueltig(x+2,y-1)) springe(x+2,y-1,s+1);
	if (gueltig(x+1,y-2)) springe(x+1,y-2,s+1);
	if (gueltig(x-1,y-2)) springe(x-1,y-2,s+1);
	if (gueltig(x-2,y-1)) springe(x-2,y-1,s+1);
	if (gueltig(x-2,y+1)) springe(x-2,y+1,s+1);

/* 	printf("oje: Nehme Zug zurück!\n");
	zeigebrett();
*/
	zurueck++;
	schachbrett[x][y] = 0;
}

int main () {
	springe(0,0,1);
}