#include <stdio.h>
#include <stdbool.h>

#define N	17								// N >= 3

bool Node[2 * N + 1][N + 1];

unsigned long long Polygons;

void step(unsigned n, int h, int v, int h_right, int h_left, int v_up)
{
	if (Node[h][v]) return;

	if (n == 4 * N) {							// one horizontal step away from start (-1, 2)
		Polygons++;
		return;
	}

	Node[h][v] = true;

	if (n % 2) {								// n odd: vertical step

		if (v_up)
			step(n + 1, h, v + 1, h_right, h_left, v_up - 1);

		if (v > 0)
			if (v > 1 || h > N)
				step(n + 1, h, v - 1, h_right, h_left, v_up);
	} else {								// n even: horizontal step

		if (h_right)
			step(n + 1, h + 1, v, h_right - 1, h_left, v_up);

		if (h_left)
			if (v > 1)
				step(n + 1, h - 1, v, h_right, h_left - 1, v_up);
	}

	Node[h][v] = false;
}

int main()									// first steps are always identical (N >= 3)
{
	Node[N - 1][2] = true;							// step 1: (-1, 2) -> (-1, 1) v down
	Node[N - 1][1] = true;							// step 2: (-1, 1) -> ( 0, 1) h right
	Node[N + 0][1] = true;							// step 3: ( 0, 1) -> ( 0, 0) v down

	step(4, N + 0, 0, N - 1, N, N);						// step 4 starts at ( 0, 0)

	printf("n=%d: %llu polygons.\n", N, Polygons);
}