main.cpp

来自「用回溯法求解4阶幻方问题,列举出所有4阶幻方数阵.」· C++ 代码 · 共 180 行

//回溯法求解4阶幻方
#include <stdio.h>

#define N 16
int flag[N];
int a[N];

typedef int (*Func)(void);

int checked15()
{
	if(a[12] + a[13] + a[14] + a[15] != 34)
		return 0;
	if(a[0] + a[5] + a[10] + a[15] != 34)
		return 0;
	if(a[3] + a[7] + a[11] + a[15] != 34)
		return 0;
	return 1;
}

int checked14()
{
	if(a[12] + a[13] + a[14] >= 34)
		return 0;
	if(a[2] + a[6] + a[10] + a[14] != 34)
		return 0;
	return 1;
}

int checked13()
{
	if(a[1] + a[5] + a[9] + a[13] != 34)
		return 0;
	return 1;
}

int checked12()
{
	if(a[0] + a[4] + a[8] + a[12] != 34)
		return 0;
	if(a[3] + a[6] + a[9] + a[12] != 34)
		return 0;
	return 1;
}

int checked11()
{
	if(a[3] + a[7] + a[11] >= 34)
		return 0;
	if(a[8] + a[9] + a[10] + a[11] != 34)
		return 0;
	return 1;
}

int checked10()
{
	if(a[2] + a[6] + a[10] >= 34)
		return 0;
	if(a[8] + a[9] + a[10] >= 34)
		return 0;
	return 1;
}

int checked9()
{
	if(a[1] + a[5] + a[9] >= 34)
		return 0;
	return 1;
}

int checked8()
{
	if(a[0] + a[4] + a[8] >= 34)
		return 0;
	return 1;
}

int checked7()
{
	if(a[4] + a[5] + a[6] + a[7] != 34)
		return 0;
	return 1;
}

int checked6()
{
	if(a[4] + a[5] + a[6] >= 34)
		return 0;
	return 1;
}

int checked5()
{
	return 1;
}

int checked4()
{
	return 1;
}

int checked3()
{
	if(a[0] + a[1] + a[2] + a[3] != 34)
		return 0;
	return 1;
}

int checked2()
{
	if(a[0] + a[1] + a[2] >= 34)
		return 0;
	return 1;
}

int checked1()
{
	return 1;
}

int checked0()
{
	return 1;
}

Func checked[] = {checked0,checked1,checked2,checked3,checked4,checked5,checked6,checked7,\
checked8,checked9,checked10,checked11,checked12,checked13,checked14,checked15};

int counter = 0;

void Print()
{
	int i;
	printf("%d \n",++counter);
	for(i=0; i<N; i++)
	{
		printf("%4d",a[i]);
		if(i%4==3)
			printf("\n");
	}
	printf("\n");
}

void main()
{
	int k;
	int i;
	for(i=0; i<N; i++)
	{
		flag[i] = 0;
		a[i] = 0;
	}

	k=0;

	while(k>=0)
	{
		while(++a[k]<=N)
		{
			if(!flag[a[k]-1])
			{
				if(k == N-1 && checked[k]())
				{
					Print();
					break;
				}
				else if(k < N-1 && checked[k]())
				{
					flag[a[k]-1] = 1;
					k++;
				}
			}
		}
		
		a[k--] = 0;
		if(k>=0)
			flag [a[k]-1] = 0;
		
	}
}