読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

プログラミングコンテストの練習

NxNのチェス盤にクイーンN個を互いに攻撃し合わないように置く置き方は何通りか?
Rubyで書いてみた。再帰の問題だけど、木をDFSしてるわけだし、途中で探索やめてるし(枝刈り?)、なかなかいい問題じゃん。

N=12

$column=Array.new(N,false)#横方向
$up=Array.new(50,false)#右斜め上方向
$down=Array.new(50,false)#右斜めした方向
$num=0

def nqueen(n)
	if n==N
		$num+=1
		return
	end
	N.times{|i|
		if (!$column[i])&&(!$up[n+i])&&(!$down[n-i])
			$column[i]=$up[n+i]=$down[n-i]=true
			nqueen(n+1)
			$column[i]=$up[n+i]=$down[n-i]=false
		end
	}
end

nqueen(0)
p $num