アルゴリズムとデータ構造 補足資料10-2 「nクイーン」 横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

バックトラックアルゴリズム とりあえずやってみる ダメなら戻って別の道を探る 試行錯誤（trial and error） あのとき別の道を選んでいたら、、、 試行錯誤（trial and error） 結局全部のケースをやってみる（完全解）

nクイーン（n-queens） チェスの「クイーン」

nクイーン（n-queens） チェスの「クイーン」、n x nの盤面上で、 n個のクイーンが お互いに取らない （効き筋にならない） 　　　　　　　　　　　　　　　　　　　お互いに取らない 　　　　　　　　　　　　　　　　　　　（効き筋にならない） 　　　　　　　　　　　　　　　　　　　ように配置

nクイーン（n-queens） この問題を解くためのデータ構造

nクイーン（n-queens） この問題を解くためのデータ構造 column 列 col = 0 col = 1 col = 2 row 行 row = 0 row = 1 row = 2 row = 3 row = 4

nクイーン（n-queens） この問題を解くためのデータ構造 すでに効き筋 →FALSE queenを置ける →TRUE column 列 row 行 TRUE FALSE row = 0 row = 1 row = 2 row = 3 row = 4

nクイーン（n-queens） この問題を解くためのデータ構造 すでに効き筋 →FALSE queenを置ける →TRUE これを2次元配列で 書いてもよいが、ここでは 次の3つの配列で表現 column 列 col = 0 col = 1 col = 2 col = 3 col = 4 row 行 TRUE FALSE row = 0 row = 1 row = 2 row = 3 row = 4

nクイーン（n-queens） この問題を解くためのデータ構造 配列１： q_row[row] その行にqueenが いるときにFALSE いないときにTRUE column 列 col = 0 col = 1 col = 2 col = 3 col = 4 row 行 TRUE FALSE row = 0 row = 1 row = 2 row = 3 row = 4

nクイーン（n-queens） この問題を解くためのデータ構造 配列2： q_se[col-row+N-1] 南東斜め筋は column 列 col = 0 col = 1 col = 2 col = 3 col = 4 row 行 TRUE FALSE col-row=-1 row = 0 row = 1 row = 2 row = 3 row = 4

nクイーン（n-queens） この問題を解くためのデータ構造 配列3： q_sw[col+row] 南西斜め筋は col+rowが一定！ column 列 col = 0 col = 1 col = 2 col = 3 col = 4 row 行 TRUE FALSE col+row=-3 row = 0 row = 1 row = 2 row = 3 row = 4

nクイーン（n-queens） この問題を解くためのデータ構造 配列： q_pos[col]=row この配列だけ、 前の3つと値が 異なることに注意 column 列 col = 0 col = 1 col = 2 col = 3 col = 4 row 行 row = 0 row = 1 row = 2 row = 3 row = 4

nクイーン（n-queens） バックトラックによる解法 配列： q_pos[col]=row に、とりあえず 置いてみる。 column 列 col = 0 col = 1 col = 2 col = 3 col = 4 row 行 row = 0 row = 1 row = 2 row = 3 row = 4

nクイーン（n-queens） バックトラックによる解法 配列： q_pos[col]=row に、とりあえず 置いてみる。 効き筋を埋める column 列 col = 0 col = 1 col = 2 col = 3 col = 4 row 行 FALSE row = 0 row = 1 row = 2 row = 3 row = 4

A B C nクイーン（n-queens） バックトラックによる解法 配列： q_pos[col]=row に、とりあえず 置いてみる。 次の候補は A, B, C column 列 col = 0 col = 1 col = 2 col = 3 col = 4 row 行 FALSE A B C row = 0 row = 1 row = 2 row = 3 row = 4

nクイーン（n-queens） バックトラックによる解法 配列： q_pos[col]=row とりあえずA q_pos[1]=2 に置いてみる column 列 col = 0 col = 1 col = 2 col = 3 col = 4 row 行 FALSE row = 0 row = 1 row = 2 row = 3 row = 4

nクイーン（n-queens） バックトラックによる解法 配列： q_pos[col]=row とりあえずA 効き筋チェック column 列 col = 0 col = 1 col = 2 col = 3 col = 4 row 行 FALSE row = 0 row = 1 row = 2 row = 3 row = 4

A nクイーン（n-queens） バックトラックによる解法 配列： q_pos[col]=row とりあえずA 次の候補はA column 列 col = 0 col = 1 col = 2 col = 3 col = 4 row 行 FALSE A row = 0 row = 1 row = 2 row = 3 row = 4

nクイーン（n-queens） バックトラックによる解法 配列： q_pos[col]=row とりあえずA q_pos[2]=4 に置いてみる column 列 col = 0 col = 1 col = 2 col = 3 col = 4 row 行 FALSE row = 0 row = 1 row = 2 row = 3 row = 4

nクイーン（n-queens） バックトラックによる解法 配列： q_pos[col]=row とりあえずA 効き筋チェック column 列 col = 0 col = 1 col = 2 col = 3 col = 4 row 行 FALSE row = 0 row = 1 row = 2 row = 3 row = 4

nクイーン（n-queens） バックトラックによる解法 この場合には うまくいっていますが、 次の候補がなければ キャンセルして 前に戻る （バックトラック） column 列 col = 0 col = 1 col = 2 col = 3 col = 4 row 行 FALSE row = 0 row = 1 row = 2 row = 3 row = 4

nクイーン（n-queens） チェスの「クイーン」、n x nの盤面上で、 n個のクイーンがお互いに取らない 　　（効き筋にならない）ように配置 考え方： とりあえず、置いてみる。 行き詰ったら、前に戻って（バックトラック）、別の選択肢でやってみる。