タグ

2013年6月5日のブックマーク (1件)

  • バックトラック法

    Nクイーン問題 8クイーン問題と呼ばれるパズルを例にとって,バックトラック法の考え方を説明する。 まず,チェスのクイーンの駒が動ける範囲を解説しよう。クイーンは,次の図のように自分の場所から縦横斜めの方向に何マスでも動くことができる。 8クイーン問題を解く方法として,まず考えられるのは,8個のクイーンの置き方をすべて調べて,条件を満たすものを探す,というものがある。 しかし,8個のクイーンをチェス盤上に置く置き方が 64C8 = 4426165368 通りあることを考えると, この方法があまりにも非現実的であることが分かる。 しかし,1つの行には1個のクイーンしか置けないことを考えると,調べる場合の数を減らすことができる。 すなわち,8つの行それぞれに,1個のクイーンをどこに置くか,ということを考えればいいから, その場合の数は, 8の8乗 = 16777216 通りである。 この考え方で