UVa 750 : 8 Queens Chess Problem

問題リンク : 8 Queens Chess Problem

問題概要 :
8*8のグリッド上に８個のQueenを置きたい
ただしQueenが攻撃できる場所に別のQueenを置く亊はできない
そのようなQueenの配置の仕方を全て辞書順で出力せよ
入力で与えられた列には入力で与えられた行にしか置く亊ができない

解法 :
バックトラックでシュミレーションする
ビットで今見ている列の置けない場所の情報を管理する
これまでに置いたQueenによって置けなくなった行をそれぞれrow,rdiagonal,ldiagonalとして管理した
答えの数が2桁になった時に余計な空白を先頭に出力しないように注意すること

コード：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cassert>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<iomanip>
#include<deque>
#include<queue>
#include<stack>
#include<sstream>
#include<vector>
#include<list>
#include<climits>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define all(n) (n).begin(),(n).end()
#define eps (1e-10)
#define equals(a,b) (fabs((a)-(b))<eps)

using namespace std;

typedef pair<int,int> ii;
typedef long long ll;
typedef unsigned long long ull;

int ix,iy,CNT;
int pos[8];

void rec(int cur,int row,int rdiagonal,int ldiagonal)
{

  if(cur >= 8)
    {
      cout << setw(2) << CNT++ << "      ";
      rep(i,8)
	{
	  if(i)cout << " ";
	  cout << pos[i]+1;
	}
      cout << endl;
      return;
    }
  if(cur == ix)
    {
      if((row>>iy) & 1)return;
      if((rdiagonal>>iy) & 1)return;
      if((ldiagonal>>iy) & 1)return;
      pos[cur] = iy;
      int Y = (1<<iy);
      rec(cur+1,row|Y,(Y|rdiagonal)>>1,(Y|ldiagonal)<<1);
      return;
    }

  int cand = ((1<<8)-1) & (~(row|rdiagonal|ldiagonal));
  while(cand)
    {
      int p = cand & -cand;
      cand -= p;
      int Y = log2(p);
      pos[cur] = Y;
      rec(cur+1,row|p,(rdiagonal|p)>>1,(ldiagonal|p)<<1);
    }
}

int main()
{

  int T;

  while(cin >> T)
    {
      bool first = true;
      rep(_,T)
	{
	  if(!first)cout << endl;
	  first = false;
	  cin >> iy >> ix;
	  iy--,ix--;
	  cout << "SOLN       COLUMN" << endl;
	  cout << " #      1 2 3 4 5 6 7 8" << endl << endl;
	  CNT = 1;
	  rec(0,0,0,0);
	}
    }
  return 0;
}