ビショップ配置問題

Y.Hanataniさんのところより。面白い問題なので解いてみることにした。
そういえばここのところあんまり問題解いてないなぁ。
英語嫌いなので自分で問題探すの大変だし…。

n*nのチェスボードにk個のビショップを互いに当たらないような配置の数を求める問題。
n-QueenはおそらくNP問題、n-Bishopは果たして。

まず最初に、チェス盤を白黒の市松模様に塗り分けたとき、
黒にあるビショップは白のマスにはどうやっても到達できない、
要するに、黒のマスのビショップは白のマスのビショップには攻撃できないので、
黒と白は全く独立に考えることが出来る。
そういうわけで、結局黒だけ(或いは白だけ)の網状(?)の盤に対して
ビショップ何個かの配置の数が求まれば良い。

次に、盤面を斜めから見てみる。
すると、左から順に縦方向に1個、3個、5個、…、5個、3個、1個
升目があるように見える。
この各ラインに対して置けるビショップは高々1であることが分かるだろう。
それで、ここがポイントなのだが、このラインを左右から2ラインづつ
ビショップを配置していく。
すると、単純な再帰的定義が求まる。

aライン目までにb個ビショップを置いた盤面にビショップc個を配置する組み合わせを
f(a,b,c)とすると、
f(a,b,c)=f(a+1,b,c)+f(a+1,b+1,c-1)*(2*(a*2+1-b))+f(a+1,b+2,c-2)*(a*2+1-b)*(a*2+1-b-1)

この式は盤面サイズの偶奇などにより少々変える必要があるが、
ここの部分は、ビショップの配置を覚えておかずとも、何個置いたかさえ覚えておけば
答えが求まるというところがミソである。
これをこのまま実装すれば最大サイズの問題に対して計算量は3^15ぐらいになって、
まぁ、解けなくも無いか?といったレベルになるが、(確実にTimeLimitExceedだろうけど…)
パラメータが3個、いずれも盤面サイズを越えることが無いような再帰なので、
メモライズすると計算量はO(n^3)になる。

というわけで、一応ソースを。

#include <iostream>
using namespace std;

long long int tbl[31][31][31];
void init()
{
  for (int i=0;i<31;i++)
    for (int j=0;j<31;j++)
      for (int k=0;k<31;k++)
        tbl[i][j][k]=-1;
}

long long int solve(int pos,int rest,int end,int piece)
{
  if (piece<=0) return 1;
  if (pos>end||piece>end) return 0;
  if (tbl[pos][rest][piece]>=0)
    return tbl[pos][rest][piece];

  // 置かない
  long long int ans=solve(pos+2,rest+2,end,piece);

  // 一つ置く
  ans+=(rest*(pos!=end?2:1))*solve(pos+2,rest-1+2,end,piece-1);

  // 二つ置く
  if (rest>=2&&piece>=2&&pos!=end)
    ans+=rest*(rest-1)*solve(pos+2,rest-2+2,end,piece-2);

  return tbl[pos][rest][piece]=ans;
}

int main()
{
  int n,k;
  while(cin>>n>>k,n!=0||k!=0){
    if (k>=n*2)
      cout<<0<<endl;
    else{
      init();
      long long int ans=0;
      if (n%2==0) // 偶数サイズ
        for (int i=0;i<=k;i++)
          ans+=solve(1,1,n,i)*solve(1,1,n,k-i);
      else // 奇数サイズ
        for (int i=0;i<=k;i++)
          ans+=solve(1,1,n,i)*solve(2,2,n,k-i);
      cout<<ans<<endl;
    }
  }
  return 0;
}

…しかし、アルゴリズムを説明するのは難しいなぁ。
図が描ければだいぶ違うんだろうけど。