README.txt

This folder explores the classic "8 queens" or "N queens" problem,
which is to place 8 queens on a chess board (or n queens on an n x n
board) so that none of them can attack any other, in other words, one
per row, one per column, and no two on the same diagonal.

See for example https://en.wikipedia.org/wiki/Eight_queens_puzzle
for a discussion of this problem.

What makes it a classic is that it can be solved by a variety
of approaches, making it a nice illustration of various
search algorithms.

First let's set the problem up.

We could just put any queen on any square. For n=8 there are 64
squares, and so C(64,8) i.e. the number of ways to choose 8
things form 64, which is 64!/((64-8)! * 8!) = 4,426,165,368 ...
but we can thin that down pretty easily.

(By C(n,k) I mean the number of combinations of n things taken
k at a time; see for example https://en.wikipedia.org/wiki/Combination .)

Let's instead put one queen each each row, narrowing the
possibilities.  Then the board can be represented by a list of n
integers from 0 to n-1 indicating which column the queen is in each row

For example, with n = 5 one solution looks like this :

   . * . . .  0      * = queen location ; queen in column 1
   . . . * .  1      . = empty                            3
   * . . . .  2                                           0
   . . * . .  3                                           2
   . . . . *  4 => rows                                   4

   0 1 2 3 4 => columns

So this board position has the representation [1, 3, 0, 2, 4].   

Then the number of boards is the number of permutations,
which for n = 8 is 40,320 ... which is much more accessible.

Using this representation, here are a few of the techniques.

 (1) brute force :
 
     Loop over the n! permutation until we find a solution.

 (2) tree traversal :
 
     Fill in board from left to right, placing a queen only in the
     remaining valid positions, producing a tree which we can
     search using recursive descent.

 (3) gradient descent :

     Start from a random board with one queen per row.
     Measure how far we are from a solution by counting
     the number of pairs of queens which are on the same
     diagonal or row. Consider neighboring boards which
     differ by moving one queen another column, or in
     other words changing one number in our representation.
     Look for a neighbor which is closest to the solution,
     with the lowest number of attacking pairs. Continue
     to move to the best neighbor until either we reach
     a solution, or we get stuck in a local minimum dead end.
     If we get stuck, start over at a different random board.
     (This approach is described at geeksforgeeks.org
      n-queen-problem-local-search-using-hill-climbing-with-random-neighbour )

Files:

    README.txt           this file
    utilities.py         various functions to work with the board representation
    heaps_permute.py     generate all permutations with Heap's Algorithm
    brute_force.py       |
    recursive_descent.py | The three approaches described above.
    gradient_descent.py  |

Note that the gradient descent can't be used to count the total number of
solutions, since it can't exhaustively search the total solution
space. The other two can, at least for smallish values for N.

The size of the search space is roughly N!, so any algorithm that
tries to count the number of solutions is going run into trouble as N
gets larger.

Since there are many possible solutions, and since gradient descent
and similar opimization algorithms work pretty well for this problem,
it is possible to find solutions even for fairly large N.

Possibilities for further work on this code :

 * Add some diagnostics (i.e. print statments) to understand better
   what's going on during these different searches.

 * Add timing and different values of n, to compare how these
   different approaches work for different values of n.

 * Create a visualization of the recursive descent tree,
   to make that algorithm more explicit and easier to imagine.
   Perhaps use graphviz to draw the tree for a small value of N?
   Add a bold line for the successful search path?

 * Create a visualization of the gradient descent, with some
   version of path through multiple positions and the values
   of the "number of attacking pairs". Perhaps turn it into
   a 2D surface by cherry picking some neighbors?

Are we having fun yet?

Jim Mahoney | cs.bennington.college | May 2022 | MIT License