这是一道状压DP题，不必想的太复杂。
关键就在于如何进行上下的转换;
f[ i ][ j ][ t ] 表示第i行，j 表示 有几个国王，t 表示在 第 i 行的分布状态；
t 的状态可以先预处理；注意上一层国王影响的将会是下一层的三个结点；
#include<cstdio>
#include<cstdlib>
#include<cstring>
long long a[1024],b[1024];
long long f[10][82][1023];
bool w[1023][1023];
bool ok(int x,int &d){
int p=0;int tot=0;
while(x>0){
if ((x&(-x))<=p*2)return false;
else {p=x&(-x);x-=p;tot++;}
}
d=tot;return true;
}
int main()
{
//freopen("king.in","r",stdin);
//freopen("king.out","w",stdout);
int n,k;scanf("%d%d",&n,&k);
int q=(1<<n)-1,l=0,d;
memset(w,false,sizeof(w));
for(int i=0;i<=q;i++)
if(ok(i,d)==true){
l++;a[l]=i;b[l]=d;
for(int y=1;y<=l;y++)
if(((a[y]&i)==0)&&(((a[y]>>1)&i)==0)&&(((i>>1)&a[y])==0))w[l][y]=w[y][l]=true;
}
memset(f,0,sizeof(f));
for(int j=1;j<=l;j++)
if(b[j]<=k)f[1][b[j]][a[j]]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=l;j++)
for(int t=1;t<=l;t++)
if(w[j][t]==true)
for(int p=b[j];p+b[t]<=k;p++)
f[i][p+b[t]][a[t]]+=f[i-1][p][a[j]];
long long ans=0;
for(int i=1;i<=l;i++)ans+=f[n][k][a[i]];
printf("%I64d\n",ans);
//system("pause");
return 0;
}