8 queens puzzle in Haskell

# Intro

The eight queens puzzle is a famous one.
the goal is to place 8 queens on a chess board, so that no queen can attack another.

In this post we'll see how to design a program in haskell that lists all the solutions.
We will try to build a concise, yet readable code.

# Queen

# Data representation

We won't use complex data representation to build the solver;
in fact, we won't even use the data keyword.
A queen will be represented as a tuple of Int's

type Queen = (Int,Int)

where each Int is one of the coordinate on the board. We don't need to bother with kowing which is the row or the column, because in our case we don't care about symmetry nor rotation.

# Game logic

Now we have to be able to know, given two queens, if they are threatening each other or not.
Let's create a function attacks for that purpose:

attacks :: Queen -> Queen -> Bool
attacks (ax,ay) (bx,by) = undefined

where (ax,ay) is the first queen's position, and (bx,by) the second's.

A queen can attack horizontally, vertically, and diagonnally:

+---------------+
|· · × · · · × ·|
|· · × · · × · ·|
|× · × · × · · ·|
|· × × × · · · ·|
|× × Q × × × × ×|
|· × × × · · · ·|
|× · × · × · · ·|
|· · × · · × · ·|
+---------------+

Checking if two queens are on the same column or row is trivial:

attacks :: Queen -> Queen -> Bool
attacks (ax,ay) (bx,by) = ax == bx || ay == by

Now to test the diagonals, it's not difficult, consider this:
a diagonal corresponds to a deplacement of the same amount of units horizontally and vertically.
If you move by 4 units to the left or right, you have to move by 4 units up or down to be located on the diagonal of your previous location:

+---------------+
|· · · · · · · ·|
|# · · · · · # ·|
|↑ · · · · · ↑ ·|
|↑ · · · · · ↑ ·|
|← ← ← Q → → → ·|
|↓ · · · · · ↓ ·|
|↓ · · · · · ↓ ·|
|# · · · · · # ·|
+---------------+

To put it more rigorously, the horizontal distance between the two queens must be the same as the vertical one

So we'll be substracting x coordinates of the two queens, taking the absolute value of the result, do the same with the y coordinate, and compare the two:

# the two queens' location
#    (x,y)
q1 = (2,4)
q2 = (5,1)

# doing the math

δx = |2-5| = |-3| = 3

δy = |4-1| = |3|  = 3




# comparing the two results
δx == δy #=> the queens are on the same diagonal

  0 1 2 3 4 5 6 7
 +---------------+
0|· · · · · · · ·|
1|· · · · · 2 · ·|
2|· · · · × · · ·|
3|· · · × · · · ·|
4|· · 1 · · · · ·|
5|· · · · · · · ·|
6|· · · · · · · ·|
7|· · · · · · · ·|
 +---------------+

Let's add that to our function:

attacks :: Queen -> Queen -> Bool
attacks (ax,ay) (bx,by) = ax == bx
                       || ay == by
                       || abs (ax - bx) == abs (ay - by)

# Board

# Data representation

What we will call a Board will in fact just be a list of queens (ie a list of (x,y) coordinates):

type Board = [Queen]

so a Board containing only one queen at (3,2) would be represented as [(3,2)] . A board with height queens could be represented as:

[(7,0), (6,1), (5,2), (4,3), (3,4), (2,5), (1,6), (0,7)]

# Game logic

We want a function that can tell us if putting a Queen at a given position on a given Board is legal:

legal :: Queen -> Board -> Bool

This will be the case if the newly added Queen does not threaten any of the Queens that are already there.

In haskell-ish terms, we could say:
not any of the Board (the list of Queens) is attacked by the Queen

with not and any defined in the Prelude:

λ> :t not
not :: Bool -> Bool

λ> :t any
any :: Foldable t => (a -> Bool) -> t a -> Bool

not just returns the negation of a boolean value (not False == True and not True == False)

any takes:

and returns True if the function f returned True for at least one of the elements in the list:

λ> map (>9000) [15, 560, 17860, 10]
[False,False,True,False]

λ> any (>9000) [15, 560, 17860, 10]
True

So we can define our legal function like this:

legal :: Queen -> Board -> Bool
legal queen board = not . any (queen `attacks`) $ board

(Note the infix notation with the `backticks` to make the expression more readable)

But let's fancy this up a bit (point-free powa):

first we introduce none:

none f l = not . any f $ l

-- the "l" variable is already removable
none f = not . any f

-- prefix notation
none f = (.) not (any f)

-- use of '$' instead of parentheses
none f = (.) not $ any f

-- regrouping (.) and 'not' allows us to move the 'f' further to the end...
none f = (not.) . any $ f 

-- and to get rid of it:
none = (not.) . any

You can of course use the definition that seems the best to read to your eyes.
For more informations about point-free

I have a thing for the Point-free notations, because I feel they show the essence of functional programming:
what really matters is how we transform the data,
the data itself being mentionned only when we'll actually use our functions.

Let's now rewrite our legal function:

legal :: Queen -> Board -> Bool
legal queen board = none (attacks queen) $ board

-- the board variable can be removed
legal queen = none (attacks queen)

-- cleanly separating 'queen':
legal queen = none $ attacks queen
legal queen = none . attacks $ queen

-- and finally:

legal = none . attacks

And this definition of being legal expressed as none . attacks is really satisfactory, isn't it?

# board printing in console

I'll add a function to display a given Board in the console:

Each solution will consist of a Board with height Queens, each being on a different line by definition (otherwise they'd be attacking each other), so for each Queen on the Board we draw a row, consisting of '·', except for the position of the Queen where we'll put a 'Q':

for example (not a solution):

+---------------+
|· · · · · Q · ·|
|· · · Q · · · ·|
|· · · · · · Q ·|
|· · Q · · · · ·|
|· · Q · · · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · · · · · Q|
+---------------+

Here is the function:

dispBoard = (sep++) . (++sep) . unlines . map dispQ
  where dispQ (_,k) = ('|':) . (++"|") . intersperse ' '
                      $ r k ++ 'Q' : r (7-k)
          where r = flip take $ repeat '·'
        sep = "+---------------+\n"

There is nothing really special going on, so I won't comment it.

# Solving the puzzle

# Strategy

We will begin with an empty Board, and progressively add the queens.

Each step corresponds to a new line.

We have the "current Board" as a parameter, and we try to add a new Queen to it, on an unoccupied line.

If we have height Queens already, we can't add another one, and we don't want to because the currend Board is a solution of the puzzle.

Otherwise, we try every position on the line (column 0 to 7),
we filter out the non-legal positions, and for each of these new boards, we try to add a new queen recursively.

At the end we want to get a list of the solution Boards we found.

# Implementation

We will define a solve function:

solve :: [Board]

it's a function that takes no argument (technically it's then a value), and returns the list of Board we want.

To keep the code pretty, the solve function is a wrapper for a function that takes a current board and returns a list of Board with one new Queen on a legal position.

When we call solve, it calls our wrapped function s with an empty Board:

solve = s []
  where s board = undefined -- for now

As we said earlier, if the boards contains height queens, we have found a solution:

solve = s []
  where s board | length board == 8 = [board]

we return a list containing one Board, the current one.

Otherwise, we try to continue:

solve = s []
  where s board | line == 8 = [board]
                | otherwise = concatMap s possibles
          where line = length board
                possibles = [((line,y):board) | y <- [0..7], legal (line,y) board]

We use haskell's list comprehensions to generate the possibles legal boards.

On each of these Boards, we call s, to try to add yet a new Queen to them.

NB since s returns a list of Board, we use concatMap:

λ> :t concatMap 
concatMap :: Foldable t => (a -> [b]) -> t a -> [b]

if we talk about lists only, we could write this signature as:

λ> :t concatMap 
concatMap :: (a -> [b]) -> [a] -> [b]

so concatMap takes:

On each element of l, concatMap applies f, generating a list of things. Until now this is very similar to map, but it returns a list of list of things, so we have co concat all the lists we have created to get the desired effect.

Let's look at a quick example:

-- this returns a list containing k times the number k
f k = take k . repeat . (nb!!) $ k where nb='0123456789'

-- example :
f 9
-- "999999999"
f 2
-- "22"

-- now we will map it on a list of digits:
map f [1,8,2]
-- ["1","88888888","22"]


-- and if we use concat, which is in prelude
-- λ> :t concat
concat :: Foldable t => t [a] -> [a]
-- but could be defined for lists as:
concat = foldr (++) []

-- we get:
concat $ map f [1,8,2]
-- "18888888822"

-- which is the same as concatMap:
concatMap f [1,8,2]
-- "18888888822"

To summarize, the function s takes a board b;
if the board is full (8 queens) then it is a solution and we return [b] (a list with one solution).
Otherwise for each possible move on the next row we call s again, which will return a list of solutions for each element.
We use concatMap to keep a nice list of boards and not some list of list of list ... of board (due to the recursive calls)

# And Voilà!

Our program is ready, let's finally write our main:

main = putStrLn $
  (++"\n"++show (lengt solutions)++" solutions.")
  . unlines . map dispBoard $ solutions
  where solutions = solve

this will call solve, generating the solutions list, and nicely print each one of them.

Here is the entirety of the code:

module Main where

import Data.List(intersperse)

---- data ----

type Queen = (Int,Int)
type Board = [Queen]

---- display ----

dispBoard = (sep++) . (++sep) . unlines . map dispQ
  where dispQ (_,k) = ('|':) . (++"|") . intersperse ' '
                      $ r k ++ 'Q' : r (7-k)
          where r = flip take $ repeat '·'
        sep = "+---------------+\n"


---- logic ----

-- attacks :: Queen -> Queen -> Bool
attacks (ax,ay) (bx,by) = ax == bx
                       || ay == by
                       || abs (ax - bx) == abs (ay - by)

none :: Foldable t => (α -> Bool) -> t α -> Bool
none = (not.) . any

-- legal :: Queen -> Board -> Bool
legal q = none . attacks $ q

-- solve :: [Board]
solve = s []
  where s board | line == 8 = [board]
                | otherwise = concatMap s possibles
          where line = length board
                possibles = [((line,y):board) | y <- [0..7], legal (line,y) board]

---- main ----
main = putStrLn $
  (++"\n"++show (length solutions)++" solutions.")
  . unlines . map dispBoard $ solutions
  where solutions = solve

We end up with very few lines (without trying to "optimize" the size of the code) of readable code, and that's one other reason to love Haskell!

For the lazy ;) ones, here is the output:

λ> main
+---------------+
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · · · Q ·|
|· · Q · · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
|Q · · · · · · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|· Q · · · · · ·|
|· · · Q · · · ·|
|· · · · · · Q ·|
|· · Q · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|Q · · · · · · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · Q · · ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|· · · Q · · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · · Q · ·|
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|· · · Q · · · ·|
|· Q · · · · · ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
|· Q · · · · · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|Q · · · · · · ·|
|· · · Q · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
|· Q · · · · · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|· · Q · · · · ·|
|· · · · · · · Q|
|· · · Q · · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · · · · Q · ·|
|· Q · · · · · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|· · · · · · Q ·|
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|· Q · · · · · ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · · · Q · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|· · Q · · · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · · Q · ·|
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|· · · Q · · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · · Q · · ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|Q · · · · · · ·|
|· · · · · · Q ·|
|· · · Q · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · · Q · · ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|· Q · · · · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · · Q · · · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
|· Q · · · · · ·|
|· · · · · Q · ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|· · · · · · · Q|
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · · · Q · ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|· · · · · · · Q|
|Q · · · · · · ·|
|· · · · Q · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · · · Q · ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|· Q · · · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
|· · · · · · · Q|
|Q · · · · · · ·|
|· · · Q · · · ·|
|· · · · · Q · ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|Q · · · · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · Q · · · ·|
|· · · · · Q · ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|· Q · · · · · ·|
|· · · · Q · · ·|
|· · · · · · Q ·|
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
|Q · · · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · · · Q · · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · · · · Q ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|Q · · · · · · ·|
|· · · Q · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · · · · Q ·|
|· · Q · · · · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|· Q · · · · · ·|
|· · · · · Q · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· · · Q · · · ·|
|· · · · · · · Q|
|· · Q · · · · ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|· · Q · · · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
|Q · · · · · · ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|· Q · · · · · ·|
|· · · · · · Q ·|
|· · Q · · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
|Q · · · · · · ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|· · · · · · Q ·|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
|· Q · · · · · ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|Q · · · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|· · Q · · · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|Q · · · · · · ·|
|· · · · Q · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|· · Q · · · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|Q · · · · · · ·|
|· · · · Q · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|· · · · · · Q ·|
|· · · · Q · · ·|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|· · · · · · Q ·|
|· · Q · · · · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · · Q · · ·|
|Q · · · · · · ·|
|· · · · · Q · ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|· Q · · · · · ·|
|· · · · Q · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · · Q · ·|
|· Q · · · · · ·|
|· · · · Q · · ·|
|· · · · · · · Q|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|Q · · · · · · ·|
|· · · · Q · · ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|· · Q · · · · ·|
|· · · · · · Q ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|· · · · · · · Q|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · Q · ·|
|· Q · · · · · ·|
|· · · · Q · · ·|
|· · · · · · Q ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|· Q · · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · Q · · ·|
|· · · · · · Q ·|
|· · · Q · · · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · · · Q · ·|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · · · Q|
|· · · Q · · · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · · Q · ·|
|· Q · · · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
|Q · · · · · · ·|
|· · · · · · · Q|
|· · · Q · · · ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|· Q · · · · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · Q · · ·|
|· · · · · · · Q|
|· · · Q · · · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|· · Q · · · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · Q · · · ·|
|· · · · · · · Q|
|Q · · · · · · ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · · · Q ·|
|· · Q · · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|Q · · · · · · ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|Q · · · · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· · Q · · · · ·|
|· · · · · · Q ·|
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · · · · Q|
|· · · Q · · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · · · · Q · ·|
|· Q · · · · · ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|· · Q · · · · ·|
|· · · · · · Q ·|
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· · · · · · Q ·|
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· Q · · · · · ·|
|· · · · · Q · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· · · Q · · · ·|
|· · · · · · · Q|
|· · Q · · · · ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· Q · · · · · ·|
|· · · Q · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · · · Q|
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· · · · · · · Q|
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · · Q · ·|
|· Q · · · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|· · · · · · · Q|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · · Q · ·|
|· Q · · · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· Q · · · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · Q · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
+---------------+

+---------------+
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · · · Q · ·|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · Q · · · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · · Q · ·|
|· Q · · · · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · · Q · · · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|· · · · · · Q ·|
|· · Q · · · · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · · Q · · ·|
|Q · · · · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · Q · · ·|
|· · · · · · · Q|
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · Q · · · ·|
|· · · · · · · Q|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · · · · · Q ·|
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · Q · · ·|
|· · · · · · · Q|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
|· · Q · · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
|· · Q · · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|Q · · · · · · ·|
|· · · · · · · Q|
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · · · Q ·|
|· · Q · · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · · · Q · · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · · · · Q ·|
|· · Q · · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|Q · · · · · · ·|
|· · · Q · · · ·|
|· · · · · · Q ·|
|· · Q · · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
|Q · · · · · · ·|
|· · · Q · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · Q · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · · Q · · ·|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· · · Q · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · Q · · ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|Q · · · · · · ·|
|· · · · · · Q ·|
|· · · Q · · · ·|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · Q · · · · ·|
|· · · · Q · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|· Q · · · · · ·|
|· · · Q · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · · Q ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|· · Q · · · · ·|
|· · · · Q · · ·|
|· · · · · · · Q|
|Q · · · · · · ·|
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · · · Q ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|· · · · · · · Q|
|· · · Q · · · ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · · Q · ·|
|· Q · · · · · ·|
|· · · · · · Q ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · Q · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · · · Q ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|· · · · · Q · ·|
|Q · · · · · · ·|
|· · · · Q · · ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|· · Q · · · · ·|
|· · · · · · Q ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · · · Q|
|· · · · Q · · ·|
|· Q · · · · · ·|
|· · · Q · · · ·|
|· · · · · · Q ·|
+---------------+

+---------------+
|· · · · Q · · ·|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · · · Q · ·|
|· · · · · · · Q|
|· Q · · · · · ·|
|· · · Q · · · ·|
|· · · · · · Q ·|
+---------------+

+---------------+
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · · · · Q|
|· · · · · Q · ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · Q · · ·|
|· · · · · · Q ·|
+---------------+

+---------------+
|· · · · · Q · ·|
|· · Q · · · · ·|
|· · · · Q · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · · Q · · · ·|
|· Q · · · · · ·|
|· · · · · · · Q|
+---------------+

+---------------+
|· · · · · Q · ·|
|· · · Q · · · ·|
|· · · · · · Q ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · Q · · ·|
|· Q · · · · · ·|
|· · · · · · · Q|
+---------------+

+---------------+
|· · · Q · · · ·|
|· · · · · · Q ·|
|· · · · Q · · ·|
|· Q · · · · · ·|
|· · · · · Q · ·|
|Q · · · · · · ·|
|· · Q · · · · ·|
|· · · · · · · Q|
+---------------+

+---------------+
|· · · · Q · · ·|
|· · · · · · Q ·|
|· Q · · · · · ·|
|· · · · · Q · ·|
|· · Q · · · · ·|
|Q · · · · · · ·|
|· · · Q · · · ·|
|· · · · · · · Q|
+---------------+


92 solutions.