//
you're reading...
Uncategorized

Generators and Orderly Algorithms: The Case of N-Queens

Many will be familiar with the classic 8-queens problem of placing 8 queens on a chessboard so that no pair is attacking. Franz Nauck in 1850 extended the 8-queen chess problem to n-queens problem on an n×n board. In 1874, 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.

N-Queens is a nice example of generator composition. We can write a generator that adds a queen to a new row as long as it is safe. A simple recursive generator function n_queens (implementing a depth-first backtracking search) will call the add_queen generator in order to add a queen to each solution to n-1 queens problem (but on a board of size n-1xn). So n_queens() will take 2 parameters, the number of queens n and width or number of rows of the board.

There is no known closed form solution for the cardinality of n-queens. My laptop found all 14200 solutions to 12-queens problem in around 1/2 minute but struggled several minutes to find 73712 solutions to 13-queens.

Research problem: What is the best method to scale the computation of enumerating n-queens. Here is a link to the world record to date http://queens.inf.tu-dresden.de/

def n_queens(n, width):
    if n == 1:
        for i in range(width):
           yield [i]
    else:
        for sol in n_queens(n-1,width):
            for new in add_queen(sol,width):
                yield sol + [new]

def add_queen(sol,width):
        for new_col in range(width):
            if safe_queen(new_col, sol):
                yield new_col

def safe_queen(new_col, sol):
    for row in range(len(sol)):
        if sol[row] == new_col or 
            abs(sol[row] - new_col) == abs(row - len(sol)):
                return False
    return True

count=0
for sol in n_queens(8, 8):
  #print sol
   count +=1
print count, "solutions to 8-queens

>>> 92 solutions to 8-queens

GENERATING NON-ISOMORPHIC SOLUTIONS AND THE “ISOMORPH REJECTION” PROBLEM

Not all of the 92 solutions found can be considered unique, in the sense that rotating or flipping the board around can result in another solution found in the set. There can been seen to be 8 transformations that map the chess-board to itself, the so-called dihedral group D8 of automorphisms of the square.

To reject isomorphic copies of solutions, we could naively check all transformations (applying each non-identity element of D8) and test weather any transformed solutions were already generated. Unfortunately this method has the drawback that there may be a very large number of non-isomorphic solutions already generated in the set, and we would need to check against everyone. So this method is not practical for combinatorial objects of large cardinality. Idea: what about using a perfect hash.

A solution (suggested by Cull and Pandy) is to consider each solution of N-Queens as a base N+1 number. We can generate solutions in numeric order, and test if a solution is isomorphic to a previously found solution if and only if one of the 8 transformations produces a solution, which is numerically (or, more generally, lexicographically) less than the original.

Let R represent the transformation of rotation by 90 degrees, and let M represent mirror reflection, we see that all 7 (non-identity) isomorphisms of the square are given by prefixes of RRRMRRR. Here is a python function to test whether a newly generated solution (original) has been previously generated as an isomorphic copy. If we add this check, we find there exist only 12 representative, non-isomorphic solutions to 8-queens problem.

def check_if_isomorph(original):
    trans = original
    flag = False
    for t in range(7):
        if t != 3:
           trans = rotate(trans)
        else:
           trans = mirror(trans)
        if trans < original:
            return True
    return False

Exercise: Write python functions for ‘rotate()’ and ‘mirror()’.

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:

degenerate
Note that 2 successive rotations (R-squared) maps this solution to itself. The image above is the (lex-first) representative for the orbit of solutions. The orbit of solutions has just 4 distinct configurations: the one above S, R(S) rotated 90 degrees, the horizontal flip H(S), the diagonal flip of D(S)=HR(S) (equivalent to rotate then horizontal flip). For the 8-queens problem this is in fact the only orbit of solutions that is degenerate.

Python Technicalities: It is often useful to determine a system of representatives (that is one representative from each orbit) and use them as a a set of keys in a Python dictionary to store all the orbit-classes. Here we use (minimum or lex-first) representatives (as above). If a generated solution is not minimum, then we simply append it to list associated with the representative minimum. Since lists are not hashable in python, we must convert it to a tuple before adding it as a key.

isosets={}
for sol in n_queens(n, n):
  minsol = min_isomorph(sol)
  if minsol == sol:
     isosets[tuple(sol)]=[]
  else:
     isosets[tuple(minsol)].append(tuple(sol))

print len(isosets), "non-iso solutions to",n,"-queens"
for i in isosets:
  print i, len(isosets[i])+1
  if len(isosets[i]) < 7:
    print "Degenerate solution"

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 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|:

 formula1

Recall from the 8-queens puzzle: we have 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,  R and R^3 fix no solution, neither does each of the horizontal, vertical, and diagonal flips

3) The rotation of 180o R-squared 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.

Eliminating the Dictionary: “Every One A Winner”

Let us return to the problem of only generating non-isomorphic solutions to the 8-queens problem. We saw that we could identify canonical representatives by interpreting solutions as numeric values and storing them in a dictionary. We build on that notion here to show that sometimes we can eliminate the need for the dictionary itself.

In 1978 RC Read published a general technique he called the “orderly algorithm” useful for generating non-isomorphic combinatorial objects. The method applies to many settings including n-queens, graphs, digraphs, tree, tournaments, etc.

The method adapts the ‘classical method’ for generating a listing L(q) of objects with a parameter q, based on recursive procedure applied to L(q-1). For example, the method allows one to generate all graphs with q+1 edges from graphs on q edges.

We now describe 3 definitions that are key to adapting the classical method to achieve an “orderly algorthm” for combinatorial objects. First, we have a  “canonicity definition”, which is simply a method to pick out from each orbit a distinct representative. Often times we will use numeric or lex-first orderings to define canonical configurations. We also need a definition of a list order < over all objects under consideration, and here too we can often use numeric ordering.

Orderly Algorithm:

1)   Start with a list of canonical configurations for L(q) arranged in list order according to <. Initialize L(q+1) to empty.

2)   Take each configuration of L(q), in order, and augment it to generate a sequence S(q+1). To each such configuration apply the following rule: If the configuration is canonical, and it comes after the last element present in L(q+1), then add it to L(q+1); otherwise ignore it.

3) When every element of L(q) is acted on in this way, then we have completed L(q+1).

 

Conditions for correctness:

1)   Coverage: each canonical configuration in S(q) must be produced from augmentation from at least one canonical configuration in S(q+1).

2)   Monotonicity: if X,Y in L(q+1), with X<Y, then first config of  L(q) that can produce X must be less that first config of L(q) that produces Y.

3)   Proper Order: the configurations produced by augmentation are in list order.

THEOREM: If the definitions of canonicity, list order, and augmentation satisfy conditions 1,2, and 3 above, then the Orderly Algorithm is effective.

Example: Generating Digraphs using the Orderly Algorithm

Let S be labeled digraphs on 5 nodes. We want to show how to generate all non-isomorphic digraphs with q+1 edges, given those on q edges.

Canonicity: we interpret the adjacency matrix as a binary integer on 20 bits (ignore diagonal entries). Define the canonical configuration to be the largest. Define the list order to be decreasing from largest to smallest. The augmentation operation is defined as changing a 0 to 1 in adjacency matrix.

Exercise: Show these definitions satisfy conditions of Theorem 1.

Advertisements

Discussion

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: