The n Queen Problem

Problem Description

This problem is described in Excercise 2.6.6 in [2].

Program Descriptions

  • q.m
    This MATLAB program gives the best found placement for n queens on an n x n chessboard using the FACE algorithm.

    Usage:
    Call the program from MATLAB, with the following syntax:

    B = q( Ne , Nmin , Nmax , alpha , d , c , n )

    Example: board = q( 15 , 300 , 2000 , 0.7 , 10 , 5 , 8 )

    Inputs:   
     Ne - Number of elite samples to use
     Nmin - Minimum number of samples to use (must be >= Ne)
     Nmax - Maximum number of samples to use (must be >= Ne)
     alpha - Smoothing Parameter
     d - number of S_t^* the same in a row with no gamma_t_hat improvement
     c - number of N_t = Nmax in a row
     n - n queens on an nxn board
    Outputs:   
     B - An n x n matrix with queens denoted by 1s, and blank squares denoted by 0s
  • genq.m
    This program is used internally to generate chessboard outcomes.

  • scoreq.m
    This program is used internally to evaluate the performance of a particular board.

  • wq.m
    This program takes in a set of exact solutions to the 8x8 queen problem, and then tells you which of the 12 unique (disregarding reflections and rotations) solutions you have found. The exact solutions were found in [1].

    Usage:
    Call the program from MATLAB, with the following syntax:

    v =wq( U )

    Inputs:   
     U - An 8 x 8 x k matrix of exact solutions
    Outputs:   
     v - A vector of length k, labelling the solutions found

Bibliography

  1. V. Chvatal.
    All solutions to the problem of eight queens.
    http://www.cs.rutgers.edu/~chvatal/8queens.html
  2. .
  3. D. P. Kroese and R. Y. Rubinstein.
    The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning.
    Springer, 2004.