UVa 11195 : Another n-Queen Problem

問題リンク : http://uva.onlinejudge.org/external/111/11195.html

問題概要 :
n*nのグリッド上にn個のQueenを置きたい
ただし、Queenを置く際にそのQueenは別のQueenから攻撃されないような場所にしなければならない
グリッド上にはいくつかの'*'が存在する
このセルにはQueenを置く亊ができない
上記の条件を満たした上で、何通りの置き方が存在するか？

解法：
バックトラックで探索する
再帰関数には３つのビットの引数をもたせる
これらはそれぞれ、過去に置いたQueenによって置けない行をビットでもっている
下のコードでは、最初x=0の時、これまでのQueenの攻撃を受けないyを全て試し
次にx=1の時、次はx=2, ・・・, x=n-1までこの順番で行う

コード；

#include<iostream>
#include<cmath>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define MAX 16

using namespace std;

int n,ans;
char field[MAX][MAX];

void rec(int cur,int row,int rdi,int ldi)
{
  if(cur >= n)
    {
      ans++;
      return;
    }

  int ok = ((1<<n)-1) & (~(row|rdi|ldi));
  while(ok)
    {
      int use = ok & -ok;
      ok -= use;
      int y = log2(use);
      if(field[y][cur] == '*')continue;
      rec(cur+1,row|use,(rdi|use)>>1,(ldi|use)<<1);
    }

}

int main()
{
  int CNT = 1;
  while(cin >> n,n)
    {
      ans = 0;
      rep(i,n)rep(j,n)
	{
	  cin >> field[i][j];
	}

      ans = 0;

      rec(0,0,0,0);

      cout << "Case " << CNT++ << ": " << ans << endl;
    }
  return 0;
}