dfs80球跳

#include<iostream>
#include<cstring>
using namespace std;
int n;
bool flag=false;
int a[15][15]={0};
bool taken[225]={false};
bool isprime(int n)
{
	if(n==1)
		return false;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)
			return false;
	} 
	return true;
}
void print()
{
	flag=true;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
}
void dfs(int y,int x)
{
	if(x>n)
	{
		y++;
		x=1;
	}
	if(y>n)
		return;
	for(int i=1;i<=n*n;i++)
	{
		if(!taken[i]&&(isprime(i+a[y-1][x])||y-1==0)&&(isprime(i+a[y][x-1])||x-1==0))
		{
			taken[i]=true;
			a[y][x]=i;
			if(x==n&&y==n)
			{
				print();
				return;
			}
			else
			{
				dfs(y,x+1);
				if(flag)
					return; 
			}
			taken[i]=false;
		}
	}
}
int main()
{
	freopen("sb.in","w",stdout);
	memset(a,0,sizeof(a));
	cin>>n;
	//cout<<isprime(n)<<endl;
	a[1][1]=1;
	taken[1]=true;
	dfs(1,2);
	if(!flag)
		cout<<"NO";	
}