J2EE之巅

 

The Clojure Program To solve N Queens Problem (Without back tracing)

Not like the previous solution here http://www.blogjava.net/chaocai/archive/2012/08/05/384844.html
The following solution not using the back tracing way is more concise and readable, but for the searching space becomes huger, the performance is much worser then the previous one.

(ns SICP.unit3)
(defn conflictInCol? [s col]
  (some #(= col %) s)
)

(defn conflictInDia? [s col]
  (let [dia (count s)
        n1 (fn [c
] (Math/abs (- dia (.indexOf s c))))
        n2 (fn [c] (Math/abs (- col c)))]
    (some #(= (n1 %) (n2 %)) s)
  )
)

(defn safe? [s col] 
  (not (or (conflictInCol? s col) (conflictInDia? s col)))
)
  
(defn next-level-queens [solutions-for-prev-level board-size current-level]
  (let [solutions (atom [])]
    (doseq [s solutions-for-prev-level]
      (doseq [col (range 0 board-size)]
        (if (safe? s col)
          (reset! solutions (cons (conj s col) @solutions))
     
        )
       )
   
    )
   
      (if (< current-level (dec board-size))
        (recur @solutions board-size (inc current-level))
        (count @solutions)
      )
   )
)

(defn queens [board-size]
  (next-level-queens  (apply vector (map #(vector %) (range 0 board-size))) board-size 1)
)

Chao Cai (蔡超)
Sr. SDE
Amazon


 

posted on 2012-11-26 12:21 超越巅峰 阅读(2775) 评论(0)  编辑  收藏 所属分类: Clojure


只有注册用户登录后才能发表评论。


网站导航:
 

导航

统计

常用链接

留言簿(12)

随笔分类(54)

随笔档案(59)

文章分类(2)

文章档案(1)

相册

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜