LogicGrowsOnTrees.Examples.Queens.Advanced

This module contains a heavily optimized solver for the n-queens problems. Specifically, it uses the following tricks:

• symmetry breaking to prune redundant solutions
• unpacked datatypes instead of multiple arguments
• optimized getOpenings
• C code for the inner-most loop
• INLINEs in many places in order to create optimized specializations of the generic functions

Benchmarks were used to determine that all of these tricks resulted in performance improvements using GHC 7.4.3.

Types

data NQueensSymmetry

The possible board symmetries.

Constructors

NoSymmetries

the board has no symmetries at all

Rotate180Only

the board is symmetric under 180 degree rotations

AllRotations

the board is symmetric under all rotations

AllSymmetries

the board is symmetric under all rotations and reflections

Instances

Eq NQueensSymmetry

Ord NQueensSymmetry

Read NQueensSymmetry

Show NQueensSymmetry

type NQueensSolution = [(Word, Word)]

Type alias for a solution, which takes the form of a list of coordinates.

type NQueensSolutions = [NQueensSolution]

Type alias for a list of solutions.

data PositionAndBit

Represents a position and bit at that position.

data PositionAndBitWithReflection

Like PositionAndBit, but also including the same for the reflection of the position (i.e., one less than the board size minus the position).

Main algorithm

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.

Symmetry breaking

A performance gain can be obtained by factoring out symmetries because if, say, a solution has rotational symmetry, then that means that there are four configurations that are equivalent, and so we would ideally like to prune three of these four equivalent solutions.

I call the approach used here symmetry breaking. The idea is we start with a perfectly symmetrical board (as it has nothing on it) and then we work our way from the outside in. We shall use the term layer to refer to a set of board positions that form a centered (hollow) square on the board, so the outermost layer is the set of all positions at the boundary of the board, the next layer in is the square just nested in the outermost layer, and so in. At each step we either preserve a given symmetry for the current layer or we break it; in the former case we stay within the current routine to try to break it in the next layer in, in the latter case we jump to a routine designed to break the new symmetry in the next layer in. When all symmetries have been broken, we jump to the brute-force search code. If we place all of the queens while having preserved one or more symmetries, then either we apply the rotations and reflections of the symmetry to generate all of the solutions or we multiply the solution count by the number of equivalent solutions.

This code is unforunately quite complicated because there are many possibilities for how to break or not break the symmetries and at each step it has to place between 0 and 4 queens in such a way as to not conflict with any queen that has already been placed.

Each function takes callbacks for each symmetry rather than directly calling nqueensBreak90, etc. in order to ease testing.

nqueensStart

Arguments

:: MonadPlus m

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

function that adds a list of coordinates to the partial solutions

-> (α -> NQueensBreak90State -> m β)

function to break the rotational symmetry for the next inner layer

-> (α -> NQueensBreak180State -> m β)

function to break the 180-degree rotational symmetry for the next inner layer

-> (α -> Int -> NQueensSearchState -> m β)

function to apply a brute-force search

-> α

partial solution

-> Word

board size

-> m β

the final result

Break the reflection symmetry.

data NQueensBreak90State

The state type while the 90-degree rotational symmetry is being broken.

Constructors

NQueensBreak90State

Fields

b90_number_of_queens_remaining :: !Word

b90_window_start :: !Int

b90_window_size :: !Int

b90_occupied_rows_and_columns :: !Word64

b90_occupied_negative_diagonals :: !Word64

b90_occupied_positive_diagonals :: !Word64

nqueensBreak90

Arguments

:: MonadPlus m

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

function that adds a list of coordinates to the partial solutions

-> (α -> m β)

function that finalizes the partial solution

-> (α -> NQueensBreak90State -> m β)

function to break the rotational symmetry for the next inner layer

-> (α -> NQueensBreak180State -> m β)

function to break the 180-degree rotational symmetry for the next inner layer

-> (α -> Int -> NQueensSearchState -> m β)

function to apply a brute-force search

-> α

partial solution

-> NQueensBreak90State

current state

-> m β

the final result

Break the 90-degree rotational symmetry at the current layer.

data NQueensBreak180State

The state while the 180-degree rotational symmetry is being broken.

Constructors

NQueensBreak180State

Fields

b180_number_of_queens_remaining :: !Word

b180_window_start :: !Int

b180_window_size :: !Int

b180_occupied_rows :: !Word64

b180_occupied_columns :: !Word64

b180_occupied_negative_diagonals :: !Word64

b180_occupied_positive_diagonals :: !Word64

b180_occupied_right_positive_diagonals :: !Word64

nqueensBreak180

Arguments

:: MonadPlus m

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

function that adds a list of coordinates to the partial solutions

-> (α -> m β)

function that finalizes the partial solution

-> (α -> NQueensBreak180State -> m β)

function to break the 180-degree rotational symmetry for the next inner layer

-> (α -> Int -> NQueensSearchState -> m β)

function to apply a brute-force search

-> α

partial solution

-> NQueensBreak180State

current state

-> m β

the final result

Break the 180-degree rotational symmetry at the current layer.

Brute-force search

After the symmetry has been fully broken, the brute-force approach attempts to place queens in the remaining inner sub-board. When the number of queens falls to 10 or less, it farms the rest of the search out to a routine written in C.

data NQueensSearchState

The state during the brute-force search.

Constructors

NQueensSearchState

Fields

s_number_of_queens_remaining :: !Word

s_row :: !Int

s_occupied_rows :: !Word64

s_occupied_columns :: !Word64

s_occupied_negative_diagonals :: !Word64

s_occupied_positive_diagonals :: !Word64

nqueensSearch

Arguments

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

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

function that adds a list of coordinates to the partial solutions

-> (α -> m β)

function that finalizes the partial solution

-> α

partial solution

-> Int

board size

-> NQueensSearchState

current state

-> m β

the final result

Using brute-force to find placements for all of the remaining queens.

nqueensBruteForceGeneric

Arguments

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

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

function that adds a list of coordinates to the partial solutions

-> (α -> m β)

function that finalizes the partial solution

-> α

initial solution

-> Word

board size

-> m β

the final result

Interface for directly using the brute-force search approach

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

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

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

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

C inner-loop

c_LogicGrowsOnTrees_Queens_count_solutions

Arguments

:: CUInt

board size

-> CUInt

number of queens remaining

-> CUInt

row number

-> Word64

occupied rows

-> Word64

occupied columns

-> Word64

occupied negative diagonals

-> Word64

occupied positive diagonals

-> FunPtr (CUInt -> CUInt -> IO ())

function to push a coordinate on the partial solution; may be NULL ^

-> FunPtr (IO ())

function to pop a coordinate from partial solution; may be NULL ^

-> FunPtr (IO ())

function to finalize a solution; may be NULL ^

-> IO CUInt

C code that performs a brute-force search for the remaining queens. The last three arguments are allowed to be NULL, in which case they are ignored and only the count is returned.

mkPushValue :: (CUInt -> CUInt -> IO ()) -> IO (FunPtr (CUInt -> CUInt -> IO ()))

wrapper stub for the push value function pointer

mkPopValue :: IO () -> IO (FunPtr (IO ()))

wrapper stub for the pop value function pointer

mkFinalizeValue :: IO () -> IO (FunPtr (IO ()))

wrapper stub for the finalize value function pointer

nqueensCSearch

Arguments

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

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

function that adds a list of coordinates to the partial solutions

-> (α -> m β)

function that finalizes the partial solution

-> α

partial solution

-> Int

board size

-> Int

window start

-> NQueensSearchState

current state

-> m β

the final result

Calls C code to perform a brute-force search for the remaining queens. The types α and β must be Typeable because this function actually optimizes for the case where only counting is being done by providing null values for the function pointer inputs.

nqueensCGeneric

Arguments

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

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

function that adds a list of coordinates to the partial solutions

-> (α -> m β)

function that finalizes the partial solution

-> α

initial value

-> Word

the board size

-> m β

the final result

Interface for directly using the C search approach

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

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

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

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

Helper functions

allRotationsAndReflectionsOf

Arguments

:: Word

board size

-> NQueensSolution

given solution

-> NQueensSolutions

all rotations and reflections of the given solution

Computes all rotations and reflections of the given solution.

allRotationsOf

Arguments

:: Word

board size

-> NQueensSolution

given solution

-> NQueensSolutions

all rotations of the given solution

Computes all rotations of the given solution.

convertSolutionToWord :: [(Int, Int)] -> [(Word, Word)]

Converts coordinates of type Int to type Word.

extractExteriorFromSolution

Arguments

:: Word

board size

-> Word

number of outer layers to extract

-> NQueensSolution

given solution

-> NQueensSolution

the outermost layers of the solution

Extracts the outermost layers of a solution.

getOpenings

Arguments

:: MonadPlus m

=> Int

board size

-> Word64

occupied positions

-> m PositionAndBit

open positions and their corresponding bits

Get the openings for a queen

getSymmetricOpenings

Arguments

:: MonadPlus m

=> Int

board size

-> Word64

occupied positions

-> m PositionAndBitWithReflection

open positions and their corresponding bits and reflections

Get the symmetric openings for a queen

hasReflectionSymmetry

Arguments

:: Word

board size

-> NQueensSolution

given solution

-> Bool

true if the given solution has reflection symmetry

Checks if a solution has reflection symmetry.

hasRotate90Symmetry

Arguments

:: Word

board size

-> NQueensSolution

given solution

-> Bool

true if the given solution has 90-degree rotation symmetry

Checks if a solution has 90-degree rotation symmetry.

hasRotate180Symmetry

Arguments

:: Word

board size

-> NQueensSolution

given solution

-> Bool

true if the given solution has 180-degree rotation symmetry

Checks if a solution has 180-degree rotation symmetry.

multiplicityForSymmetry :: NQueensSymmetry -> Word

Returns the number of equivalent solutions for a solution with a given symmetry.

multiplySolution

Arguments

:: MonadPlus m

=> Word

board size

-> NQueensSymmetry

the symmetry of the solution

-> NQueensSolution

a solution with the given symmetry

-> m NQueensSolution

the equivalent solutions of the given solution

Gets all of the equivalent solutions with an equivalent symmetry.

reflectBits :: Word64 -> Word64

Reflects the bits in a number so that each bit at position i is moved to position -i (i.e., what you get when you take a bit at position 0 and rotate it i positions to the right)

reflectSolution

Arguments

:: Word

board size

-> NQueensSolution

given solution

-> NQueensSolution

the solution with its columns reflected

Reflects the columns of a solution

rotate180

Arguments

:: Word

board size

-> NQueensSolution

given solution

-> NQueensSolution

the given solution rotated by 180 degrees

Rotate a solution left by 180 degrees.

rotateLeft

Arguments

:: Word

board size

-> NQueensSolution

given solution

-> NQueensSolution

the given solution rotated left by 90 degrees

Rotate a solution left by 90 degrees.

rotateRight

Arguments

:: Word

board size

-> NQueensSolution

given solution

-> NQueensSolution

the given solution rotated right by 90 degrees

Rotate a solution right by 90 degrees.

symmetryOf

Arguments

:: Word

board size

-> NQueensSolution

given solution

-> NQueensSymmetry

the symmetry of the given solution

Computes the symmetry class of the given solution