#include <stdio.h>
#include <stdlib.h>

void showboard(int **table,int size)
{
	printf("\n");
	for(int i = 0;i < size;i++)
	{
		for(int j = 0;j < size;j++)
			printf("[%2d]",*(*(table + i) + j));
		printf("\n");
	}
}

int check(int **table,int size)
{
	int i,j,sum,temp;

	temp = (1 + size * size) * size / 2;

	for(i = 0;i < size;i++)
	{
		sum = 0;
		for(j = 0;j < size;j++)
			sum += *(*(table + i) + j);
		if(sum != temp)
			return 0;
	}

	for(j = 0;j < size;j++)
	{
		sum = 0;
		for(i = 0;i < size;i++)
			sum += *(*(table + i) + j);
		if(sum != temp)
			return 0;
	}

	sum = 0;
	for(i = 0;i < size;i++)
		sum += *(*(table + i) + i);
	if(sum != temp)
		return 0;

	sum = 0;
	for(i = 0;i < size;i++)
		sum += *(*(table + i) + size - i - 1);
	if(sum != temp)
		return 0;

	return 1;
}

void gen(int size,int time)
{
	int i,j,k,flag,sum;
	static int **table;	/* board */
	static int *used;	/* record if used */

	/* firsr time ,initial */
	if(time)
	{
		/* get mem */
		table = (int **)malloc(sizeof(int *) * size);
		for(i = 0;i < size;i++)
			*(table + i) = (int *)malloc(sizeof(int) * size);
		used = (int *)malloc(sizeof(int) * size * size);

		/* initial board and used table */
		for(i = 0;i < size;i++)
			for(j = 0;j < size;j++)
				*(*(table + i) + j) = 0;
		for(i = 0;i < size * size;i++)
			*(used + i) = 0;
	}

	/* check if the board is full */
	sum = 0;
	for(i = 0;i < size * size;i++)
	{
		sum += *(used + i);
	}

	/* is full */
	if(sum == size * size)
	{
		/* if success print the board */
		if(check(table,size))
		{
			showboard(table,size);
		}
		return;
	}

	/* find where is the first point not been used */
	flag = 0;
	for(i = 0;i < size;i++)
	{
		for(j = 0;j < size;j++)
		{
			if(!*(*(table + i) + j))
			{
				flag = 1;
				break;
			}
		}
		if(flag)
			break;
	}

	/* here is the most important part */
	for(k = 0;k < size * size;k++)
	{
		/* find the number not been used */
		if(!*(used + k))
		{
			*(used + k) = 1;	/* set the number used */
			*(*(table + i) + j) = k + 1;	/* put the number */
			gen(size,0);	/* recursive generate */
			*(used + k) = 0;	/* set the number not used */
			*(*(table + i) + j) = 0;	/* pick up the number */
		}
	}
}

int main()
{
	int n;
	printf("Please input the board size : ");
	scanf("%d",&n);
	gen(n,1);
	return 0;
}