アルゴリズムとデータ構造 補足資料10-2 「nクイーン」

Presentation on theme: "アルゴリズムとデータ構造 補足資料10-2 「nクイーン」"— Presentation transcript:

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

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

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

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

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

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

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

8 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

9 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

10 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

11 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

12 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

13 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

14 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

15 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

16 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

17 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

18 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

19 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

20 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

21 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

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