LogicGrowsOnTrees.Examples.Queens

This module contains examples of logic programs that generate solutions to the n-queens problem, which is the problem of finding ways to put n queens on an n x n chessboard in such a way that they do not conflict. Solutions of the n-queens problem take the form of a list of n coordinates such that no coordinates have overlapping rows, columns, or diagonals (as these are the directions in which a queen can attack).

Correct solution counts

nqueens_correct_counts :: IntMap Word

A table with the correct number of solutions for board sizes ranging from 1 to nqueens_maximum_size.

This data was pulled from http://queens.inf.tu-dresden.de/?n=f&l=en.

nqueens_maximum_size :: Int

The maximum board size in nqueens_correct_counts. In a 64-bit environment this value is equal to the largest board size for which we know the number of solutions, which is 26. In a 32-bit environment this value is equal to the largest board size such that the number of solutions fits within a 32-bit (unsigned) integer (i.e., the range of Word), which is 18.

nqueensCorrectCount :: Word -> Word

A partial function that returns the number of solutions for the given input board size; this should only be used when you are sure that the input is not greater than nqueens_maximum_size.

Basic examples

The two examples in this section are pretty basic in that they do not make use of the many optimizations that are available (at the cost of code complexity). The first example uses set operations, and the second uses bitwise operations.

Using sets

The functions in this subsection use IntSets to keep track of which columns and diagonals are occupied by queens. (It is not necessarily to keep track of occupied rows because the rows are filled consecutively.)

nqueensUsingSetsSolutions :: MonadPlus m => Word -> m NQueensSolution

Generate solutions to the n-queens problem using IntSets.

nqueensUsingSetsCount :: MonadPlus m => Word -> m WordSum

Generates the solution count to the n-queens problem with the given board size; you need to sum over all these counts to obtain the total, which is done by the exploreTree (and related) functions.

Using bits

nqueensUsingBitsSolutions :: MonadPlus m => Word -> m NQueensSolution

Generate solutions to the n-queens problem using bitwise-operations.

nqueensUsingBitsCount :: MonadPlus m => Word -> m WordSum

Generates the solution count to the n-queens problem with the given board size; you need to sum over all these counts to obtain the total, which is done by the exploreTree (and related) functions.

Advanced example

The advanced example use several techniques to try and squeeze out as much performance as possible using the functionality of this package. The functions listed here are just the interface to it; for the implementation driving these functions, see the LogicGrowsOnTrees.Examples.Queens.Advanced module.

nqueensGeneric

Arguments

:: (MonadPlus m, Typeable α, Typeable β)

=> ([(Word, Word)] -> α -> α)

function that adds a list of coordinates to the partial solution

-> (Word -> NQueensSymmetry -> α -> m β)

function that finalizes a partial solution with the given board size and symmetry

-> α

initial partial solution

-> Word

board size

-> m β

the final result

Interface to the main algorithm; note that α and β need to be Typeable because of an optimization used in the C part of the code. This function takes functions for its first two operators that operate on partial solutions so that the same algorithm can be used both for generating solutions and counting them; the advantage of this approach is that it is much easier to find problems in the generated solution than it is in their count, so we can test it by looking for problems in the generated solutions, and when we are assured that it works we can trust it to obtain the correct counts.

nqueensSolutions :: MonadPlus m => Word -> m NQueensSolution

Generates the solutions to the n-queens problem with the given board size.

nqueensCount :: MonadPlus m => Word -> m WordSum

Generates the solution count to the n-queens problem with the given board size; you need to sum over all these counts to obtain the total, which is done by the exploreTree (and related) functions.

With a list at the bottom (instead of C)

nqueensWithListAtBottomGeneric

Arguments

:: (MonadPlus m, Typeable α, Typeable β)

=> ([(Word, Word)] -> α -> α)

function that adds a list of coordinates to the partial solution

-> (Word -> NQueensSymmetry -> α -> m β)

function that finalizes a partial solution with the given board size and symmetry

-> α

initial partial solution

-> Word

board size

-> m β

the final result

nqueensWithListAtBottomSolutions :: MonadPlus m => Word -> m NQueensSolution

Like nqueensSolutions, but uses List at the bottom instead of C.

nqueensWithListAtBottomCount :: MonadPlus m => Word -> m WordSum

Like nqueensCount, but uses List at the bottom instead of C.

With nothing at the bottom (instead of C or a List)

nqueensWithNothingAtBottomGeneric

Arguments

:: MonadPlus m

=> ([(Word, Word)] -> α -> α)

function that adds a list of coordinates to the partial solution

-> (Word -> NQueensSymmetry -> α -> m β)

function that finalizes a partial solution with the given board size and symmetry

-> α

initial partial solution

-> Word

board size

-> m β

the final result

nqueensWithNothingAtBottomSolutions :: MonadPlus m => Word -> m NQueensSolution

Like nqueensSolutions, but uses List at the bottom instead of C.

nqueensWithNothingAtBottomCount :: MonadPlus m => Word -> m WordSum

Like nqueensCount, but uses List at the bottom instead of C.

Board size command argument

newtype BoardSize

This newtype wrapper is used to provide an ArgVal instance that ensure that an input board size is between 1 and nqueens_maximum_size. In general you do not need to use this type directly but instead can use the function makeBoardSizeTermAtPosition.

Constructors

BoardSize

Fields

getBoardSize :: Word

Instances

ArgVal BoardSize

ArgVal (Maybe BoardSize)

makeBoardSizeTermAtPosition

Arguments

:: Int

the position in the commonand line arguments where this argument is expected

-> Term Word

This constructs a term for the cmdtheline command line parser that expects a valid board size (i.e., a number between 1 and nqueens_maximum_size) at the given positional argument.