We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Recursion
  4. Super-Queens on a Chessboard
  5. Discussions

Super-Queens on a Chessboard

  • carl_smotricz
     + 0 comments

    A Clojure solution that handles all test cases.

    PERFORMANCE HINT: It pays to look at the "environment" link at the bottom of the page! My code was a bit too slow to handle case 4 (14), and it seems one bottleneck in union-ing sets. The test environment includes a library called int-map which is significantly faster and solved the problem.

    (ns superqueens
    (:require [clojure.data.int-map :as i]))

(def N (Integer/parseInt (read-line)))
; (def N 14)

(defn between [v1 v2 v]
    (and (<= v1 v) (<= v v2)))

(defn between-xy [v1x v1y v2x v2y px py]
    (and (between v1x v2x px) (between v1y v2y py)))

(defn blocked [qx qy x y]
    (or
        (= x qx)
        (= (- x qx) (- y qy))
        (= (- x qx) (- qy y))
        (between-xy (- qx 2)(- qy 2) (+ qx 2)(+ qy 2) x y)))

(def BLOCKERS
    (vec (for [qy (range N) qx (range N)]
        (i/int-set (for [y (range N) x (range N) :when (blocked qx qy x y)]
               (+ x (* N y)))))))

(defn place [row board]
  (if (< row N)
   (let [pmin (* N row)]
     (reduce + (for [p (range pmin (+ N pmin))
                     :when (nil? (board p))]
                 (place 
                    (inc row)
                    (i/union board (BLOCKERS p))))))
   1))

(let [t0 (System/currentTimeMillis)]
  (println (place 0 (i/int-set)))
  (format "Time: %d" (- (System/currentTimeMillis) t0)))