PKU 1315 Don't Get Rooked (ZOJ 1002 Fire Net)

http://poj.org/problem?id=1315
nクイーン問題に似たような問題。

dfs

string in[4];
int n,ans;

void dfs(int pos,int tans){
  ans=max(ans,tans);
  if(pos==n*n){
    ans=max(ans,tans);
    return;
  }
  for(int i=pos;i<n*n;i++){
    int x=i/n,y=i%n;
    if(in[x][y]!='.')continue;
    bool ok=true;
    rep(j,4){
      int cx=x,cy=y;
      while(0<=cx && cx<n && 0<=cy && cy<n && in[cx][cy]!='X'){
        if(in[cx][cy]=='x')ok=false;
        cx+=dx[j];
        cy+=dy[j];
      }
    }
    if(!ok)continue;
    in[x][y]='x';
    dfs(i+1,tans+1);
    in[x][y]='.';
  }
}

main(){
  while(cin>>n,n){
    rep(i,n)cin>>in[i];
    ans=0;
    dfs(0,0);
    cout<<ans<<endl;
  }
}

4/16追記
ZOJの1002が全く同じ問題みたいですね。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=2