20131019-n-queens-clj

View Github Repository Open presentation in a new window

kaosf

See all presentation from kaosf

20131019-n-queens-clj

0 0

20131019-n-queens-clj

On Github kaosf / 20131019-n-queens-clj

n-queens problem

date: 2013-10-19

author: ka

N クイーン問題

8 クイーン問題なら聞いたことある？

その一般化された問題

8 クイーン問題

チェス盤に 8 つのクイーンを互いに効かないように配置する

チェスの簡単な説明

将棋と似ている

将棋もチェスも源流はインドのチャトランガというゲーム

王将を「詰め」れば勝ちなのと同様，チェスではキングを「チェックメイト」すれば勝ち

将棋と違うところ

盤面が 8 * 8

取った駒 (チェス用語ではピース) が使えない

引き分けがよくある

駒の種類

  • キング (King)
  • クイーン (Queen)
  • ルーク (Rook)
  • ビショップ (Bishop)
  • ナイト (Knight)
  • ポーン (Pawn)

それぞれの駒の動き

ポーン

前に 1 マスだけ進める

+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | |*| | |
+-+-+-+-+-+
| | |P| | |
+-+-+-+-+-+

最初の一回だけ 2 マス進める

+-+-+-+-+-+
| | |*| | |
+-+-+-+-+-+
| | |*| | |
+-+-+-+-+-+
| | |P| | |
+-+-+-+-+-+

ポーン (駒を取るとき)

斜めにある駒しか取れない

前にある駒はとれない

+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| |*| |*| |
+-+-+-+-+-+
| | |P| | |
+-+-+-+-+-+

ポーン同士が衝突してお互い動けなくなることがよくある

ポーンの特殊ルール

  • プロモーション (昇格)
  • アンパッサン (通過捕獲)

ナイト

桂馬と似た動き

桂馬と違い左右と後ろに同様の動きが出来る

+-+-+-+-+-+
| |*| |*| |
+-+-+-+-+-+
|*| | | |*|
+-+-+-+-+-+
| | |N| | |
+-+-+-+-+-+
|*| | | |*|
+-+-+-+-+-+
| |*| |*| |
+-+-+-+-+-+

ビショップ

角行と同じ

+-+-+-+-+-+
|*| | | |*|
+-+-+-+-+-+
| |*| |*| |
+-+-+-+-+-+
| | |B| | |
+-+-+-+-+-+
| |*| |*| |
+-+-+-+-+-+
|*| | | |*|
+-+-+-+-+-+

ルーク

飛車と同じ

+-+-+-+-+-+
| | |*| | |
+-+-+-+-+-+
| | |*| | |
+-+-+-+-+-+
|*|*|R|*|*|
+-+-+-+-+-+
| | |*| | |
+-+-+-+-+-+
| | |*| | |
+-+-+-+-+-+

クイーン

飛車 + 角行 (ルーク + ビショップ)

+-+-+-+-+-+
|*| |*| |*|
+-+-+-+-+-+
| |*|*|*| |
+-+-+-+-+-+
|*|*|Q|*|*|
+-+-+-+-+-+
| |*|*|*| |
+-+-+-+-+-+
|*| |*| |*|
+-+-+-+-+-+

実際最強である

キング

王将と同じ

+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| |*|*|*| |
+-+-+-+-+-+
| |*|Q|*| |
+-+-+-+-+-+
| |*|*|*| |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+

キングとルークの特殊ルール

  • キャスリング (入城)

初期配置

+-+-+-+-+-+-+-+-+
|R|N|B|Q|K|B|N|R| (Black)
+-+-+-+-+-+-+-+-+
|P|P|P|P|P|P|P|P|
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
|P|P|P|P|P|P|P|P|
+-+-+-+-+-+-+-+-+
|R|N|B|Q|K|B|N|R| (White)
+-+-+-+-+-+-+-+-+

各駒の詳しい説明

それぞれ Wikipedia へのリンクです

チェスのゲーム進行

  • 白が先攻
  • ルールに従いお互い駒を動かす
  • 相手の駒の位置に移動出来る場合はその駒をゲームから除外出来る
  • 自分の駒で自分の駒を除外は出来ない
  • 駒を飛び越して移動することは出来ない
  • ただしナイトは駒を飛び越せる

チェックメイト

チェスでは「王手」のことを「チェック」と言う

チェックをかけつつ相手が次にどう動いても相手のキングを取れる状況になること

これが勝ちの条件

チェックメイト例 1

+-+-+-+-+-+-+-+-+
| | | | | |Q| |K| (<- Black King)
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | |K|
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+

チェックメイト例 2

+-+-+-+-+-+-+-+-+
| | | | | |N| |K| (<- Black King)
+-+-+-+-+-+-+-+-+
| | | | | |K| | |
+-+-+-+-+-+-+-+-+
| | | | | |B| | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+

ステイルメイト

チェスでは「チェックがかかっていない状態」で相手を詰み状態にしてしまうと引き分けになる

ステイルメイト例 1

+-+-+-+-+-+-+-+-+
| | | | | | | |K| (<- Black King)
+-+-+-+-+-+-+-+-+
| | | | | |Q| | |
+-+-+-+-+-+-+-+-+
| | | | | | | |K|
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+

ステイルメイト例 2

+-+-+-+-+-+-+-+-+
| | | | | | |K| | (<- Black King)
+-+-+-+-+-+-+-+-+
| | | | | | |P| |
+-+-+-+-+-+-+-+-+
| | | | | | |K| |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | | |
+-+-+-+-+-+-+-+-+

8 クイーン問題とは何か

先ほど紹介された最強の駒ことクイーン

これを盤面上に 8 つ配置する

ただしどの 2 つの駒もお互いに取られないようにする

実際にやってみよう

実物のチェスにはクイーンは白と黒の 1 つずつしかない

仕方がないのでポーンをクイーンの代わりにしてみる

解答例

+-+-+-+-+-+-+-+-+
|Q| | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | |Q| |
+-+-+-+-+-+-+-+-+
| | | | |Q| | | |
+-+-+-+-+-+-+-+-+
| | | | | | | |Q|
+-+-+-+-+-+-+-+-+
| |Q| | | | | | |
+-+-+-+-+-+-+-+-+
| | | |Q| | | | |
+-+-+-+-+-+-+-+-+
| | | | | |Q| | |
+-+-+-+-+-+-+-+-+
| | |Q| | | | | |
+-+-+-+-+-+-+-+-+

余談

Prolog という論理プログラミング言語

問題のルールと制約を記述するだけ

アルゴリズムを考える必要なし

詳しくは 7 つの言語 7 つの世界にて (本棚にあります)

Clojure で実装する

答えが既に存在する

N-queens problem - Rosetta Code

英語の解説は存在する

以降このコードを読み解くことにする

コードリーディング

(def size 8)

(defn extends? [v n]
  (let [k (count v)]
    (not-any? true?
      (for [i (range k) :let [vi (v i)]]
        (or
          (= vi n)  ;check for shared row
          (= (- k i) (Math/abs (- n vi)))))))) ;check for shared diagonal

(defn extend [vs]
  (for [v vs
        n (range 1 (inc size)) :when (extends? v n)]
    (conj v n)))

(def solutions
  (nth (iterate extend [[]]) size))

(doseq [s solutions]
  (println s))

(println (count solutions) "solutions")

コードリーディング 1

solutions 定義

(def solutions
  (nth (iterate extend [[]]) size))

extend 関数とは何か？

コードリーディング 2-1

extend 関数

(defn extend [vs]
  (for [v vs
        n (range 1 (inc size)) :when (extends? v n)]
    (conj v n)))

コードリーディング 2-2

vs: 初期値は [[]]

(range 1 (inc size))

今 size が 8 なのでこの部分は '(1 2 3 4 5 6 7 8) になる

コードリーディング 2-3

extend 関数は以下のように読める

(defn extend [vs]
  (for [v vs
        n '(1 2 3 4 5 6 7 8) :when (extends? v n)]
    (conj v n)))

コードリーディング 3-1

extend? 関数

(defn extends? [v n]
  (let [k (count v)]
    (not-any? true?
      (for [i (range k) :let [vi (v i)]]
        (or
          (= vi n)  ;check for shared row
          (= (- k i) (Math/abs (- n vi)))))))) ;check for shared diagonal