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 Queen
s that are already there.
In haskell-ish terms, we could say:not
any
of the Board
(the list of Queens) is attack
ed 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:
- a function f taking a α and returning a Bool
- a
Foldable
of α (here, a list)
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 Queen
s, 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 Queen
s 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 Board
s, 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:
- a function
f
that takes an element and returns a list of things - a list of elements
l
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.