// Kompillieren am besten mit `gcc -o perfect_snake -O3 perfect_snake.` und dann `perfect_snake <n>` mit n = 2,3,4,...
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

	// KONFIGURATION

#define CHECK_SEPARATION // Überprüft, ob durch das Hinzufügen zwei separierte Teile entstehen und verwirft dann den Pfad (danke Tobchen)
#define CHECK_ENDS       // Überprüft, ob "Enden" entstehen (das sind leere Felder, die zu drei Seiten hin begrenzt sind). Wenn drei Enden existieren bzw.
			// irgendwann zwangsläufig enstehen müssen, wird abgebrochen
//#define DEBUG		   // Schaltet Debug-Ausgaben ein und führt Überprüfungen durch, wenn CHECK_ENDS auch an ist.

#ifdef DEBUG
	#define dlog(format, ...) printf("LOG (%u): " format "\n", __LINE__,##__VA_ARGS__) // Debug-Ausgabe, wie printf
	#define DEBUG_FIELD { \
		int x,y;      \
		for (y = 0; y < fieldSize; y++) { \
			for (x = 0; x < fieldSize; x++) { \
				if (FIELD(x,y)) { printf("x"); } else { printf(" "); } \
			} \
			printf("\n"); \
		}}     // Gibt das Feld aus
#else
	#define dlog(...)   
	#define DEBUG_FIELD   
#endif

int fieldSize = 2; // Seitenlänge des quadratischen Feldes
int fieldCapacity; // = fieldSize^2
char* field;  // Pointer auf den Speicherbereich, in dem das Feld gespeichert wird. Zugriff am besten über FIELD(x,y)
int filled;  // Zahl der gefüllten Felder
#define FIELD(x,y) field[(x)+fieldSize*(y)]
#define FN(x,y) filledNeighbors[(x)+fieldSize*(y)]
#define N 0
#define E 1
#define S 2
#define W 3
int vx[] = {0, 1, 0, -1};
int vy[] = {-1, 0, 1, 0};

typedef struct {
	int x;
	int y;
	int lastDir;
	int dir;
#ifdef CHECK_ENDS
	int endX, endY; // notwendige Fortführung
#endif

} step, *pstep;

pstep path;

int endX = -1;
int endY = -1;

pstep root;


int main (int argc, char* argv[]) {
	
	dlog("argc: %u", argc);
	if (argc == 2) {
		sscanf(argv[1], "%u", &fieldSize);
		if (fieldSize < 1) {
			fprintf(stderr, "Field size must be integer and greater than zero\n");
			return 1;
		}
	}
	fieldCapacity = fieldSize*fieldSize;
	field = malloc(fieldCapacity);
	memset(field, 0, fieldCapacity);

	int x = 2;
	int y = 0;

	root = malloc(sizeof(step)*fieldCapacity);
	root->x = 1;
	root->y = 0;
	root->lastDir = E;
	root->dir = E;
#ifdef CHECK_ENDS
	root->endX = -1;
	root->endY = -1;
#endif
	FIELD(0,0) = 1;
	FIELD(1,0) = 1;
	path = root;
	filled = 2;

	int perfects = 0;

#ifdef CHECK_ENDS

	char* filledNeighbors = malloc(fieldCapacity);
	memset(filledNeighbors, 0, fieldCapacity);
	int i;
	for (i = 0; i < fieldSize; i++) {
		FN(i,0)++;
		FN(i,fieldSize-1)++;
		FN(0,i)++;
		FN(fieldSize-1,i)++;
	}
	FN(0,0)++;
	if (fieldSize>1) {
		FN(0,1)++;
		FN(1,1)++;
		FN(1,0)++;
	}
	if (fieldSize>2) FN(2,0)++;

#endif

	int start = time(0);

	while(path != NULL) { // Hauptschleife. Sucht so lange weiter, bis der Pfad Null ist.


#ifdef CHECK_ENDS
	#ifdef DEBUG

		{
			int x, y, dir;
			int totalFilled = 0;
			for (x = 0; x < fieldSize; x++) {
				for (y = 0; y < fieldSize; y++) {
					int fn = 0;
					for (dir = 0; dir < 4; dir++) {
						int nx = x+vx[dir];
						int ny = y+vy[dir];
						fn += (nx < 0) || (nx >= fieldSize) || (ny < 0) || (ny >= fieldSize) || FIELD(nx,ny);
					}
					if (FN(x,y) != fn) {
						dlog("discovered error in FN (%d / %d): found: %d; expected: %d!", x, y, FN(x,y), fn);
						return 1;
					}
					if (fieldSize>3 && !FIELD(x,y) && fn >= 3 && (x != endX || y != endY) && (x != path->endX || y != path->endY)) {
						dlog("discovered error in end variables (%d / %d): filled neighbors: %d", x, y, fn);
						dlog("endX: %d, endY: %d, path->endX: %d, path->endY: %d", endX, endY, path->endX, path->endY);
						return 1;
					}
					totalFilled += FIELD(x,y);
				}
			}
			if (endX != -1 && FN(endX, endY) < 3) {
				dlog("discovered error in end variables end: (%d / %d); FN(%d,%d): %d", endX, endY, endX, endY, FN(endX,endY));
				return 1;
			}
			if (path->endX != -1 && FN(path->endX, path->endY) < 3) {
				dlog("discovered error in end variables path->end: (%d / %d); FN(%d,%d): %d",
					       		path->endX, path->endY, path->endX, path->endY, FN(path->endX,path->endY));
				return 1;
			}
			if (endX != -1 && FIELD(endX, endY)) {
				dlog("end (%d / %d) is filled!", endX, endY);
				DEBUG_FIELD;
				return 1;
			}
			if (totalFilled != filled) {
				dlog("error in filled");
				return 1;
			}
		}
	#endif
#endif


		x = path->x+vx[path->dir];
		y = path->y+vy[path->dir];

		int recheckEnds = 0;

		while (x<0 || y<0 || x>=fieldSize || y >= fieldSize || FIELD(x,y)) { // Eine Schleife, die den Pfad so lange verändert, bis alle Kombinationen
											//ausprobiert wurden oder bis ein sinnvoller Pfad gefunden wurde

discard_path:
			path->dir++;
			while (path != NULL && path->dir >= 4) {


#ifdef CHECK_ENDS

				if (path->x > 0          ) FN(path->x-1, path->y  )--;
				if (path->y > 0          ) FN(path->x  , path->y-1)--;
				if (path->x < fieldSize-1) FN(path->x+1, path->y  )--;
				if (path->y < fieldSize-1) FN(path->x  , path->y+1)--;

				if (endX != -1) {
					if (FN(endX,endY) < 3) {
						dlog("reset end");
						endX = -1;
						endY = -1;
					} else if (endX == path->endX && endY == path->endY && filled < fieldCapacity-1) {
						dlog("reset end");
						endX = -1;
						endY = -1;
					}
				}

#endif

				FIELD(path->x,path->y) = 0;
				filled--;

				if (path == root) goto finished;
				dlog("step back", endX, endY);
				DEBUG_FIELD;
				pstep temppath = path;
				path--;
				recheckEnds = 1;
				if (path != NULL) {
					path->dir++;
					if (path->endX == endX && path->endY == endY) {
						dlog("reset end");
						endX = -1;
						endY = -1;
					}
				}

			}
			if (path == NULL) {
				goto finished;
			}
			x = path->x+vx[path->dir];
			y = path->y+vy[path->dir];
		}
		if (recheckEnds) {
			if (path->endX != -1 && FN(path->endX, path->endY) < 3) {
				path->endX = -1;
				path->endY = -1;
			}
		}

#ifdef CHECK_SEPARATION

		int freeN = y >           0 && !FIELD(x  ,y-1);
		int freeE = x < fieldSize-1 && !FIELD(x+1,y  );
		int freeS = y < fieldSize-1 && !FIELD(x  ,y+1);
		int freeW = x >           0 && !FIELD(x-1,y  );
		if ( (freeN && ((freeE && FIELD(x+1, y-1)) || (freeW && FIELD(x-1,y-1)))) ||
		     (freeS && ((freeE && FIELD(x+1, y+1)) || (freeW && FIELD(x-1,y+1)))) ||
		     (freeS && freeN && !freeE && !freeW) || (!freeS && !freeN && freeE && freeW)   ) {

			goto discard_path;

		}


#endif

		if (filled == fieldCapacity-1) { // Alle Felder bis auf eines gefüllt, das würden wir jetzt füllen -> perfektes Snakespiel gefunden!
			perfects++;
#ifdef DEBUG
			dlog("PERFECT");
			pstep temppath = path;
			printf("(%d / %d) - ", x, y);
			for (;;) {
				printf("(%d / %d) - ", temppath->x, temppath->y);
				if (temppath == root) break;
				temppath--;
			}
			printf("(0 / 0)\n");
#endif
			goto discard_path;
		}

#ifdef CHECK_SEPARATION
		if (!(freeN || freeE || freeS || freeW)) goto discard_path;
#endif

#ifdef CHECK_ENDS

		dlog("x: %d ; y: %d", x, y);
		
		if (x == endX && y == endY && path->endX != -1) {
			int h;
			dlog("swap endX <-> path->endX (%d / %d ; %d / %d)", endX, endY, path->endX, path->endY);
			h = endX;
			endX = path->endX;
			path->endX = h;

			h = endY;
			endY = path->endY;
			path->endY = h;
		}




		dlog("path->end: (%d / %d)", path->endX, path->endY);
		if (path->endX != -1 && (path->endX != x || path->endY != y)) {
			if (endX != -1) {
				/*
				 * Der Pfad hat eine notwendige Fortführung, die wird aber nicht genommen.
				 * Außerdem existiert ein allgemeines Ende, das wurde aber auch nicht gewählt (sie 20 Zeilen weiter oben).
				 * Da ein ganz anderer Pfad gewählt wurde, kommt es irgendwann zwangsläufig zu einem dritten Ende -> verwerfen.
				 */
				dlog("->D I S C A R D (%d / %d), path->end: (%d / %d), end: (%d / %d)", x, y, path->endX, path->endY, endX, endY);
				DEBUG_FIELD;
				goto discard_path;
			} else {
				dlog("end := path->end (%d / %d)", path->endX, path->endY);
				endX = path->endX;
				endY = path->endY;
			}
		}
		int tx = x, ty = y;

#define IS_END(x,y)  dlog("END: (%d / %d)", x, y);\
	      	     if (ex == -1) { ex = (x); ey = (y); } else if (endX == -1) {endX = (x); endY = (y);dlog("->end");} else {\
			     dlog("D I S C A R D (%d / %d); e (%d / %d); end (%d / %d)",tx,ty,ex,ey,endX,endY); DEBUG_FIELD;goto discard_path;}
		/*
		 * Versuch der Erklärung des obigen Makros:
		 * Wenn bei (x / y) ein Ende vorliegt, wird dies zunächst als notwendige Fortführung des Pfades gespeichert (path->endX/Y).
		 * Wenn eine solche schon existiert, wird es als allgemeines Ende gespeichert (endX/Y).
		 * Wenn ein solches schon existiert, haben wir drei Enden und der Pfad wird verworfen.
		 */
		int ex = -1, ey = -1;
		if (freeN && FN(x, y-1) >= 2) {

			IS_END(x, y-1);

		}
		if (freeE && FN(x+1, y) >= 2) {

			IS_END(x+1, y);

		}
		if (freeS && FN(x, y+1) >= 2) {

			IS_END(x, y+1);

		}
		if (freeW && FN(x-1, y) >= 2) {

			IS_END(x-1, y);

		}


#endif

		// Der Pfad wird fortgeführt
		
		pstep node = path+1;

		node->x = x;
		node->y = y;
		node->lastDir = path->dir;
		node->dir = 0;
#ifdef CHECK_ENDS
		node->endX = ex;
		node->endY = ey;
		if (x > 0          ) FN(x-1, y  )++;
		if (y > 0          ) FN(x  , y-1)++;
		if (x < fieldSize-1) FN(x+1, y  )++;
		if (y < fieldSize-1) FN(x  , y+1)++;
		if (ex == endX && ey == endY && filled<fieldCapacity-2) {
			dlog("reset end");
			endX = -1;
			endY = -1;
		}
#endif
		filled++;
		FIELD(x,y) = 1;
		path = node;
#ifdef CHECK_ENDS
		dlog("path->end: (%d / %d)", path->endX, path->endY);
#endif

	}
finished:
	printf("finished\n");
	printf("%u perfect games in %ux%u (%us)\n", perfects*2, fieldSize, fieldSize, time(0)-start);
	return 0;
}