AtCoder Regular Contest #001 C : パズルのお手伝い

問題概要

一部が埋められた8クイーンがあるので残りを埋めて出力する問題。

解法

5!+枝刈りとかでもよいのだけど、以前書いたN-Queenソルバ(全生成)があるのでそれを使って8-Queenの盤面全部出して与えられたのと合致するかだけ調べた。

acceptされたコード

import std.stdio;

immutable W = 8;

char[W][W+1] target;
int[W] pos;
int bit1, bit2, bit3;

void init(){
	for(int i=0; i<W; ++i){
		scanf("%[^\n]%*c", target[i].ptr);
	}
}

bool dfs(int depth){
	if(depth == W){
		int cnt = 0;
		for(int i=0; i<W; ++i){
			if(target[i][pos[i]] == 'Q'){
				++cnt;
			}
		}
		if( cnt == 3 ){
			for(int i=0; i<W; ++i){
				for(int j=0; j<W; ++j){
					write(pos[i] == j ? 'Q' : '.');
				}
				writeln;
			}
			return true;
		}
		return false;
	}
	
	int cannot = bit1 | bit2 | bit3;
	int t1 = bit1, t2 = bit2, t3 = bit3;
	
	for(int i=0; i<W; ++i)if( !((cannot>>i)&1) ){
		bit1 = t1 | (1<<i);
		bit2 = (t2<<1) | (1<<(i+1));
		bit3 = (t3>>1) | (i>0 ? 1<<(i-1) : 0);
		pos[depth] = i;
		if(dfs(depth+1)){
			return true;
		}
	}
	
	bit1 = t1; bit2 = t2; bit3 = t3;
	return false;
}

void solve(){
	if(!dfs(0)){
		writeln("No Answer");
	}
}

void main(){
	init;
	solve;
}