「新・明解Pythonで学ぶアルゴリズムとデータ構造」で勉強日記#19 - Qiita

【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」 前回の記事はこちら 5-4 8王妃問題 今回もハノイの塔と同様に、問題を小さく分割することで8王妃問題を学習します。 8王妃問題とは 互いに取りあえないように、8個の王妃(チェスのクイーン)をチェス盤に配置せよ。という問題です。 王妃の配置 8個の王妃を配置する組み合わせは全部で、64×63×62×61×60×59×58×57=178462987637760通りあります。そこで、 【方針1】各列には王妃を1個だけ配置する とすると、8の8乗=16777216通りになります。 これでも、すべての配置が8王妃問題の会ではありません。 そこで、 【方針2】各行には王妃を1個だけ配置する とします。 分枝操作 次々と枝分かれを行うことによって、すべての組み合わせを列挙するプログラムを作ります。 #各列に1個の王妃を配置する組み合わせを