n Queens Problem

I work in a little shop in Monteriggioni (SI) here in Italy, we sell local products like olive oil, Chianti wines, pasta and more; it is a very nice idea but we are in a little hide place and few people can really find us, so most of the time is just myself looking the emptiness in front of me.

Finally I decided to bring my computer and use the plenty of free time I have at work to do something interesting.

Since I have never solved it before I decide to work on the n-Queens problem.

Let’s go straight to the code

(defn new-world [n]
  (mapv (fn [a] (mapv (fn [b] (str a b)) (range n))) (range n)))

(defn put-queen [x y state]
  (assoc-in state [x y] :q))

(defn valid-state? [x y state]
  (and (valid-row? x y state)
       (valid-collum? x y state)
       (valid-diagonal? x y state)))

(defn put-on [x y state]
  (when (valid-state? x y state)
    (put-queen x y state)))

(defn queens
  ([n]
     (->> (queens 0 (new-world n))
          flatten
          (partition n)
          (partition n)))
  ([x state]
     (if (>= x (count state))
       state
       (remove (fn [_] (or (nil? _) (empty? _)))
               (for [y (range (count state))]
                 (when-let [new-state (put-on x y state)]
                   (queens (inc x) new-state)))))))

Short and easy how I like it.

The chess-board is a vector of vector, nothing more classic, and it is build by the function new-world.

put-queen put a queen (:q) in the chess-board, nothing to add.

The function that check if the queen is in a valid position is valid-state? (the help functions are not show, but they are trivial), the function instead of check if any queen in the whole chess-board attack any other queen only check if the position (x, y) is under attack by some queen (or vice-versa), we safe some little computation for interaction but considering the number of total interaction it is worthed.

Consider now just the double argument queens function.

x is the row we are analyzing and y is the collum (just the contrary of the normal xOy plane), all the function is basically just a big cycle but in this way, instead of cycle for every single possibility in the chess board, as soon as I realize that the state is not valid I cut the research.

It is a recursive function so it may be hard to get it very quickly however just try to visualize it in a paper, draw a 4 by 4 chess board and try to follow the algorithm (note that the 4x4 chessboard has not solution, if you want to find a solution by hand try with the 5x5 board).

A problem with this function is that return a very deep nested list (you call a for inside another for up to the number of queens times), I solved it flatten all and the re-assembling (partitioning) the chessboard.

The function is lazy, even if a lot of computation to get the result n is the same that the computation necessary to get the result n+1.