USACO 8クイーン問題拡張

http://ace.delos.com/usacoprob2?a=lPFJMyj 6 B 9 f&S=checker
この問題のNの範囲は6<=N<=13で、明らかに普通のDFS検索はタイムアウトします。ここでビット演算を使って加速して、三つの変数left、right、midで現在の行の配置状態をマークします。leftは左の状態、rightは右の状態、midは現在の状態です。次の行に移る時、三者の変化状況は以下の通りです。
left=left<<1;
right=right>>1
mid=mid;
参考コードは以下の通りです。

/*
TASK : checker
ID : chris
LANG: C++
*/
#include<stdio.h>
#include<string.h>
int N;
int ans[15] ;
int left , right ,mid ,cnt;
void dfs(int row,int l,int r, int m){
	int left , mid ,right;
	if(row == N+1){
		cnt++;
		if(cnt > 3)	return ;
		printf("%d",ans[1]);
		for(int i=2;i<=N;++i){
			printf(" %d",ans[i]);	
		}	
		printf("
");
		return ;
	}
	int s = ( (m|r)|l ) ;
	bool ok = 0 ;
	
	for(int i=1;i<=N;++i){
		if( ( s&(1<<(i-1)) )!=0 )	continue ;
		mid = (m | (1<<(i-1))) ;
		left = 	(l | (1<<(i-1))) ;
		right = (r | (1<<(i-1))) ;
		left = ( left << 1 ) ;
		right = (right >> 1) ;
		ans[row] = i ;
		dfs(row+1,left,right,mid);
	}
}
int main(){
	//freopen("checker.in","r",stdin);
	//freopen("checker.out","w",stdout);
	while(scanf("%d",&N)!=EOF){
		cnt = 0;
		for(int i=1;i<=N;++i){
			left = right = mid = 0 ;
			ans[1] = i ;
			mid = ( mid|(1<<(i-1)) ) ;
			left = right = mid ;		//       
			left = (left << 1) ;		//       
			right = (right >> 1) ;
			dfs(2,left ,right, mid) ;
		}
		printf("%d
",cnt);
	}	
	return 0 ;	
}