最近 discord のエンジニアサーバーでお互いにクイズを出し合って遊んでいる。その中でエイトクイーンを出題してみた。
問題文:
エイトクイーンを解くプログラムを作ってください。 エイトクイーンはチェスのマス目上にクイーンのコマを8個並べるパズルです。 クイーンは上下左右斜めの8方向に遮るものがない限り進むことができます（将棋の飛車と角行をあわせた動き）。 クイーンが他のどのクイーンも遮らないように8個全てマス目上に並べてください。 出力は文字列でクイーンは「Q」なにもないマスは「.」で表現することで出力してください。 以下に例を示します。 入力: なし 出力: Q . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . Q . . . . . . . . . . . Q . . Q . . . . . . . . . Q . . . . 解は複数ありますが、1パターンのみ出力できればOKです。 応用問題。余力のある人は入力でn（数値）を受け取って、n個のクイーンをn x n の大きさのマスにならべてください。nに大きい数をいれても実行可能な時間で計算できるようにすること
エイトクイーンはアルゴリズムの題材としてよく出てくるテーマで、バックトラック法や動的計画法などで解くことができる。解説サイトも多数あるが、それなりに難易度が高いのでサーバーでは結構盛り上がった。
回答
僕は次のサイトを参考にした。 http://bacspot.dip.jp/virtual_link/www/si.musashi-tech.ac.jp/new_www/Python_IntroProgramming/03/index-1c.html
完成したコードが次
(ns eight-queen (:require [clojure.string :as s])) (defn conflict? [x y board] (->> (map-indexed vector (take y board)) (some (fn [[y1 x1]] (or (= (- x1 y1) (- x y)) (= (+ x1 y1) (+ x y))))))) (defn check? [board] (->> (map-indexed vector board) (every? (fn [[y x]] (not (conflict? x y board)))))) (defn queen [n] (loop [board (vec (range n))] (if (check? board) board (recur (shuffle board))))) (defn display-queen [n] (let [board (vec (repeat n (vec (repeat n ".")))) queens (map-indexed vector (queen n)) result (reduce #(assoc-in %1 %2 "Q") board queens)] (println (s/join "\n" (map #(s/join " " %) result))))) (display-queen 8)
非常に短いコードになって驚いている。どう考えても参考サイトのアルゴリズムがすごい。 参考サイトに詳しくあるが、将来リンク切れする可能性があるので少し解説する。
まず、クイーンの座標を一次元配列で表現する。
添字が y 座標、値が x 座標。 クイーンは縦横方向に重なり合って置くことはないので、重複のない一次元配列で表現することで必然的に縦横の衝突を考える必要がなくなる。
次に斜め方向だがこれは次のように x, y 座標を足すまたは引くことで判定する。
これもシンプルで秀逸なロジックだと思う。
参考サイトではクイーンを置く位置をすべて表示するコードなので順列を使ってクイーンを並べているけど、今回は一つの解を出す問題なので、ランダムにクイーンを並べて条件を満たしていればOK、満たしてなければ再度並べ直すというロジックにした。
回答2: バックトラック法
クイーンの配置をランダムにするだけではつまらなかったのでバックトラック法で並べてみることにした。 つまり、１つクイーンをおいて次のクイーンを置くときに条件を満たしていれば置く、だめだったら一つ前のクイーンを取り除いて再度置き直すというロジックにした。
(ns eight-queen2 (:require [clojure.string :as s])) (defn check? [x y queens] (not (->> (map-indexed vector queens) (some (fn [[qy qx]] (or (= y qy) (= x qx) (= (- qx qy) (- x y)) (= (+ qx qy) (+ x y)))))))) (defn pop-queen [n x queens] (if (>= x n) (recur n (inc (peek queens)) (pop queens)) [x queens])) (defn queen ([n] (queen n 0 ())) ([n x queens] (if (>= (count queens) n) queens (when (< x n) (if (check? x (count queens) (reverse queens)) (recur n 0 (conj queens x)) (let [[nx nqueens] (pop-queen n (inc x) queens)] (recur n nx nqueens))))))) (defn display-queen [n] (let [board (vec (repeat n (vec (repeat n ".")))) queens (map-indexed vector (queen n)) result (reduce #(assoc-in %1 %2 "Q") board queens)] (println (s/join "\n" (map #(s/join " " %) result))))) (display-queen 8)
バックトラックは stack を使ったほうがわかりやすいコードになるが、ここでは再帰を使っている。 だいたい次の動きをする。
check?で条件を満たしていればクイーンを置いて、次のクイーンを置きに行く- 条件を満たしていなければ以前のクイーンを再配置する。このときクイーンが置かれていた位置から一つ右の位置からクイーンを置き始める。右端にクイーンがおいてあった場合、もう一つ前のクイーンから置き直す。
比較用にRubyのコードも示す。
def check?(x, y, queens) !queens.each_with_index.any? {|qx, qy| y == qy || x == qx || (qx - qy) == (x - y) || (qx + qy) == (x + y) } end def queen(n) queens = [] while queens.size < n x = 0 while x < n if check?(x, queens.size, queens) queens.push(x) break else x += 1 while x >= n x = queens.pop x += 1 end end end end queens end def display_queen(n) queens = queen(n) result = [] n.times do |x| row = [] n.times do |y| row << if queens[y] == x 'Q' else '.' end end result[x] = row.join(' ') end result.join("\n") end puts display_queen(8)
再帰が while になっていること以外はだいたい同じ。Clojureはどうも配列の末尾に要素を追加したり、末尾以外の要素を取得する処理が書きづらい。Stackを使いたい場合は javaの stack を使うのが一番楽な気がする。