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

アルゴリズムとデータ構造 補足資料 10-2

「 n クイーン」

横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

バックトラックアルゴリズム

• とりあえずやってみる

• ダメなら戻って別の道を探る

– あのとき別の道を選んでいたら、、、

• 試行錯誤（ trial and error ）

– 結局全部のケースをやってみる（完全解）

n クイーン（ n-queens ）

• チェスの「クイーン」

• チェスの「クイーン」、 n x n の盤面上で、

n 個 のクイーンが

お互 いに取らない

筋にならない）

よう に配置

n クイーン（ n-queens ）

• この問題を解くためのデータ構造

n クイーン（ n-queens ）

• この問題を解くためのデータ構造

n クイーン（ n-queens ）

column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

• この問題を解くためのデータ構造

• すでに効き筋

→FALSE

• queen を置ける

→TRUE

n クイーン（ n-queens ）

TRUE

FALSE TRUE FALSE TRUE

FALSE FALSE FALSE TRUE TRUE

FALSE FALSE FALSE FALSE FALSE

FALSE FALSE FALSE TRUE TRUE

TRUE FALSE TRUE FALSE TRUE column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

• この問題を解くためのデータ構造

• すでに効き筋

→FALSE

• queen を置ける

→TRUE

これを

2

書いてもよいが、ここでは 次の

3

n クイーン（ n-queens ）

TRUE

FALSE TRUE FALSE TRUE

FALSE FALSE FALSE TRUE TRUE

FALSE FALSE FALSE FALSE FALSE

FALSE FALSE FALSE TRUE TRUE

TRUE FALSE TRUE FALSE TRUE column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

• この問題を解くためのデータ構造 配列１：

q_row[row]

その行に queen が いるときに FALSE いないときに TRUE

n クイーン（ n-queens ）

TRUE

FALSE TRUE FALSE TRUE

FALSE FALSE FALSE TRUE TRUE

FALSE FALSE FALSE FALSE FALSE

FALSE FALSE FALSE TRUE TRUE

TRUE FALSE TRUE FALSE TRUE column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

• この問題を解くためのデータ構造 配列 2 ：

q_se[col-row+N-1]

南東斜め筋は

col-row が一定！

n クイーン（ n-queens ）

TRUE

FALSE TRUE FALSE TRUE row=-1 col-

FALSE FALSE FALSE TRUE TRUE

FALSE

row=-1 col-

FALSE FALSE FALSE FALSE

FALSE FALSE

row=-1 col-

FALSE TRUE TRUE

TRUE FALSE TRUE

col- row=-1

FALSE TRUE column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

• この問題を解くためのデータ構造 配列 3 ：

q_sw[col+row]

南西斜め筋は

col+row が一定！

n クイーン（ n-queens ）

TRUE

FALSE TRUE

col+row

FALSE =-3 TRUE

FALSE FALSE

col+row

=-3

FALSE TRUE TRUE

FALSE

col+row

=-3

FALSE FALSE FALSE FALSE col+row

=-3

FALSE FALSE FALSE TRUE TRUE

TRUE FALSE TRUE FALSE TRUE column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

• この問題を解くためのデータ構造 配列：

q_pos[col]=row この配列だけ、

前の 3 つと値が 異なることに注意

n クイーン（ n-queens ）

column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

• バックトラックによる解法 配列：

q_pos[col]=row に、とりあえず 置いてみる。

q_pos[0]=0

n クイーン（ n-queens ）

column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

• バックトラックによる解法 配列：

q_pos[col]=row に、とりあえず 置いてみる。

q_pos[0]=0

効き筋を埋める

n クイーン（ n-queens ）

column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

FALSE

FALSE FALSE FALSE FALSE

FALSE

FALSE

FALSE

FALSE

• バックトラックによる解法 配列：

q_pos[col]=row に、とりあえず 置いてみる。

次の候補は A, B, C

n クイーン（ n-queens ）

column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

FALSE

FALSE FALSE FALSE FALSE

FALSE

A FALSE

B FALSE

C FALSE

• バックトラックによる解法 配列：

q_pos[col]=row とりあえず A q_pos[1]=2

に置いてみる

n クイーン（ n-queens ）

column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

FALSE FALSE FALSE FALSE FALSE

FALSE

FALSE

FALSE

FALSE

• バックトラックによる解法 配列：

q_pos[col]=row とりあえず A

効き筋チェック

n クイーン（ n-queens ）

column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

FALSE FALSE FALSE FALSE FALSE

FALSE FALSE FALSE

FALSE FALSE FALSE FALSE FALSE

FALSE FALSE FALSE

FALSE FALSE

• バックトラックによる解法 配列：

q_pos[col]=row とりあえず A 次の候補は A

n クイーン（ n-queens ）

column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

FALSE FALSE FALSE FALSE FALSE

FALSE FALSE FALSE

FALSE FALSE FALSE FALSE FALSE

FALSE FALSE FALSE

A FALSE FALSE

• バックトラックによる解法 配列：

q_pos[col]=row とりあえず A q_pos[2]=4

に置いてみる

n クイーン（ n-queens ）

column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

FALSE FALSE FALSE FALSE FALSE

FALSE FALSE FALSE

FALSE FALSE FALSE FALSE FALSE

FALSE FALSE FALSE

FALSE FALSE

• バックトラックによる解法 配列：

q_pos[col]=row とりあえず A

効き筋チェック

n クイーン（ n-queens ）

column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

FALSE FALSE FALSE FALSE FALSE

FALSE FALSE FALSE

FALSE FALSE FALSE FALSE FALSE

FALSE FALSE FALSE FALSE

FALSE FALSE FALSE FALSE FALSE

• バックトラックによる解法 この場合には

うまくいっていますが、

次の候補がなければ キャンセルして

前に戻る

（バックトラック）

n クイーン（ n-queens ）

column

col = 0 col = 1 col = 2 col = 3 col = 4 row

row = 0

row = 1

row = 2

row = 3

row = 4

FALSE FALSE FALSE FALSE FALSE

FALSE FALSE FALSE

FALSE FALSE FALSE FALSE FALSE

FALSE FALSE FALSE FALSE

FALSE FALSE FALSE FALSE FALSE

• チェスの「クイーン」、 n x n の盤面上で、

n 個のクイーンがお互いに取らない （効き筋にならない） ように配置

• 考え方：

– とりあえず、置いてみる。

– 行き詰ったら、前に戻って（バックトラック）

、別の選択肢でやってみる。

n クイーン（ n-queens ）