Comparison of algorithmic approaches to the N queens problem

Question

I wanted to evaluate performance comparisons for various approaches to solving the N queens problem. Mainly AI metaheuristics based algorithms like simulated annealing, tabu search and genetic algorithm etc compared to exact methods(like backtracking). Is there any code available for study? A lot of real-world optimization problems like it consider cooperative schemes between exact methods and metaheuristics.

Answer 1

I had to write an n-queens solver in Java for a class a couple years ago in college. I'm not sure what type of source code you are looking for, but if it would be of any help here's the code from that program. It's not really optimized in any way, just a pretty simple recursive algorithm. I wrote this my first semester of college, so excuse the beginner mistakes:-) I took most of the block comments out, but hopefully you can make sense of it with the ones that I left in. If you want some professional source code than maybe do a Google search? I know that Wikipedia had some decent articles and pseudo-code. Hope this helps!

import java.util.Scanner;
public class QueensSolver 
{
public static void main(String args[])
{
 System.out.println("Please enter the size of the chessboard: ");
 Scanner stdin = new Scanner(System.in);
 int sizeOfBoard = stdin.nextInt();
 //Create the board to the given size.
 char[][] board = new char[sizeOfBoard][sizeOfBoard];

 //fill board with hyphens
 for(int row=0; row<sizeOfBoard; row++)
 {
  for(int col=0; col<sizeOfBoard; col++)
  {
   board[row][col] = '-';
  }
 }

 //Call the method which attempts to solve the problem
 if(solve(sizeOfBoard, board, 0))
 { //if true, we know that the board array contains a solution
  printBoard(sizeOfBoard, board);
 }
 else
 { //if false, we know that no solutions exist on this size of board
  System.out.println("No solutions are possible with this board size.");
 }
}

public static boolean solve(int sizeOfBoard, char[][] board, int row)
{
 //If all rows have been filled, we have a solution
 if(row>=sizeOfBoard)
 {
  return true;
 }
 //For each column(space) on the given row
 for(int col=0; col<sizeOfBoard; col++)
 {
  //If placing a queen in this column(space) does not cause a conflict
  if(!checkConflict(sizeOfBoard, board, row, col))
  {
   //place a queen here
   board[row][col]='Q';
   //then call this same function on the next row
   boolean success = solve(sizeOfBoard, board, row+1);
   //if every function in this recursive path returns true
   if(success)
   {
    //then we return true also
    return true;
   }
   //If there is no possible solution with this queen placement,
   //then we replace the queen with an empty and attempt
   //to place a queen in the next column(space).
   else
   {
    board[row][col]='-';
   }
  }
 }
 return false;
}

public static boolean checkConflict(int sizeOfBoard, char[][] board, int rowCheck, int colCheck)
{
 //Check for queens placed directly above this position
 for(int row = rowCheck-1; row>=0; row--)
 {
  if(board[row][colCheck]=='Q')
  {
   return true;
  }
 }

 //Check for queens placed on the diagonal 
 //above and to the right of this position
 int col = colCheck+1;
 for(int row = rowCheck-1; row>=0; row--)
 {

  if(col>=sizeOfBoard)
  {
   break;
  }
  if(board[row][col]=='Q')
  {
   return true;
  }
  col++;
 }

 //Check for queens placed on the diagonal 
 //above and to the left of this position
 col = colCheck-1;
 for(int row = rowCheck-1; row>=0; row--)
 {

  if(col<0)
  {
   break;
  }

  if(board[row][col]=='Q')
  {
   return true;
  }
  col--;
 }
 //We know that no conflicts are caused by this position, so return false
 return false;
}

public static void printBoard(int sizeOfBoard, char[][] board)
{
 for(int row=0; row<sizeOfBoard; row++)
 {
  for(int col=0; col<sizeOfBoard; col++)
  {
   System.out.print(board[row][col]);
  }
  System.out.print("\n");
 }
}
}

Answer 2

I don't really get your question (do you want to know the theory of th ealgorithm? do you want to see code?), but I am willing to share code I adapted from the wild. It's python and it's pretty cool. I changed it to use iterators and, miraculously, it still works.

# I can't really claim much credit for this implementation.
# I found this on the web and I converted it to use python generators.
# Adapted from:
#     http://en.wikibooks.org/wiki/Algorithm_implementation/Miscellaneous/N-Queens

def queensproblem(solution, rows, columns):
    def add_one_queen(new_row, columns, solution):
        for new_column in range(columns):
            if not conflict(new_row, new_column, solution):
                yield new_column

    def conflict(new_row, new_column, solution):
        return any(solution[row]       == new_column or
                   solution[row] + row == new_column + new_row or
                   solution[row] - row == new_column - new_row
                   for row in range(new_row))

    if len(solution) == rows:
        yield solution
    else :
        for row in range(len(solution), rows):
            for col in add_one_queen(row, columns, solution):
                for x in queensproblem(solution + [col], rows, columns):
                    yield x
            else:
                break

if __name__ == '__main__':
    for i,solution in enumerate(queensproblem([], 8, 8)):
        print i, solution

Answer 3

A nice approach exists in the file test/test_generators.py of the Python standard library. Check the Queens class.

If you don't have Python installed in your computer, you can browse the file online here.

Answer 4

The Drools solver could be interesting for you. Especially chapter 1 of the documentation.

Answer 5

This isn't the fastest scheme implementation possible, but it's pretty concise. I did come up with it independently, but I doubt it's unique. It's in PLT Scheme, so some function names need to be changed to get it running in R6RS. The list of solutions and each solution are built with cons, so they're reversed. The reverses and maps at the end reorder everything and add rows to the solutions for a pretty output. Most languages have a fold type function, see:
http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29

#lang scheme/base
(define (N-Queens N)  

  (define (attacks? delta-row column solution)
    (and (not (null? solution))
         (or (= delta-row (abs (- column (car solution))))
             (attacks? (add1 delta-row) column (cdr solution)))))  

  (define (next-queen safe-columns solution solutions)
    (if (null? safe-columns)
        (cons solution solutions)
        (let move-queen ((columns safe-columns) (new-solutions solutions))
          (if (null? columns) new-solutions
              (move-queen
                (cdr columns)
                (if (attacks? 1 (car columns) solution) new-solutions
                    (next-queen (remq (car columns) safe-columns)  
                                (cons (car columns) solution)  
                                new-solutions)))))))

  (unless (exact-positive-integer? N)
    (raise-type-error 'N-Queens "exact-positive-integer" N))
  (let ((rows (build-list N (λ (row) (add1 row)))))
    (reverse (map (λ (columns) (map cons rows (reverse columns)))
                  (next-queen (build-list N (λ (i) (add1 i))) null null)))))