Clojure’s Core Functions and the N-Queens Problem
The classic 8-queens problem is that of placing 8 queens on a chessboard so that no pair is attacking. Franz Nauck in 1850 extended the chess problem to n-queens problem on an n×n board. S. Günther proposed a method of finding solutions by using matrix determinants. Edsger Dijkstra used this problem in 1972 to illustrate the power of what he called structured programming. We will use this classic problem here to illustrate the power of Clojure’s core functional abstractions.
Clojure’s core functional abstractions
In OOP programmers write code that emphasizes the core abstractions of classes and objects. Clojure, in contrast, emphasizes programming to simple abstractions referred to as collections and sequences. All of Clojure’s core data structures — vectors, maps, lists and sets — take part in both abstractions.
The Clojure abstractions differ in that the sequence or seq abstraction is “generically about” operating on members of a collection individually, while the collection abstraction is “generically about” the data structure as a whole. For example, the collection functions count, empty?, and every? are about the whole collection, whereas the seq functions first, rest and cons are about individual items in collection.
Lazy-seqs are almost the same abstraction as seq, but with a substitution of a next function for the rest function associated with a seq. Most of the seq library functions are lazy, i.e. functions that return seqs do so incrementally, as they are consumed, and thus consume any seq arguments incrementally as well. Functions returning lazy seqs can be implemented using the lazy-seq macro. For example, the map function creates a lazy sequence by applying a function to every element in a seqable collection.
It is important to understand the arity of core functions. Clojure allows the definition of variable-arity functions by including a “rest-param” that is indicated with & syntax, and works by putting the rest of the unknown number of arguments in a list with the name following the &.
(defn my-inc-map [& rest-lst] (map inc rest-lst)) (my-inc-map 1 2 3 4) ;=> (2 3 4 5)
cons, into, conj, and apply
- cons takes an item and a seq and returns the seq with the item as first.
- into takes two collections and adds all the elements from the second to the first.
- conj takes a collection and a rest-param and adds the rest elements to build a larger collection (note slight difference with into)
- apply takes a function and an argument and applies the function to args transformed to a rest-parameter.
(cons 0 [1 2 3 4]) ; => [0 1 2 3 4] // a seq (into [0] [1 2 3 4]) ;=> [0 1 2 3 4] (conj [0] 1 2 3 4) ;=> [0 1 2 3 4] // a collection (apply conj [0] [1 2 3 4]) ;=> [0 1 2 3 4]
cons returns a seq and conj returns a collection. conj “adds” the item to the optimal end of the collection, which may be at different locations (depending on the data structure), for example, conj “adds” to the right end of a vector, but the left end of a list; and, note that cons always “adds” the item to the front of a seq.
into allows you to take any collection such as list, vector, map, set, sorted-map, and using an empty or not empty container fill it with the collection.
(into [] '(1 2 3 4)) ;=> [1 2 3 4] "have a lazy list, want a vector"
(into #{} [1 2 3 4]); => #{1 2 3 4} "have a vector, want a set"
(into {} #{[1 2] [3 4]}); => {3 4, 1 2} "have a set of vectors, want a map"
(into #{} [{1 2} {3 4}]);=> #{{1 2} {3 4}} "have a vector of maps, want a set of maps"
apply “explodes” a seqable data structure so that it can be passed to a function which expects a rest-param. For example, conj takes a rest-param making it multi-arity, and so apply conj is basically equivalent to into. Also, if you want to reduce or find the “max” element in a vector, you have to explode it into a rest-param with apply.
(apply max [1 2 3 4]) ;=> 4 (map vector '(1 2 3) '(4 5 6)) ;=> ([1 4] [2 5] [3 6]) (apply map vector '((1 2 3) (4 5 6))) ;=> ([1 4] [2 5] [3 6])
List Comprehension using for-form
List comprehension uses the for-form syntax for generating lists. The for-form takes a vector of one or more binding-form/collection-expr pairs, each followed by zero or more modifiers, and yields a lazy sequence of evaluations of expr.
;a for-expression for generating a list of triples
(for [x (range 6) y (range 5)
:let [z (* x y)]
:when (odd? z)]
(list x y z))
;=> ((1 1 1) (1 3 3) (3 1 3) (3 3 9) (5 1 5) (5 3 15))
:when iterates over the bindings, but only evaluates the body of the loop when the condition is true.
:while iterates over the bindings and evaluates the body until the condition is false:
(for [x (range 20) :when (not= x 10)] x) ; =>(0 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19) (for [x (range 20) :when (>= 50 (rand-int 100))] x) ;=> (1 3 5 6 7 8 10 14 17) ; So for-forms treat collections like collections and seqs like seqs ; and a :while modifier applied to a seq acts nice (for [x (range 20) :while (not= x 10)] x) ; => (0 1 2 3 4 5 6 7 8 9)
We model a chain as a vector of colored beads (ints). Let’s use the conj and the for-form together to recursively generate a list of all chains of n beads with m colors (equivalently, length-n vectors of all numbers mod m):
(defn allchains [n m]
(cond
(= n 1) (map vector (range m))
:else (for [i (range m)
ch (allchains (dec n) m)] (conj ch i))))
(allchains 3 2) ;=> ([0 0 0] [1 0 0] [0 1 0] [1 1 0] [0 0 1] [1 0 1] [0 1 1] [1 1 1])
(allchains 2 3) ;=> ([0 0] [1 0] [2 0] [0 1] [1 1] [2 1] [0 2] [1 2] [2 2])
N-Queens Solution Design
We are now set to code a solution to the n-queens problem. Let us represent solutions using vectors of non-attacking column locations. Here is the representation for the solution image at top above:
[5 3 6 0 7 1 4 2].
So a solution is simply a permutation vector where no pair of numbers differ by the same value as their displacement.
Our goal is to write a generator that produces a collection of all possible solutions to the n-queens problem. Modeled after the allchains function above, we can define a simple recursive generator function called n-queens that will take each solution to n-1 queens problem and use a list comprehension with the results of a which-queen-to-add function (defined below) to compute a list of all possible additions.
(defn n-queens [n m]
(cond
(= n 1) (map vector (range m))
:else (for [psol (n-queens (dec n) m)
q (which-queens-to-add psol m)]
(conj (vec psol) q))))
Which-queens-to-add function
Suppose we are given a partial solution psol and an integer m; that is, psol is a seq of non-attacking queen positions. We generate all column positions less than m that can be added to the psol seq using a list comprehension.
; for each possible column position q return q
; if all other queens in partial-solution psol are non-attacking
; by checking if queen-i and q share same col or diagonal
(defn which-queens-to-add [psol m]
(for [q (range m)
:when (not-any? true?
(for [i (range (count psol)) :let [queen-i (psol i)]]
(or
(= queen-i q)
(= (- (count psol) i) (Math/abs (- q queen-i))))))]
q))
Here are some results:
user=> (count (n-queens 8 8)) 92 user=> (n-queens 8 8) ([0 4 7 5 2 6 1 3] [0 5 7 2 6 3 1 4] [0 6 3 5 7 1 4 2] [0 6 4 7 1 3 5 2] [1 3 5 7 2 0 6 4] [1 4 6 0 2 7 5 3] [1 4 6 3 0 7 5 2] [1 5 0 6 3 7 2 4] [1 5 7 2 0 3 6 4] [1 6 2 5 7 4 0 3] .... )
So there are 92 solutions to the 8-queens problem.
But, you may object: are not some of these solutions the same – or isomorphs – equivalent via symmetries of rotation and reflection of the chess board?
Let’s Reject Isomorphs
Of all the 92 solutions found, which ones can be considered unique, in the sense that no two can be equated via rotating or flipping the board.
There are 8 transformations that map the chess-board to itself; 4 rotations of 90 degrees, and 4 reflections — in math this is called the dihedral group D8 of automorphisms of the square.
Let us consider each solution of N-Queens as a base N+1 number. To obtain a set of unique solutions, we can generate all solutions in numeric order, and then test if a solution is isomorphic to a previously found solution. So if one of the 8 transformations applied to solution, yields an equivalent one which is numerically (or, more generally, lexicographically) less than the original, then it follows that adding it would violate uniqueness, and so we reject it.
There is a clojure.core function compare that can be used to compare vectors. If first arg is less, equal, or greater than the second, then compare returns -1,0,+1, respectively. Thus we can lexicographically compare solutions as follows:
user=> (compare [0 4 7 5 2 6 1 3] [7 1 3 0 6 4 2 5]) -1
Encoding Symmetries
We can model and implement the symmetries obtained by rotation and reflection transformations via a method that expands and collapses each solution vector using a list of [row-index col-index] pairs as intermediate representation.
Let us write a rotate transformation that maps each solutions to the transformed solution given by right-rotation of the board, and reflect that maps solutions to flip of board along the horizontal axis.
(def one (first (n-queens 8 8))
;=> [0 4 7 5 2 6 1 3]
(defn expand [sol] (map vector (range 8) sol) )
(expand one)
;=>([0 0] [1 4] [2 7] [3 5] [4 2] [5 6] [6 1] [7 3])
;Rotating and Reflected Solutions:
;If [i j] is a queen in sol, then [j 7-i] is a queen in (rotate sol)
;If [i j] is a queen in sol, then [i 7-j] is a queen in (reflect sol)
(defn rotate [sol]
(map (fn[x] (let [[i j] x] (vector j (- 7 i)))) sol))
(defn reflect [sol]
(map (fn[x] (let [[i j] x] (vector i (- 7 j)))) sol))
;Expand and Collapse Transformed Solutions
(expand one)
;=>([0 0] [1 4] [2 7] [3 5] [4 2] [5 6] [6 1] [7 3])
(sort (reflect (expand one)))
;=> ([0 7] [1 3] [2 0] [3 2] [4 5] [5 1] [6 6] [7 4])
(sort (rotate (expand one)))
;=> ([0 7] [1 1] [2 3] [3 0] [4 6] [5 4] [6 2] [7 5])
(defn collapse [exp-q] (into [] (map (fn[ij] (last ij)) exp-q)))
(collapse '([0 7] [1 1] [2 3] [3 0] [4 6] [5 4] [6 2] [7 5]))
;=> [7 1 3 0 6 4 2 5]
Every solution has at most 7 isomorphs, obtained by applying all 7 (non-identity) symmetries of the square. These 7 isomorphs can be obtained by joining the 3 rotations and the 4 reflected rotations.
Hence, we write a function all_isos by conjoining these 7 transformations as follows:
(defn all_isos [orig] (let [exp-o (expand orig)] (map collapse (apply conj (take 3 (iterate rotate (rotate exp-o))) (take 4 (iterate rotate (reflect exp-o))))))) (defn any_iso [orig] (some #(= % orig) (all_isos orig))) (count (filter #(= % true) (map any_iso (n-queens 8 8)))) ; => 4 ; So it is the case that 4 solutions to 8-queens problem have non-trivial transformations that fix them. We will call these degenerate. (filter #(any_iso %) (n-queens 8 8)) ;=> ([2 4 1 7 0 6 3 5] [3 5 7 1 6 0 2 4] [4 2 0 6 1 7 5 3] [5 3 6 0 7 1 4 2])
Exercises:
1) What are the transformations of the square that fix each of these solutions.
2) Write another version of all_isos functions possibly using other generating transformations substituting for ‘rotate’ and ‘reflect’. Verify the same transformation fix the degenerate solutions described above.
Orbits, Systems of Representatives, and Degenerate Solutions
A group of transformations acting on a set of objects, in our case solutions to n-queens, partitions the set into orbits. An orbit is simply the equivalence class of objects/solutions given by the transformations. A Degenerate Orbit of Solutions is one in which the orbit of solutions defined by 8 symmetries of the square has fewer than 8 distinct solutions, i.e., some in the collection of symmetries are identical solutions, that is they are ‘fixed’ by at least one non-trivial symmetry. Consider this solution:
Note that 2 successive rotations maps this solution to itself. The image above is the (lex-first) representative for the orbit of solutions, that is the one of least numerical value as a base-8 integer. The orbit of solutions has just 4 distinct configurations: the one above, and the one rotated 90 degrees, the horizontal flip, the diagonal flip (equivalent to rotate then horizontal flip). For the 8-queens problem this is in fact the only orbit of solutions that is degenerate.
Burnsides Lemma and Its Application
Burnside’s Lemma gives a formula that equates the number of orbits (or non-isomorphic classes) to the average number of elements of an underlying set X that are fixed by member of group G of transformations.
So in mathematical notation, for each g in G let Xg denote the set of elements in X that are fixed by g. Burnside’s lemma asserts the following remarkable formula for the total number of distinct orbits, denoted |X/G|:
Recall from the 8-queens puzzle: we have total of 92 solutions in our set X, and the 8-symmetries of the square is the group G called the dihedral group.
We found experimentally that the solution set X divided into 12 classes of orbits. All but one of the orbits were of full and of size 8. There was one degenerate orbit with 4 solutions, hence each of these must have been fixed by one symmetry. To show the application of Burnsides Lemma we have the following calculations over the group elements:
1) the identity transfomation fixes all 92 solutions
2) the rotations of 90o and 270o, rotate and rotate^3 fix no solution, neither does each of the horizontal, vertical, and diagonal flips
3) The rotation of 180o rotate^2 fixes each of the 4 solutions in the degenerate orbit
Hence the sum total number of fixed solutions is 96, and if we divide this by 8, the size of the group, we indeed compute the number of distinct orbits (isomorphism-classes) 12 =96/8.
Exercises
- Write clojure program to produce list of all 12 canonical orbit-representatives (non-isomorphic) solution vectors for the 8-queens problem.
- Experiment with n-queens problem for n>8. Determine the number of orbits and canonical representatives.
Compuzzle 
Discussion
No comments yet.