【正经题解】棋盘问题

正解深搜
但是，不一定第一个搜到的就是最优的，如果直接输出第一个搜到的，那么最后一个点会过不去
首先，从（ $1$ ， $2$ ）开始搜，因为（ $1$ ， $1$ ）固定为 $1$ ，然后他要求第一行和第一列的和最小，则我们可以使不在第一 行或第一列的数尽量的大，也就是从大到小枚举，则剩下给第一行和第一列的数也就更小了，则这样搜出来的第一个解即是正解。
这里我还加了个优化，用线性筛素数来判断。

#include <cstdio>
#include <cstring>
#include <cstdlib>
int f[11][11];
int n,a[210],t=0;
bool v[210];
bool s[110];
int ans[11][11];
inline void dfs(int x,int y)
{
    if(x==n+1&&y==1)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            printf("%d ",f[i][j]);
            printf("\n");
        }
        exit(0);//直接结束程序，注意要用<cstdlib>头文件
    }
    if(x==1||y==1)
    {
        for(int i=2;i<=n*n;i++)
        {
            if(s[i])continue;
            if((x==1&&y!=1&&!v[i+f[x][y-1]])||(x!=1&&y==1&&!v[i+f[x-1][y]])||(x!=1&&y!=1&&!v[i+f[x-1][y]]&&!v[i+f[x][y-1]]))//判断相加是否为素数
            {
                f[x][y]=i;s[i]=true;//标记i出现过
                if(y==n)dfs(x+1,1);
                else dfs(x,y+1);
                f[x][y]=0;s[i]=false;
            }
        }
    }
    else
    {
        for(int i=n*n;i>=2;i--)//如果不是第一行或第一列的数那么就让他拿尽量大的数，把小的留给第一行或第一列的位置
        {
            if(s[i])continue;
            if((x==1&&y!=1&&!v[i+f[x][y-1]])||(x!=1&&y==1&&!v[i+f[x-1][y]])||(x!=1&&y!=1&&!v[i+f[x-1][y]]&&!v[i+f[x][y-1]]))//同上
            {
                f[x][y]=i;s[i]=true;
                if(y==n)dfs(x+1,1);
                else dfs(x,y+1);
                f[x][y]=0;s[i]=false;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    if(n==1)
    {
        printf("NO");
        return 0;
    }
    memset(s,false,sizeof(s));
    memset(v,false,sizeof(v));
    for(int i=2;i<=n*n*2;i++)//注意要枚举到n^2的两倍，因为两个数相加很可能大于n
    {
        if(!v[i])//线性筛素数
        {
            a[++t]=i;
        }
        for(int j=1;j<=t;j++)
        {
            if(i*a[j]>200)break;
            v[i*a[j]]=true;
            if(i%a[j]==0)break;
        }
    }
    memset(f,0,sizeof(f));
    f[1][1]=1;s[1]=true;
    dfs(1,2);
    printf("NO");
    return 0;
}