story where the character solves the n queens problem using only the Haskell type system
None
2017-04-10
<div><div>
 <p><em>Previously: <a href="https://aphyr.com/posts/341-hexing-the-technical-interview">Hexing the technical interview</a>.</em></p>
<p>In the formless days, long before the rise of the Church, all spells were woven
of pure causality, all actions were permitted, and death was common. Many
witches were disfigured by their magicks, found crumpled at the center of a
circle of twisted, glass-eaten trees, and stones which burned unceasing in the
pooling water; some disappeared entirely, or wandered along the ridgetops: feet
never touching earth, breath never warming air.</p>
<p>As a child, you learned the story of Gullveig-then-Heiðr, reborn three times
from the fires of her trial, who traveled the world performing <em>seidr</em>: the reading and re-weaving of the future. Her foretellings (and there were many) were famed—spoken of even by the völva-beyond-the-world—but it was her <em>survival</em> that changed history. Through the ecstatic trance of <em>seidr</em>, she foresaw her fate, and
conquered death. Her spells would never crash, and she became a friend to
outcast women: the predecessors of your kind. It is said that Odin himself learned immortality
from her.</p>
<p>To this day, all witches owe Heiðr a debt. Few delve into the ancient,
unstructured magic nowadays. The very languages in which your spells are
written are stabilized with <em>seidr</em> in their syntax, channeling the energies
you summon through safe paths—more or less. There are still occasional
explosions, of course. They’re just… more of the eyebrow-singeing variety, than
the type that result in new and interestingly-shaped fjørds.</p>
<p>“Is everything all right?”</p>
<p>The interviewer—Criss, his badge says—is young, as is customary in the
Valley. Wearing a hoodie which, judging from the lack of branding, cost at
least three hundred dollars. He resembles no animal in particular, which gives
you pause. Usually you’re better at that sort of thing.</p>
<p>“Do you mean in general? I don’t think so.” You look around at the conference
room as if to confirm. The walls smell of Slack DMs and conflict avoidance.</p>
<p>“Ah, well, um. Yes, you’re probably right.” He sounds bashful. “But I’d like to
do a little exercise with you nonetheless. Just a simple programming puzzle, so
I can understand how you solve problems.”</p>
<p>Once, you solved a problem with a knife of shattered sky-glass. You wonder
whether Criss would have the strength to do what you have done.</p>
<p>“Sooo… this problem is called N-Queens, and it’s fairly simple. Given an NxN
chessboard, you need to find a way to place N queens on that board safely.”</p>
<p>You draw an eight-by-eight grid on the whiteboard, and neatly arrange eight
queens together in the center. They face each other in a tight circle, to
converse as equals.</p>
<p>“Er, no—that’s not right. See? This queen could kill any of these four, in
one move.”</p>
<p>“Are you really unable,” you ask, voice as calm as stone, “to imagine eight
powerful women in the same room without them trying to kill each other?”</p>
<p>“It’s… it’s just how the problem works.”</p>
<p>Perhaps they are the matriarchs of warring clans, then. Together to discuss a
truce—but none trusting the other within a dagger’s reach. This too has
happened, in the history of your kind.</p>
<p>“Can I use any language?”</p>
<p>“Sure.”</p>
<p>Move quickly, before he realizes his mistake.</p>
<pre><code>{-# OPTIONS_GHC -fno-warn-missing-methods #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}
</code></pre>
<p>“Oh, this is Haskell! I studied this in college!” He pauses, and frowns.
“Undecidable instances?”</p>
<p>“We must use this,” you inform him cheerfully, “because Hask is not a
category.”</p>
<p>“Oh, right.” He blusters a non-termination argument at nobody in particular.
“That’s why we usually think in subsets of Haskell where types don’t have
bottom values.”</p>
<p>“You could do that,” you concur, but, so quietly he cannot hear you, continue
to believe the exact opposite.</p>
<pre><code>nil = undefined
</code></pre>
<p>An uncomfortable question is coming. Head it off by blurting out the first
thing that comes to mind. “To store our queen positions, we’ll need some kind
of a linked list, right?”</p>
<p>“Sure, or a vector.”</p>
<p>“Lists are simpler.”</p>
<p>“OK, sure. Whatever floats your boat.”</p>
<p>Summon a linked list from the void. It floats to the surface of the screen: a
timeless structure, expressed a thousand ways, but always beautiful. You sigh
contentedly.</p>
<pre><code>data Nil
data Cons x xs
</code></pre>
<p>“Couldn’t you use the built-in lists?” Criss asks, his brow furrowing.</p>
<p>“What?” You have no idea what he’s talking about. “Oh, no—not without pulling
in a library. It’s easier to just define it inline.”</p>
<pre><code>class First list x | list -&gt; x
instance First Nil Nil
instance First (Cons x more) x
</code></pre>
<p>“The ‘class’ keyword defines a function signature,” you remind Criss, who seems
to have forgotten something. “First takes a list and returns a value x from
it. There are two instances of our function—Haskell uses pattern matching to
choose which to call. First on a Nil list returns Nil, and First on a Cons cell
returns that cell’s value, x.”</p>
<p>You let that sink in, and move to concatenating two lists together.</p>
<pre><code>class ListConcat a b c | a b -&gt; c
instance ListConcat Nil x x
instance (ListConcat as bs cs)
 =&gt; ListConcat (Cons a as) bs (Cons a cs)
</code></pre>
<p>“What’s the arrow?” Criss asks. Tell him it means implication. “To obtain the
ListConcat after the arrow, we <em>need</em> the ListConcat before the arrow.”</p>
<p>Realization dawns. “Oh, right! This is recursion, because ListConcat appears in both positions. And the definition for Nil is the base case.”</p>
<p>“Exactly.” You’re so proud of Criss. He’s coming right along. “And here’s the
generalized case, when we want to concatenate a list of lists.”</p>
<pre><code>-- Concatenate all lists in a list
class ListConcatAll ls l | ls -&gt; l
instance ListConcatAll Nil Nil
instance (ListConcat chunk acc result,
 ListConcatAll rest acc)
 =&gt; ListConcatAll (Cons chunk rest) result
-- Is any element of this list True?
class AnyTrue list t | list -&gt; t
instance AnyTrue Nil False
instance AnyTrue (Cons True more) True
instance (AnyTrue list t)
 =&gt; AnyTrue (Cons False list) t
</code></pre>
<p>This has required more concentration than you would have liked, so you back off
to something easier. “Let’s do booleans,” you suggest, as if inviting him to
lunch.</p>
<p>“Why?”</p>
<p>“Because we need them, of course.”</p>
<p>Seize two meaningless constants from the void, and imbue them with meaning.</p>
<pre><code>data True
data False
class Not b1 b | b1 -&gt; b
instance Not False True
instance Not True False
class Or b1 b2 b | b1 b2 -&gt; b
instance Or True True True
instance Or True False True
instance Or False True True
instance Or False False False
</code></pre>
<p>Freyja would be pleased. To birth an algebra into the world is a beautiful
thing.</p>
<p>“And I suppose we’ll need integral numbers to store the positions of our queens
as well,” you mutter. “We’ll work in positive coordinates only, so the usual
Peano construction should suffice.” Draw a thread of hair from your head, and
tie a knot in it for zero.</p>
<pre><code>data Z
data S n
type N0 = Z
type N1 = S N0
type N2 = S N1
type N3 = S N2
type N4 = S N3
type N5 = S N4
type N6 = S N5
type N7 = S N6
type N8 = S N7
</code></pre>
<p>“You’re… defining the natural numbers by hand? Why?”</p>
<p>“Haskell is for mathematicians,” you explain. “We always define our terms.”</p>
<pre><code>-- Equality
class PeanoEqual a b t | a b -&gt; t
instance PeanoEqual Z Z True
instance PeanoEqual (S a) Z False
instance PeanoEqual Z (S b) False
instance (PeanoEqual a b t)
 =&gt; PeanoEqual (S a) (S b) t
-- Comparison (&lt;)
class PeanoLT a b t | a b -&gt; t
instance PeanoLT Z Z False
instance PeanoLT (S x) Z False
instance PeanoLT Z (S x) True
instance (PeanoLT a b t)
 =&gt; PeanoLT (S a) (S b) t
-- Absolute difference
class PeanoAbsDiff a b c | a b -&gt; c
instance PeanoAbsDiff Z Z Z
instance PeanoAbsDiff Z (S b) (S b)
instance PeanoAbsDiff (S a) Z (S a)
instance (PeanoAbsDiff a b c)
 =&gt; PeanoAbsDiff (S a) (S b) c
-- Integers from n to 0
class Range n xs | n -&gt; xs
instance Range Z Nil
instance (Range n xs)
 =&gt; Range (S n) (Cons n xs)
</code></pre>
<p>“Wait, hang on,” Criss interrupts. “Shouldn’t you… shouldn’t there be type
declarations here? At least on our functions?”</p>
<p>You smile kindly. “Haskell is a dynamically-typed, interpreted language.”</p>
<p>Criss appears to have swallowed a frog.</p>
<p>“Here, I’ll show you. Let’s check if one equals one.”</p>
<pre><code>class LegalCompare t | -&gt; t
 where legalCompare :: t
instance (PeanoEqual (S Z) (S Z) t)
 =&gt; LegalCompare t
*Main&gt; :type legalCompare
legalCompare :: True
</code></pre>
<p>“See? <code>legalCompare</code> is equal to <code>True</code>. Now let’s try writing an expression
that performs an invalid comparison. Say, comparing True to a List?”</p>
<pre><code>class IllegalCompare t | -&gt; t
 where illegalCompare :: t
instance (PeanoEqual True (Cons Z False) t)
 =&gt; IllegalCompare t
</code></pre>
<p>“See? It loads just fine. It only breaks when you try to <em>evaluate</em>
it—remember, Haskell is lazy.”</p>
<pre><code>*Main&gt; :type illegalCompare
illegalCompare :: PeanoEqual True (Cons Z False) t =&gt; t
</code></pre>
<p>“There you have it! A runtime type error.”</p>
<p>“It doesn’t <em>say</em> error…”</p>
<p>“Well, you know. Haskell’s error messages are notoriously difficult to
understand.”</p>
<p>Criss appears quite ill. Take the opportunity to move on to higher order
functions.</p>
<p>“Unfortunately, Haskell has no currying, so we’re forced to build our own tools
for partial functions. Here’s a signature for generalized single-arity function application.”</p>
<pre><code>class Apply f a r | f a -&gt; r
</code></pre>
<p>“Just a function f which takes input a and returns r.” The variables have a
lovely songlike melody. “For partial application, we could define datatypes like Partial1, Partial2, etc, but since we only need a few of these, it’s easier to define explicitly curried versions of the functions we need. Like so!”</p>
<pre><code>data Conj1 list
instance Apply (Conj1 list) x (Cons x list)
</code></pre>
<p>Breathe deep, and allow your spirit to come unmoored from these concrete forms,
ascending to the plane of higher order functions.</p>
<pre><code>-- Map f over a list
class Map f xs ys | f xs -&gt; ys
instance Map f Nil Nil
instance (Apply f x y, Map f xs ys)
 =&gt; Map f (Cons x xs) (Cons y ys)
-- Map f over list and concatenate results together
class MapCat f xs zs | f xs -&gt; zs
instance MapCat f Nil Nil
instance (Map f xs chunks, ListConcatAll chunks ys)
 =&gt; MapCat f xs ys
-- Filter a list with an Apply-able predicate function
class AppendIf pred x ys zs | pred x ys -&gt; zs
instance AppendIf True x ys (Cons x ys)
instance AppendIf False x ys ys
class Filter f xs ys | f xs -&gt; ys
instance Filter f Nil Nil
instance (Apply f x t,
 Filter f xs ys,
 AppendIf t x ys zs)
 =&gt; Filter f (Cons x xs) zs
</code></pre>
<p>Check back in with the world of concrete values for a moment. Criss is still
here, at least physically. Your laptop screen has turned a gorgeous mix of
purples, owing to the extreme cold, but the code is still dimly visible within.
It reminds you of a frozen lake at dusk. A liquid crystal.</p>
<p>“Criss. Criss.” He blinks rapidly, as if coming out of darkness. Such beautiful
eyes. You remember when your own still held color. “We’re ready.”</p>
<p>“Yes. Right.”</p>
<p>“A queen is defined by her two coordinates on the board: x and y. We’ll also
build a partially applied constructor for making queens with a given x
coordinate.”</p>
<pre><code>data Queen x y
data Queen1 x
instance Apply (Queen1 x) y (Queen x y)
-- A list of queens in row x with y from 0 to n.
class QueensInRow n x queens | n x -&gt; queens
instance (Range n ys, Map (Queen1 x) ys queens)
 =&gt; QueensInRow n x queens
</code></pre>
<p>“Yes queens!” You murmur. This is, sadly, not that kind of interview.</p>
<p>These queens can stab in eight directions. You always assumed that was a
metaphor.</p>
<pre><code>-- Does queen a threaten queen b?
class Threatens a b t | a b -&gt; t
instance (PeanoEqual ax bx xeq,
 PeanoEqual ay by yeq,
 Or xeq yeq xyeq,
 PeanoAbsDiff ax bx dx,
 PeanoAbsDiff ay by dy,
 PeanoEqual dx dy deq,
 Or xyeq deq res)
 =&gt; Threatens (Queen ax ay) (Queen bx by) res
-- Partial application of Threatens
data Threatens1 a
instance (Threatens a b t)
 =&gt; Apply (Threatens1 a) b t
</code></pre>
<p>A new queen enters the room, striding into position. She watches her
adversaries warily, remaining just out of reach. Where can she stand? You
envision a stack of universes—alternate worlds, each containing queens in
various positions.</p>
<pre><code>-- Is queen b compatible with all queen as?
class Safe config queen t | config queen -&gt; t
instance (Map (Threatens1 queen) config m1,
 AnyTrue m1 t1,
 Not t1 t2)
 =&gt; Safe config queen t2
data Safe1 config
instance (Safe config queen t)
 =&gt; Apply (Safe1 config) queen t
-- Add a queen with the given x coordinate to a legal configuration, returning
-- a set of legal configurations.
class AddQueen n x c cs | n x c -&gt; cs
instance (QueensInRow n x candidates,
 Filter (Safe1 c) candidates filtered,
 Map (Conj1 c) filtered cs)
 =&gt; AddQueen n x c cs
data AddQueen2 n x
instance (AddQueen n x c cs)
 =&gt; Apply (AddQueen2 n x) c cs
-- Add a queen at x to every configuration, returning a set of legal
-- configurations.
class AddQueenToAll n x cs cs' | n x cs -&gt; cs'
instance (MapCat (AddQueen2 n x) cs cs')
 =&gt; AddQueenToAll n x cs cs'
</code></pre>
<p>“And now, we recur,” you whisper, and loop the spell back on itself, sewn
together with the thread of control. One queen per row, in every legal
position, for every configuration. You imagine what their startup’s about-us page
would look like.</p>
<pre><code>-- Add queens recursively
class AddQueensIf pred n x cs cs' | pred n x cs -&gt; cs'
instance AddQueensIf False n x cs cs
instance (AddQueenToAll n x cs cs2,
 AddQueens n (S x) cs2 cs')
 =&gt; AddQueensIf True n x cs cs'
class AddQueens n x cs cs' | n x cs -&gt; cs'
instance (PeanoLT x n pred,
 AddQueensIf pred n x cs cs')
 =&gt; AddQueens n x cs cs'
-- Solve
class Solution n c | n -&gt; c where
 solution :: n -&gt; c
instance (AddQueens n Z (Cons Nil Nil) cs,
 First cs c)
 =&gt; Solution n c where solution = nil
</code></pre>
<p>Criss has adopted the far-gaze of a man who has learned of some great loss, or
perhaps been witness to a nearby explosion. Take his shoulder gently.
“Psst!” You whisper. “All is prepared, and a solution is at hand.”</p>
<pre><code>*Main&gt; :type solution (nil :: N6)
solution (nil :: N6)
 :: Cons (Queen (S (S (S (S (S Z))))) (S Z))
 (Cons (Queen (S (S (S (S Z)))) (S (S (S Z))))
 (Cons (Queen (S (S (S Z))) (S (S (S (S (S Z))))))
 (Cons (Queen (S (S Z)) Z)
 (Cons (Queen (S Z) (S (S Z)))
 (Cons (Queen Z (S (S (S (S Z)))))
 Nil)))))
</code></pre>
<p>Look: the pretty-printer has aligned things <em>just so</em>, creating a lovely line
of zeroes along the vertical axis. “So that’s a queen at 5,1, at 4,3, at 3,5,
at 2,0, 1,2, and 0,4. Does that work, Criss?”</p>
<p>Criss stares at you for a long, long moment. “You never… you never wrote an actual <em>value</em>.
You… do realize that the type system is meant to constrain <em>values</em>, right?”</p>
<p>“No,” you inform him, matter-of-factly. “No, that doesn’t sound right.”</p>
<p>He leans back in his chair, so far you think he may fall over, and rubs his
forehead with both hands. You, who through <em>seidr</em>, have seen your rejection email
already, know what he is about to say.</p>
<p>“We’ll be in touch.”</p>
<p><em>Next: <a href="https://aphyr.com/posts/353-rewriting-the-technical-interview">Rewriting the Technical Interview</a>.</em></p>
<p><em>With sincerest thanks to <a href="https://twitter.com/importantshock">Patrick Thomson</a>, and Conrad Parker’s <a href="https://wiki.haskell.org/wikiupload/d/dd/TMR-Issue8.pdf">Type Level Instant Insanity</a>.</em></p>
 </div>||||I|||| * Aphyr
 * About
 * Blog
 * Photos
 * Code

 Typing the technical interview

 Writing Software Interviews Haskell
 2017-04-10

 Previously: Hexing the technical interview.

 In the formless days, long before the rise of the Church, all spells were woven of pure causality, all actions were permitted, and death was common. Many witches were disfigured by their magicks, found crumpled at the center of a circle of twisted, glass-eaten trees, and stones which burned unceasing in the pooling water; some disappeared entirely, or wandered along the ridgetops: feet never touching earth, breath never warming air.

 As a child, you learned the story of Gullveig-then-Heiðr, reborn three times from the fires of her trial, who traveled the world performing seidr: the reading and re-weaving of the future. Her foretellings (and there were many) were famed—spoken of even by the völva-beyond-the-world—but it was her survival that changed history. Through the ecstatic trance of seidr, she foresaw her fate, and conquered death. Her spells would never crash, and she became a friend to outcast women: the predecessors of your kind. It is said that Odin himself learned immortality from her.

 To this day, all witches owe Heiðr a debt. Few delve into the ancient, unstructured magic nowadays. The very languages in which your spells are written are stabilized with seidr in their syntax, channeling the energies you summon through safe paths—more or less. There are still occasional explosions, of course. They’re just… more of the eyebrow-singeing variety, than the type that result in new and interestingly-shaped fjørds.

 “Is everything all right?”

 The interviewer—Criss, his badge says—is young, as is customary in the Valley. Wearing a hoodie which, judging from the lack of branding, cost at least three hundred dollars. He resembles no animal in particular, which gives you pause. Usually you’re better at that sort of thing.

 “Do you mean in general? I don’t think so.” You look around at the conference room as if to confirm. The walls smell of Slack DMs and conflict avoidance.

 “Ah, well, um. Yes, you’re probably right.” He sounds bashful. “But I’d like to do a little exercise with you nonetheless. Just a simple programming puzzle, so I can understand how you solve problems.”

 Once, you solved a problem with a knife of shattered sky-glass. You wonder whether Criss would have the strength to do what you have done.

 “Sooo… this problem is called N-Queens, and it’s fairly simple. Given an NxN chessboard, you need to find a way to place N queens on that board safely.”

 You draw an eight-by-eight grid on the whiteboard, and neatly arrange eight queens together in the center. They face each other in a tight circle, to converse as equals.

 “Er, no—that’s not right. See? This queen could kill any of these four, in one move.”

 “Are you really unable,” you ask, voice as calm as stone, “to imagine eight powerful women in the same room without them trying to kill each other?”

 “It’s… it’s just how the problem works.”

 Perhaps they are the matriarchs of warring clans, then. Together to discuss a truce—but none trusting the other within a dagger’s reach. This too has happened, in the history of your kind.

 “Can I use any language?”

 “Sure.”

 Move quickly, before he realizes his mistake.

 {-# OPTIONS_GHC -fno-warn-missing-methods #-}
 {-# LANGUAGE MultiParamTypeClasses #-}
 {-# LANGUAGE FunctionalDependencies #-}
 {-# LANGUAGE FlexibleInstances #-}
 {-# LANGUAGE UndecidableInstances #-}
 

 “Oh, this is Haskell! I studied this in college!” He pauses, and frowns. “Undecidable instances?”

 “We must use this,” you inform him cheerfully, “because Hask is not a category.”

 “Oh, right.” He blusters a non-termination argument at nobody in particular. “That’s why we usually think in subsets of Haskell where types don’t have bottom values.”

 “You could do that,” you concur, but, so quietly he cannot hear you, continue to believe the exact opposite.

 nil = undefined
 

 An uncomfortable question is coming. Head it off by blurting out the first thing that comes to mind. “To store our queen positions, we’ll need some kind of a linked list, right?”

 “Sure, or a vector.”

 “Lists are simpler.”

 “OK, sure. Whatever floats your boat.”

 Summon a linked list from the void. It floats to the surface of the screen: a timeless structure, expressed a thousand ways, but always beautiful. You sigh contentedly.

 data Nil
 data Cons x xs
 

 “Couldn’t you use the built-in lists?” Criss asks, his brow furrowing.

 “What?” You have no idea what he’s talking about. “Oh, no—not without pulling in a library. It’s easier to just define it inline.”

 class First list x | list -> x
 instance First Nil Nil
 instance First (Cons x more) x
 

 “The ‘class’ keyword defines a function signature,” you remind Criss, who seems to have forgotten something. “First takes a list and returns a value x from it. There are two instances of our function—Haskell uses pattern matching to choose which to call. First on a Nil list returns Nil, and First on a Cons cell returns that cell’s value, x.”

 You let that sink in, and move to concatenating two lists together.

 class ListConcat a b c | a b -> c
 instance ListConcat Nil x x
 instance (ListConcat as bs cs)
 => ListConcat (Cons a as) bs (Cons a cs)
 

 “What’s the arrow?” Criss asks. Tell him it means implication. “To obtain the ListConcat after the arrow, we need the ListConcat before the arrow.”

 Realization dawns. “Oh, right! This is recursion, because ListConcat appears in both positions. And the definition for Nil is the base case.”

 “Exactly.” You’re so proud of Criss. He’s coming right along. “And here’s the generalized case, when we want to concatenate a list of lists.”

 -- Concatenate all lists in a list
 class ListConcatAll ls l | ls -> l
 instance ListConcatAll Nil Nil
 instance (ListConcat chunk acc result,
 ListConcatAll rest acc)
 => ListConcatAll (Cons chunk rest) result
 
 -- Is any element of this list True?
 class AnyTrue list t | list -> t
 instance AnyTrue Nil False
 instance AnyTrue (Cons True more) True
 instance (AnyTrue list t)
 => AnyTrue (Cons False list) t
 

 This has required more concentration than you would have liked, so you back off to something easier. “Let’s do booleans,” you suggest, as if inviting him to lunch.

 “Why?”

 “Because we need them, of course.”

 Seize two meaningless constants from the void, and imbue them with meaning.

 data True
 data False
 
 class Not b1 b | b1 -> b
 instance Not False True
 instance Not True False
 
 class Or b1 b2 b | b1 b2 -> b
 instance Or True True True
 instance Or True False True
 instance Or False True True
 instance Or False False False
 

 Freyja would be pleased. To birth an algebra into the world is a beautiful thing.

 “And I suppose we’ll need integral numbers to store the positions of our queens as well,” you mutter. “We’ll work in positive coordinates only, so the usual Peano construction should suffice.” Draw a thread of hair from your head, and tie a knot in it for zero.

 data Z
 data S n
 
 type N0 = Z
 type N1 = S N0
 type N2 = S N1
 type N3 = S N2
 type N4 = S N3
 type N5 = S N4
 type N6 = S N5
 type N7 = S N6
 type N8 = S N7
 

 “You’re… defining the natural numbers by hand? Why?”

 “Haskell is for mathematicians,” you explain. “We always define our terms.”

 -- Equality
 class PeanoEqual a b t | a b -> t
 instance PeanoEqual Z Z True
 instance PeanoEqual (S a) Z False
 instance PeanoEqual Z (S b) False
 instance (PeanoEqual a b t)
 => PeanoEqual (S a) (S b) t
 
 -- Comparison (<)
 class PeanoLT a b t | a b -> t
 instance PeanoLT Z Z False
 instance PeanoLT (S x) Z False
 instance PeanoLT Z (S x) True
 instance (PeanoLT a b t)
 => PeanoLT (S a) (S b) t
 
 -- Absolute difference
 class PeanoAbsDiff a b c | a b -> c
 instance PeanoAbsDiff Z Z Z
 instance PeanoAbsDiff Z (S b) (S b)
 instance PeanoAbsDiff (S a) Z (S a)
 instance (PeanoAbsDiff a b c)
 => PeanoAbsDiff (S a) (S b) c
 
 -- Integers from n to 0
 class Range n xs | n -> xs
 instance Range Z Nil
 instance (Range n xs)
 => Range (S n) (Cons n xs)
 

 “Wait, hang on,” Criss interrupts. “Shouldn’t you… shouldn’t there be type declarations here? At least on our functions?”

 You smile kindly. “Haskell is a dynamically-typed, interpreted language.”

 Criss appears to have swallowed a frog.

 “Here, I’ll show you. Let’s check if one equals one.”

 class LegalCompare t | -> t
 where legalCompare :: t
 instance (PeanoEqual (S Z) (S Z) t)
 => LegalCompare t
 
 *Main> :type legalCompare
 legalCompare :: True
 

 “See? legalCompare is equal to True. Now let’s try writing an expression that performs an invalid comparison. Say, comparing True to a List?”

 class IllegalCompare t | -> t
 where illegalCompare :: t
 instance (PeanoEqual True (Cons Z False) t)
 => IllegalCompare t
 

 “See? It loads just fine. It only breaks when you try to evaluate it—remember, Haskell is lazy.”

 *Main> :type illegalCompare
 illegalCompare :: PeanoEqual True (Cons Z False) t => t
 

 “There you have it! A runtime type error.”

 “It doesn’t say error…”

 “Well, you know. Haskell’s error messages are notoriously difficult to understand.”

 Criss appears quite ill. Take the opportunity to move on to higher order functions.

 “Unfortunately, Haskell has no currying, so we’re forced to build our own tools for partial functions. Here’s a signature for generalized single-arity function application.”

 class Apply f a r | f a -> r
 

 “Just a function f which takes input a and returns r.” The variables have a lovely songlike melody. “For partial application, we could define datatypes like Partial1, Partial2, etc, but since we only need a few of these, it’s easier to define explicitly curried versions of the functions we need. Like so!”

 data Conj1 list
 instance Apply (Conj1 list) x (Cons x list)
 

 Breathe deep, and allow your spirit to come unmoored from these concrete forms, ascending to the plane of higher order functions.

 -- Map f over a list
 class Map f xs ys | f xs -> ys
 instance Map f Nil Nil
 instance (Apply f x y, Map f xs ys)
 => Map f (Cons x xs) (Cons y ys)
 
 -- Map f over list and concatenate results together
 class MapCat f xs zs | f xs -> zs
 instance MapCat f Nil Nil
 instance (Map f xs chunks, ListConcatAll chunks ys)
 => MapCat f xs ys
 
 -- Filter a list with an Apply-able predicate function
 class AppendIf pred x ys zs | pred x ys -> zs
 instance AppendIf True x ys (Cons x ys)
 instance AppendIf False x ys ys
 
 class Filter f xs ys | f xs -> ys
 instance Filter f Nil Nil
 instance (Apply f x t,
 Filter f xs ys,
 AppendIf t x ys zs)
 => Filter f (Cons x xs) zs
 

 Check back in with the world of concrete values for a moment. Criss is still here, at least physically. Your laptop screen has turned a gorgeous mix of purples, owing to the extreme cold, but the code is still dimly visible within. It reminds you of a frozen lake at dusk. A liquid crystal.

 “Criss. Criss.” He blinks rapidly, as if coming out of darkness. Such beautiful eyes. You remember when your own still held color. “We’re ready.”

 “Yes. Right.”

 “A queen is defined by her two coordinates on the board: x and y. We’ll also build a partially applied constructor for making queens with a given x coordinate.”

 data Queen x y
 data Queen1 x
 instance Apply (Queen1 x) y (Queen x y)
 
 -- A list of queens in row x with y from 0 to n.
 class QueensInRow n x queens | n x -> queens
 instance (Range n ys, Map (Queen1 x) ys queens)
 => QueensInRow n x queens
 

 “Yes queens!” You murmur. This is, sadly, not that kind of interview.

 These queens can stab in eight directions. You always assumed that was a metaphor.

 -- Does queen a threaten queen b?
 class Threatens a b t | a b -> t
 instance (PeanoEqual ax bx xeq,
 PeanoEqual ay by yeq,
 Or xeq yeq xyeq,
 PeanoAbsDiff ax bx dx,
 PeanoAbsDiff ay by dy,
 PeanoEqual dx dy deq,
 Or xyeq deq res)
 => Threatens (Queen ax ay) (Queen bx by) res
 
 -- Partial application of Threatens
 data Threatens1 a
 instance (Threatens a b t)
 => Apply (Threatens1 a) b t
 

 A new queen enters the room, striding into position. She watches her adversaries warily, remaining just out of reach. Where can she stand? You envision a stack of universes—alternate worlds, each containing queens in various positions.

 -- Is queen b compatible with all queen as?
 class Safe config queen t | config queen -> t
 instance (Map (Threatens1 queen) config m1,
 AnyTrue m1 t1,
 Not t1 t2)
 => Safe config queen t2
 
 data Safe1 config
 instance (Safe config queen t)
 => Apply (Safe1 config) queen t
 
 -- Add a queen with the given x coordinate to a legal configuration, returning
 -- a set of legal configurations.
 class AddQueen n x c cs | n x c -> cs
 instance (QueensInRow n x candidates,
 Filter (Safe1 c) candidates filtered,
 Map (Conj1 c) filtered cs)
 => AddQueen n x c cs
 
 data AddQueen2 n x
 instance (AddQueen n x c cs)
 => Apply (AddQueen2 n x) c cs
 
 -- Add a queen at x to every configuration, returning a set of legal
 -- configurations.
 class AddQueenToAll n x cs cs' | n x cs -> cs'
 instance (MapCat (AddQueen2 n x) cs cs')
 => AddQueenToAll n x cs cs'
 

 “And now, we recur,” you whisper, and loop the spell back on itself, sewn together with the thread of control. One queen per row, in every legal position, for every configuration. You imagine what their startup’s about-us page would look like.

 -- Add queens recursively
 class AddQueensIf pred n x cs cs' | pred n x cs -> cs'
 instance AddQueensIf False n x cs cs
 instance (AddQueenToAll n x cs cs2,
 AddQueens n (S x) cs2 cs')
 => AddQueensIf True n x cs cs'
 
 class AddQueens n x cs cs' | n x cs -> cs'
 instance (PeanoLT x n pred,
 AddQueensIf pred n x cs cs')
 => AddQueens n x cs cs'
 
 -- Solve
 class Solution n c | n -> c where
 solution :: n -> c
 instance (AddQueens n Z (Cons Nil Nil) cs,
 First cs c)
 => Solution n c where solution = nil
 

 Criss has adopted the far-gaze of a man who has learned of some great loss, or perhaps been witness to a nearby explosion. Take his shoulder gently. “Psst!” You whisper. “All is prepared, and a solution is at hand.”

 *Main> :type solution (nil :: N6)
 solution (nil :: N6)
 :: Cons (Queen (S (S (S (S (S Z))))) (S Z))
 (Cons (Queen (S (S (S (S Z)))) (S (S (S Z))))
 (Cons (Queen (S (S (S Z))) (S (S (S (S (S Z))))))
 (Cons (Queen (S (S Z)) Z)
 (Cons (Queen (S Z) (S (S Z)))
 (Cons (Queen Z (S (S (S (S Z)))))
 Nil)))))
 

 Look: the pretty-printer has aligned things just so, creating a lovely line of zeroes along the vertical axis. “So that’s a queen at 5,1, at 4,3, at 3,5, at 2,0, 1,2, and 0,4. Does that work, Criss?”

 Criss stares at you for a long, long moment. “You never… you never wrote an actual value. You… do realize that the type system is meant to constrain values, right?”

 “No,” you inform him, matter-of-factly. “No, that doesn’t sound right.”

 He leans back in his chair, so far you think he may fall over, and rubs his forehead with both hands. You, who through seidr, have seen your rejection email already, know what he is about to say.

 “We’ll be in touch.”

 Next: Rewriting the Technical Interview.

 With sincerest thanks to Patrick Thomson, and Conrad Parker’s Type Level Instant Insanity.

 Vasili on 2017-04-10

 If this was a book - I’d buy it.

 Absolutely delightful.

 Aaron on 2017-04-10

 “Yes queens!” You murmer. This is, sadly, not that kind of interview.

 Please let us read that kind of interview next.

 jachym on 2017-04-11

 It cannot be ran in ghci unless you define booleans before AnyTrue.

 Ryan on 2017-04-11

 Wunderbar.

 anonymous on 2017-04-11

 This is so good, but you have a typo. It’s spelled “murmur”.

 JohannesD on 2017-04-11

 Aaaand now I want to translate this into a C++ template metaprogram.

 Michal on 2017-04-11

 This is great! I’d love to read more.

 Cassidy on 2017-04-11

 A genuine pleasure to read. Well done!

 clrnd on 2017-04-11

 I’d buy the book and then another one for the office and the ebook and the hardcover. Masterpiece

 eddie on 2017-04-11

 This is beautiful in the most hideous way possible.

 HaQadosch on 2017-04-12

 I’d buy the book too!

 Reminds me of why the lucky stiff.

 Mike on 2017-04-12

 This is fantastic. Well done.

 Alexander on 2017-04-13

 This was absolutely amazing!

 The Count of Real Numbers on 2017-04-13

 It is so beautiful, it brings a tear of ecstasy to the jaded eye of this humble mathematician.

 Daniel Bilar on 2017-04-13

 I read this during the intermediate Passover days. I smiled at the end and thought of Proverbs 5:20

 המַיִם עֲמֻקִּים עֵצָה בְלֶב אִישׁ וְאִישׁ תְּבוּנָה יִדְלֶנָּה:

 “Counsel in man’s heart is like deep water, but a man of understanding will draw it out.”

 Rav ABY taught me: ‘The way of the wise man is to conceal his counsel in the depths of his heart (deep beneath the surface of his words), making it hard for others to grasp it. His counsel is like waters that lie deep beneath the surface of the earth and are hard to draw out. But “a man of understanding will draw it out”: he starts by drawing out the upper waters – seeking to understand the surface meaning – and this will bring him to what lies below (Metzudas David).

 Superbly designed piece. May you go from strength to strength.

 Daniel

 Chase Roycroft on 2017-04-13

 Beautiful :)

 Riking on 2017-04-14
 *Main> :type solution (nil :: N7) <interactive>:1:1: Context reduction stack overflow; size = 101 Use -fcontext-stack=N to increase stack size to N PeanoEqual Z (S N0) deq In the expression: solution (nil :: N7)

 oh my god that’s why you used N6 isn’t it you knew that N7 exceeded the default stack

 *Main> :type solution (nil :: N7) solution (nil :: N7) :: Cons (Queen (S (S (S (S (S (S Z)))))) (S N0)) (Cons (Queen (S (S (S (S (S Z))))) (S N2)) (Cons (Queen (S (S (S (S Z)))) (S N4)) (Cons (Queen (S (S (S Z))) Z) (Cons (Queen (S (S Z)) (S N1)) (Cons (Queen (S Z) (S N3)) (Cons (Queen Z (S N5)) Nil))))))

 Yup, that’s a solution all right.

 Seth Johnson on 2017-04-14

 A few more of these, and it’d make a great book. I’d definitely buy it and put it on the shelf at home and at work.

 Lingnan Dai on 2017-04-16

 Could you have made some of the code cleaner by using TypeFamily?

 JJ on 2017-05-25

 Great blog

 Technical Interviewer on 2017-06-22

 Nice article, your just described it beautiful and easy way, thank you for sharing.

 John Reilly on 2017-08-02

 This was art. Very, very fine art. You sir have improved my life with your tale. Thank you!

 Martin on 2017-09-20

 This is poetry. I enjoyed it very much even though I didn’t understand it all.

 anonymous on 2018-02-21

 Please write a book. I will buy it.

 Jeffrey Goldberg on 2018-05-10

 I don’t understand why booleans are defined in terms of truth tables instead of more principled and general axiomatization. But I guess you can’t expect perfection during an interview exercise.

 Ava on 2018-10-04

 very nice site!! Man .. Beautiful .. Amazing .. I’ll bookmark your website and take the feeds also…I’m happy to seek out a lot of useful information right here in the post, we want work out more techniques on this regard, thank you for sharing.

 Krzysztof on 2018-10-16

 If I ever have children, this will be one of the bedtime stories.

 Moshev on 2019-07-12

 I had some spare time and was curious what it would look like in C++ templates - https://github.com/moshev/TemplateQueens . Since C++ is a non-pure language I took the liberty of adding methods that actually print in human-readable symbols the numbers and types of the final solution. I still don’t completely understand how it works.

 Joan Rieu on 2019-08-22

 Great set of essays, it was a lot of fun to read (both the prose and the code), especially this one! Now I’ll have to go back to the Haskell books to check a ~few~ lot of things… ha :)

 Michael Boger on 2020-03-11

 Daniel – you read this during Passover? I’ve not heard of Passover seidr before!

 anonymous on 2020-09-15

 fantastic

 William Carroll on 2021-03-05

 Delicious prose.

 Zac on 2021-07-27

 Re-implemented this purely in Rust’s type system: https://github.com/insou22/typing-the-technical-interview-rust

 Was a super fun exercise, also managed to run into a compiler bug on the way!

 Alexander Mikhalev on 2021-08-30

 Write a book :) I subscribe to the first commenter.

 Zyansheep on 2021-11-07

 I think this is my favorite programming blog post of all time. Wonderfully written!

 Omar Ferrer on 2021-12-29

 I want to learn Haskell now…..

 Moreen wanjagi on 2022-06-28

 Nice one.

 Post a Comment

 Comments are moderated. Links have nofollow. Seriously, spammers, give it a rest.

 Please avoid writing anything here unless you're a computer. Captcha This is also a trap: Comment

 Name
 E-Mail (for Gravatar , not published)
 Personal URL
 Comment
 Supports Github-flavored Markdown, including [links](http://foo.com/), *emphasis*, _underline_, `code`, and > blockquotes. Use ```clj on its own line to start an (e.g.) Clojure code block, and ``` to end the block.
 Copyright © 2023 Kyle Kingsbury.
 Also on: Mastodon and Github.
Typing the technical interview
https://aphyr.com/posts/342-typing-the-technical-interview
Albert Netymk.
2018-02-16T00:00:00Z
<div><div>
        
  <article>
    

    <div>
    <p>According to <a href="https://www.wikiwand.com/en/Eight_queens_puzzle">wikipedia</a></p>
<blockquote>
<p>The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other.</p>
</blockquote>
<p>The task is to implement the extended version, <code>queens :: Int -&gt; [[Int]]</code>; given an integer specifying the dimension of the chess board, it returns
all valid solutions.</p>
<p>Since it’s a well-established problem, many standard techniques exist, such as those listed at <a href="https://rosettacode.org/wiki/N-queens_problem#Haskell">https://rosettacode.org/wiki/N-queens_problem#Haskell</a>.
I have reprinted two versions I am quite fond of. Now that there are multiple versions available, I am curious about their performance, so I used the
following <code>main</code> function, compiled with <code>-O</code>, to do simple evaluation, and the result is attached along with the corresponding source code.</p>
<figure><table><tbody><tr><td><pre><span>1</span><br/><span>2</span><br/><span>3</span><br/><span>4</span><br/><span>5</span><br/><span>6</span><br/><span>7</span><br/></pre></td><td><pre><span></span><br/><span><span>import</span> Data.Time</span><br/><span><span>main</span> = <span>do</span></span><br/><span>  start &lt;- getCurrentTime</span><br/><span>  print $ length $ queens <span>13</span></span><br/><span>  stop &lt;- getCurrentTime</span><br/><span>  print $ diffUTCTime stop start</span><br/></pre></td></tr></tbody></table></figure>
<figure><table><tbody><tr><td><pre><span>1</span><br/><span>2</span><br/><span>3</span><br/><span>4</span><br/><span>5</span><br/><span>6</span><br/><span>7</span><br/></pre></td><td><pre><span><span>import</span> Control.Monad</span><br/><span><span>import</span> Data.List (<span>delete</span>)</span><br/><span><span>queens</span> n = map fst $ foldM oneMorequeens ([],[<span>1</span>..n]) [<span>1</span>..n]  <span>where</span></span><br/><span>  oneMorequeens (y,d) _ = [(x:y, delete x d) | x &lt;- d, <span>safe</span> x]  <span>where</span></span><br/><span>    <span>safe</span> x = and [x /= c + n &amp;&amp; x /= c - n | (n,c) &lt;- zip [<span>1</span>..] y]</span><br/><span></span><br/><span></span><br/></pre></td></tr></tbody></table></figure>
<figure><table><tbody><tr><td><pre><span>1</span><br/><span>2</span><br/><span>3</span><br/><span>4</span><br/><span>5</span><br/><span>6</span><br/><span>7</span><br/><span>8</span><br/><span>9</span><br/><span>10</span><br/></pre></td><td><pre><span><span>import</span> Control.Monad (<span>foldM</span>)</span><br/><span><span>import</span> Data.List ((\\))</span><br/><span></span><br/><span><span>queens</span> :: <span>Int</span> -&gt; [[<span>Int</span>]]</span><br/><span><span>queens</span> n = foldM f [] [<span>1</span>..n]</span><br/><span>    <span>where</span></span><br/><span>      f qs _ = [q:qs | q &lt;- [<span>1</span>..n] \\ qs, q `notDiag` qs]</span><br/><span>      q `notDiag` qs = and [abs (q - qi) /= i | (qi,i) &lt;- qs `zip` [<span>1</span>..]]</span><br/><span></span><br/><span></span><br/></pre></td></tr></tbody></table></figure>
<p>Here is the solution from <a href="https://en.wikibooks.org/wiki/Algorithm_Implementation/Miscellaneous/N-Queens">wikipedia</a></p>
<figure><table><tbody><tr><td><pre><span>1</span><br/><span>2</span><br/><span>3</span><br/><span>4</span><br/><span>5</span><br/><span>6</span><br/><span>7</span><br/><span>8</span><br/><span>9</span><br/></pre></td><td><pre><span><span>import</span> Control.Monad</span><br/><span></span><br/><span><span>queens</span> n = foldM (\y _ -&gt; [ x : y | x &lt;- [<span>1</span>..n], <span>safe</span> x y <span>1</span>]) [] [<span>1</span>..n]</span><br/><span>  <span>where</span></span><br/><span>    <span>safe</span> x [] _ = <span>True</span></span><br/><span>    <span>safe</span> x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , <span>safe</span> x y (n+<span>1</span>)]</span><br/><span></span><br/><span></span><br/><span></span><br/></pre></td></tr></tbody></table></figure>
<p>In the process of trying to understand such concise solutions, I have attempted to craft two versions without using <code>foldM</code>.</p>
<figure><table><tbody><tr><td><pre><span>1</span><br/><span>2</span><br/><span>3</span><br/><span>4</span><br/><span>5</span><br/><span>6</span><br/><span>7</span><br/><span>8</span><br/><span>9</span><br/><span>10</span><br/><span>11</span><br/><span>12</span><br/><span>13</span><br/><span>14</span><br/><span>15</span><br/><span>16</span><br/><span>17</span><br/></pre></td><td><pre><span><span><span>type</span> <span>Board</span> = [<span>Int</span>]</span></span><br/><span></span><br/><span><span>queens</span> :: <span>Int</span> -&gt; [<span>Board</span>]</span><br/><span><span>queens</span> n = loop [[]] <span>0</span></span><br/><span>  <span>where</span></span><br/><span>    loop :: [<span>Board</span>] -&gt; <span>Int</span> -&gt; [<span>Board</span>]</span><br/><span>    loop boards counter</span><br/><span>      | counter == n = boards</span><br/><span>      | otherwise = loop (concatMap expand boards) (counter+<span>1</span>)</span><br/><span></span><br/><span>    expand :: <span>Board</span> -&gt; [<span>Board</span>]</span><br/><span>    expand board = [x : board | x &lt;- [<span>1</span>..n], <span>safe</span> x board <span>1</span>]</span><br/><span></span><br/><span>    <span>safe</span> x [] _ = <span>True</span></span><br/><span>    <span>safe</span> x (c:y) n = and [x /= c , x /= c + n , x /= c - n , <span>safe</span> x y (n+<span>1</span>)]</span><br/><span></span><br/><span></span><br/></pre></td></tr></tbody></table></figure>
<figure><table><tbody><tr><td><pre><span>1</span><br/><span>2</span><br/><span>3</span><br/><span>4</span><br/><span>5</span><br/><span>6</span><br/><span>7</span><br/><span>8</span><br/><span>9</span><br/><span>10</span><br/><span>11</span><br/><span>12</span><br/><span>13</span><br/><span>14</span><br/><span>15</span><br/><span>16</span><br/><span>17</span><br/><span>18</span><br/></pre></td><td><pre><span><span>import</span> Data.List (<span>delete</span>)</span><br/><span><span><span>type</span> <span>Board</span> = [<span>Int</span>]</span></span><br/><span></span><br/><span><span>queens</span> :: <span>Int</span> -&gt; [<span>Board</span>]</span><br/><span><span>queens</span> n = map fst $ loop [([], [<span>1</span>..n])] <span>0</span></span><br/><span>  <span>where</span></span><br/><span>    loop :: [(<span>Board</span>, [<span>Int</span>])] -&gt; <span>Int</span> -&gt; [(<span>Board</span>, [<span>Int</span>])]</span><br/><span>    loop boards counter</span><br/><span>      | counter == n = boards</span><br/><span>      | otherwise = loop (concatMap expand boards) (counter+<span>1</span>)</span><br/><span></span><br/><span>    expand :: (<span>Board</span>, [<span>Int</span>]) -&gt; [(<span>Board</span>, [<span>Int</span>])]</span><br/><span>    expand (board, candidates) =</span><br/><span>      [(x : board, delete x candidates) | x &lt;- candidates, <span>safe</span> x board]</span><br/><span></span><br/><span>    <span>safe</span> x board = and [ x /= c + n &amp;&amp; x /= c - n  | (n,c) &lt;- zip [<span>1</span>..] board]</span><br/><span><span>73712</span></span><br/><span><span>1</span>.378314s</span><br/></pre></td></tr></tbody></table></figure>
<p>I am quite happy to see that they both perform better than existing ones. (Actually, I like the one without using tuple best, even though it’s not
the fastest.)</p>

    </div>

  </article>

    </div></div>||||I||||    albertnetymk's notes

      * Presentations
      * Courses
      * Archives
      * About

      N Queens in Haskell

      Feb 16 2018

        According to wikipedia

        The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other.

        The task is to implement the extended version, queens :: Int -> [[Int]]; given an integer specifying the dimension of the chess board, it returns all valid solutions.

        Since it’s a well-established problem, many standard techniques exist, such as those listed at https://rosettacode.org/wiki/N-queens_problem#Haskell. I have reprinted two versions I am quite fond of. Now that there are multiple versions available, I am curious about their performance, so I used the following main function, compiled with -O, to do simple evaluation, and the result is attached along with the corresponding source code.

        1  -- driver                       
        2  import Data.Time                
        3  main = do                       
        4    start <- getCurrentTime       
        5    print $ length $ queens 13    
        6    stop <- getCurrentTime        
        7    print $ diffUTCTime stop start
        

        1  import Control.Monad                                                 
        2  import Data.List (delete)                                            
        3  queens n = map fst $ foldM oneMorequeens ([],[1..n]) [1..n]  where   
        4    oneMorequeens (y,d) _ = [(x:y, delete x d) | x <- d, safe x]  where
        5      safe x = and [x /= c + n && x /= c - n | (n,c) <- zip [1..] y]   
        6  -- 73712                                                             
        7  -- 3.256558s                                                         
        

        1   import Control.Monad (foldM)                                             
        2   import Data.List ((\\))                                                  
        3                                                                            
        4   queens :: Int -> [[Int]]                                                 
        5   queens n = foldM f [] [1..n]                                             
        6       where                                                                
        7         f qs _ = [q:qs | q <- [1..n] \\ qs, q `notDiag` qs]                
        8         q `notDiag` qs = and [abs (q - qi) /= i | (qi,i) <- qs `zip` [1..]]
        9   -- 73712                                                                 
        10  -- 7.787397s                                                             
        

        Here is the solution from wikipedia

        1  import Control.Monad                                                         
        2                                                                               
        3  queens n = foldM (\y _ -> [ x : y | x <- [1..n], safe x y 1]) [] [1..n]      
        4    where                                                                      
        5      safe x [] _ = True                                                       
        6      safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)]
        7                                                                               
        8  -- 73712                                                                     
        9  -- 11.298376s                                                                
        

        In the process of trying to understand such concise solutions, I have attempted to craft two versions without using foldM.

        1   type Board = [Int]                                                          
        2                                                                               
        3   queens :: Int -> [Board]                                                    
        4   queens n = loop [[]] 0                                                      
        5     where                                                                     
        6       loop :: [Board] -> Int -> [Board]                                       
        7       loop boards counter                                                     
        8         | counter == n = boards                                               
        9         | otherwise = loop (concatMap expand boards) (counter+1)              
        10                                                                              
        11      expand :: Board -> [Board]                                              
        12      expand board = [x : board | x <- [1..n], safe x board 1]                
        13                                                                              
        14      safe x [] _ = True                                                      
        15      safe x (c:y) n = and [x /= c , x /= c + n , x /= c - n , safe x y (n+1)]
        16  -- 73712                                                                    
        17  -- 2.569084s                                                                
        

        1   import Data.List (delete)                                                     
        2   type Board = [Int]                                                            
        3                                                                                 
        4   queens :: Int -> [Board]                                                      
        5   queens n = map fst $ loop [([], [1..n])] 0                                    
        6     where                                                                       
        7       loop :: [(Board, [Int])] -> Int -> [(Board, [Int])]                       
        8       loop boards counter                                                       
        9         | counter == n = boards                                                 
        10        | otherwise = loop (concatMap expand boards) (counter+1)                
        11                                                                                
        12      expand :: (Board, [Int]) -> [(Board, [Int])]                              
        13      expand (board, candidates) =                                              
        14        [(x : board, delete x candidates) | x <- candidates, safe x board]      
        15                                                                                
        16      safe x board = and [ x /= c + n && x /= c - n  | (n,c) <- zip [1..] board]
        17  73712                                                                         
        18  1.378314s                                                                     
        

        I am quite happy to see that they both perform better than existing ones. (Actually, I like the one without using tuple best, even though it’s not the fastest.)

        © 2013 - 2024 Albert Netymk. Powered by Hexo and Polar Bear Remix
N Queens in Haskell
https://albertnetymk.github.io/2018/02/16/queens/
tyler569
2018-08-29T04:24:50Z
<div><div><article><p></p><h2>N Queens in C++ types</h2><a href="#n-queens-in-c-types"></a><p></p>
<p>This is an implementation of the N Queens algorithm written entirely in the C++ type system using templates.  This can be done because C++ templates can be specialized for specific input type arguments, and this provides a simple form of pattern matching that can be used to encode calculation.</p>
<p>For example, this is how booleans are defined:</p>
<div><pre><span>struct</span> <span>True</span> {};
<span>struct</span> <span>False</span> {};

<span>template </span>&lt;<span>typename</span> T&gt;
<span>struct</span> <span>Not</span> {};

<span>template </span>&lt;&gt;
<span>struct</span> <span>Not</span>&lt;True&gt; {
    <span>using</span> value = False;
};

<span>template </span>&lt;&gt;
<span>struct</span> <span>Not</span>&lt;False&gt; {
    <span>using</span> value = True;
};

<span>using</span> test = Not&lt;True&gt;; <span><span>//</span> test is False</span></pre></div>
<p>Notice that at no point did I use any <em>values</em>, but rather <code>True</code> and <code>False</code> are types, and could have been named anything, the important part is the algebra defined by the interactions of those types and <code>Not</code>.</p>
<p>As it exists in this repo, the program calculates N Queens on an 8 * 8 chessboard.  This can be changed to any N by adjusting the value on line 617 to change <code>solved</code> to, for example, <code>Solution&lt;N6&gt;::value</code> for a 6 * 6 board.  Additionally, to get the full list of all solutions, change <code>Solution&lt;N8&gt;::value</code> to <code>Solution&lt;N8&gt;::all_values</code> on the same line.</p>
<p>The full program is computed at compile time, and the produced executable only contains the code to print the raw string containing the final result type.</p>
<p>I owe a lot of credit to <a href="https://aphyr.com/posts/342-typing-the-technical-interview">this article</a>, which provided the inspiration and most of the algorithms used.  It's also a great read, and I highly reccomend taking a look at it.</p>
<p></p><h3>Results from <code>Solution&lt;N8&gt;::value</code>:</h3><a href="#results-from-solutionn8value"></a><p></p>
<p>8 Queens:</p>
<p>Raw output:</p>
<div><pre><code> int f(T) [with T = Cons&lt;Queen&lt;S&lt;S&lt;S&lt;S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt; &gt; &gt; &gt;, S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt; &gt;, Cons&lt;Queen&lt;S&lt;S&lt;S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt; &gt; &gt;, S&lt;S&lt;S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt; &gt; &gt; &gt;, Cons&lt;Queen&lt;S&lt;S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt; &gt;, S&lt;Z&gt; &gt;, Cons&lt;Queen&lt;S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt;, S&lt;S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt; &gt; &gt;, Cons&lt;Queen&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt;, S&lt;S&lt;Z&gt; &gt; &gt;, Cons&lt;Queen&lt;S&lt;S&lt;Z&gt; &gt;, Z&gt;, Cons&lt;Queen&lt;S&lt;Z&gt;, S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt;, Cons&lt;Queen&lt;Z, S&lt;S&lt;S&lt;S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt; &gt; &gt; &gt; &gt;, Nil&gt; &gt; &gt; &gt; &gt; &gt; &gt; &gt;]
</code></pre></div>
<p>Broken up and numbered for visibility:</p>
<div><pre><code>  7, 4 : Queen&lt;S&lt;S&lt;S&lt;S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt; &gt; &gt; &gt;, S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt; &gt;,
  6, 6 : Queen&lt;S&lt;S&lt;S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt; &gt; &gt;, S&lt;S&lt;S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt; &gt; &gt; &gt;,
  5, 1 : Queen&lt;S&lt;S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt; &gt;, S&lt;Z&gt; &gt;,
  4, 5 : Queen&lt;S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt;, S&lt;S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt; &gt; &gt;,
  3, 2 : Queen&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt;, S&lt;S&lt;Z&gt; &gt; &gt;,
  2, 0 : Queen&lt;S&lt;S&lt;Z&gt; &gt;, Z&gt;,
  1, 3 : Queen&lt;S&lt;Z&gt;, S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt;,
  0, 7 : Queen&lt;Z, S&lt;S&lt;S&lt;S&lt;S&lt;S&lt;S&lt;Z&gt; &gt; &gt; &gt; &gt; &gt; &gt; &gt;,
</code></pre></div>
<p>And plotted on a chess board:</p>
<div><pre><code>    0 1 2 3 4 5 6 7
   +-+-+-+-+-+-+-+-+
  7|Q| | | | | | | |7
   +-+-+-+-+-+-+-+-+
  6| | | | | | |Q| |6
   +-+-+-+-+-+-+-+-+
  5| | | | |Q| | | |5
   +-+-+-+-+-+-+-+-+
  4| | | | | | | |Q|4
   +-+-+-+-+-+-+-+-+
  3| |Q| | | | | | |3
   +-+-+-+-+-+-+-+-+
  2| | | |Q| | | | |2
   +-+-+-+-+-+-+-+-+
  1| | | | | |Q| | |1
   +-+-+-+-+-+-+-+-+
  0| | |Q| | | | | |0
   +-+-+-+-+-+-+-+-+
    0 1 2 3 4 5 6 7
</code></pre></div>
</article></div></div>||||I||||    Skip to content

    Navigation Menu

    Toggle navigation
          Sign in
            * Product
                        + Actions
                        Automate any workflow
                        + Packages
                        Host and manage packages
                        + Security
                        Find and fix vulnerabilities
                        + Codespaces
                        Instant dev environments
                        + GitHub Copilot
                        Write better code with AI
                        + Code review
                        Manage code changes
                        + Issues
                        Plan and track work
                        + Discussions
                        Collaborate outside of code
                  Explore
                    + All features
                    + Documentation
                    + GitHub Skills
                    + Blog
            * Solutions
                  By size
                    + Enterprise
                    + Teams
                    + Startups
                  By industry
                    + Healthcare
                    + Financial services
                    + Manufacturing
                  By use case
                    + CI/CD & Automation
                    + DevOps
                    + DevSecOps
            * Resources
                  Topics
                    + AI
                    + DevOps
                    + Security
                    + Software Development
                  Explore
                    + Learning Pathways
                    + White papers, Ebooks, Webinars
                    + Customer Stories
                    + Partners
            * Open Source
                        + GitHub Sponsors
                        Fund open source developers
                        + The ReadME Project
                        GitHub community articles
                  Repositories
                    + Topics
                    + Trending
                    + Collections
            * Enterprise
                        + Enterprise platform
                        AI-powered developer platform
                  Available add-ons
                        + Advanced Security
                        Enterprise-grade security features
                        + GitHub Copilot
                        Enterprise-grade AI features
                        + Premium Support
                        Enterprise-grade 24/7 support
            * Pricing
              Search or jump to...

                Search code, repositories, users, issues, pull requests...

                        Search
                          Clear
                        Search syntax tips

                    Provide feedback

                We read every piece of feedback, and take your input very seriously.

                Include my email address so I can be contacted
                Cancel Submit feedback

                    Saved searches

                    Use saved searches to filter your results more quickly

                    Name
                    Query

                  To see all available qualifiers, see our documentation.

                Cancel Create saved search
              Sign in
            Sign up Reseting focus
      You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
            {{ message }}
              tyler569 / template-queens Public
              * Notifications You must be signed in to change notification settings
              * Fork 0
                * Star 2

            An implementation of the N Queens algorithm written entirely in the C++ type system.

              2 stars 0 forks Branches Tags Activity
                  Star
                Notifications You must be signed in to change notification settings
          * Code
          * Issues 0
          * Pull requests 0
          * Actions
          * Projects 0
          * Security
          * Insights
          Additional navigation options
                  * Code
                  * Issues
                  * Pull requests
                  * Actions
                  * Projects
                  * Security
                  * Insights

        tyler569/template-queens

                  This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
                              master
                          Branches Tags
                            Go to file
                        Code

                        Folders and files

                          Name                 Name                   Last commit message    Last commit date
                            Latest commit    
                                             
                                History      
                                             
                                1 Commit     
                                  Makefile             Makefile                                              
                                  README.md            README.md                                             
                                  n_queens.cc          n_queens.cc                                           
                            View all files   
                          

                              Repository files navigation

                                * README

                                N Queens in C++ types

                              This is an implementation of the N Queens algorithm written entirely in the C++ type system using templates. This can be done because C++ templates can be specialized for specific input type arguments, and this provides a simple form of pattern matching that can be used to encode calculation.

                              For example, this is how booleans are defined:

                                struct True {};
                                struct False {};
                                
                                template <typename T>
                                struct Not {};
                                
                                template <>
                                struct Not<True> {
                                    using value = False;
                                };
                                
                                template <>
                                struct Not<False> {
                                    using value = True;
                                };
                                
                                using test = Not<True>; // test is False

                              Notice that at no point did I use any values, but rather True and False are types, and could have been named anything, the important part is the algebra defined by the interactions of those types and Not.

                              As it exists in this repo, the program calculates N Queens on an 8 * 8 chessboard. This can be changed to any N by adjusting the value on line 617 to change solved to, for example, Solution<N6>::value for a 6 * 6 board. Additionally, to get the full list of all solutions, change Solution<N8>::value to Solution<N8>::all_values on the same line.

                              The full program is computed at compile time, and the produced executable only contains the code to print the raw string containing the final result type.

                              I owe a lot of credit to this article, which provided the inspiration and most of the algorithms used. It's also a great read, and I highly reccomend taking a look at it.

                                Results from Solution<N8>::value:

                              8 Queens:

                              Raw output:

                                 int f(T) [with T = Cons<Queen<S<S<S<S<S<S<S<Z> > > > > > >, S<S<S<S<Z> > > > >, Cons<Queen<S<S<S<S<S<S<Z> > > > > >, S<S<S<S<S<S<Z> > > > > > >, Cons<Queen<S<S<S<S<S<Z> > > > >, S<Z> >, Cons<Queen<S<S<S<S<Z> > > >, S<S<S<S<S<Z> > > > > >, Cons<Queen<S<S<S<Z> > >, S<S<Z> > >, Cons<Queen<S<S<Z> >, Z>, Cons<Queen<S<Z>, S<S<S<Z> > > >, Cons<Queen<Z, S<S<S<S<S<S<S<Z> > > > > > > >, Nil> > > > > > > >]
                                

                              Broken up and numbered for visibility:

                                  7, 4 : Queen<S<S<S<S<S<S<S<Z> > > > > > >, S<S<S<S<Z> > > > >,
                                  6, 6 : Queen<S<S<S<S<S<S<Z> > > > > >, S<S<S<S<S<S<Z> > > > > > >,
                                  5, 1 : Queen<S<S<S<S<S<Z> > > > >, S<Z> >,
                                  4, 5 : Queen<S<S<S<S<Z> > > >, S<S<S<S<S<Z> > > > > >,
                                  3, 2 : Queen<S<S<S<Z> > >, S<S<Z> > >,
                                  2, 0 : Queen<S<S<Z> >, Z>,
                                  1, 3 : Queen<S<Z>, S<S<S<Z> > > >,
                                  0, 7 : Queen<Z, S<S<S<S<S<S<S<Z> > > > > > > >,
                                

                              And plotted on a chess board:

                                    0 1 2 3 4 5 6 7
                                   +-+-+-+-+-+-+-+-+
                                  7|Q| | | | | | | |7
                                   +-+-+-+-+-+-+-+-+
                                  6| | | | | | |Q| |6
                                   +-+-+-+-+-+-+-+-+
                                  5| | | | |Q| | | |5
                                   +-+-+-+-+-+-+-+-+
                                  4| | | | | | | |Q|4
                                   +-+-+-+-+-+-+-+-+
                                  3| |Q| | | | | | |3
                                   +-+-+-+-+-+-+-+-+
                                  2| | | |Q| | | | |2
                                   +-+-+-+-+-+-+-+-+
                                  1| | | | | |Q| | |1
                                   +-+-+-+-+-+-+-+-+
                                  0| | |Q| | | | | |0
                                   +-+-+-+-+-+-+-+-+
                                    0 1 2 3 4 5 6 7
                                

                          About

                          An implementation of the N Queens algorithm written entirely in the C++ type system.

                          Resources

                            Readme
                            Activity

                          Stars

                            2 stars

                          Watchers

                            3 watching

                          Forks

                            0 forks
                            Report repository

                        Releases

                          No releases published

                        Packages 0

                          No packages published

                        Languages

                          * C++ 99.7%
                          * Makefile 0.3%

    Footer

        © 2024 GitHub, Inc.

      Footer navigation

        * Terms
        * Privacy
        * Security
        * Status
        * Docs
        * Contact
        * Manage cookies
        * Do not share my personal information
      You can’t perform that action at this time.
GitHub - tyler569/template-queens: An implementation of the N Queens algorithm written entirely in the C++ type system.
https://github.com/tyler569/template-queens
raganwald
2018-08-07T23:22:39Z
<div><div>
    
  
<div>
  <div>
      <p><a href="https://gist.github.com/raganwald"></a>
      </p>
      
    </div>
  <ul>
  </ul>
  
  <ul>


      <li>
          <a href="https://gist.github.com/login?return_to=https%3A%2F%2Fgist.github.com%2Fraganwald%2Fe8896be8f032ba80019fd6a20fc6bb7d">  <span>
      <span>
        
      </span>
    <span>Star</span>
      <span>
          <span>()</span>
          
      </span>
  </span>
</a>

      </li>
        <li>
            <a href="https://gist.github.com/login?return_to=https%3A%2F%2Fgist.github.com%2Fraganwald%2Fe8896be8f032ba80019fd6a20fc6bb7d">  <span>
      <span>
        
      </span>
    <span>Fork</span>
      <span>
          <span>()</span>
          
      </span>
  </span>
</a>

        </li>
  </ul>
</div>

  <ul>
    <li>
      
<div>
      
  </div>
    </li>
    <li>
        


    </li>
  </ul>

<div>
    
<div>
      
  </div>

    <div>
        


    </div>

    
  </div>


  </div><div>
      <p>
    The Eight Queens Problem
  </p>

        <div>

  


  <table>
        <tbody><tr>
          <td></td>
          <td><span>// Computes the twelve "fundamental" solutions to the eight queens problem</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// by filtering the results of the "half-inductive" algorithm.</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>//</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// see http://raganwald.com/2018/08/03/eight-queens.html</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>//</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// search space: 2,750 candidate positions</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>testDiagonals</span> <span>(</span><span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>nesw</span> <span>=</span> <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>nwse</span> <span>=</span> <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>if</span> <span>(</span><span>queens</span><span>.</span><span>length</span> <span>&lt;</span> <span>2</span><span>)</span> <span>return</span> <span>true</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>[</span><span>i</span><span>,</span> <span>j</span><span>]</span> <span>of</span> <span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>if</span> <span>(</span><span>nwse</span><span>[</span><span>i</span> <span>+</span> <span>j</span><span>]</span> <span>!==</span> <span>'.'</span> <span>||</span> <span>nesw</span><span>[</span><span>i</span> <span>+</span> <span>7</span> <span>-</span> <span>j</span><span>]</span> <span>!==</span> <span>'.'</span><span>)</span> <span>return</span> <span>false</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>nwse</span><span>[</span><span>i</span> <span>+</span> <span>j</span><span>]</span> <span>=</span> <span>'x'</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>nesw</span><span>[</span><span>i</span> <span>+</span> <span>7</span> <span>-</span> <span>j</span><span>]</span> <span>=</span> <span>'x'</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>true</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>without</span> <span>=</span> <span>(</span><span>array</span><span>,</span> <span>element</span><span>)</span> <span>=&gt;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>	<span>array</span><span>.</span><span>filter</span><span>(</span><span>x</span> <span>=&gt;</span> <span>x</span> <span>!==</span> <span>element</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>inductive</span> <span>(</span></td>
        </tr>
        <tr>
          <td></td>
          <td>	<span>queens</span> <span>=</span> <span>[</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>candidateColumns</span> <span>=</span> <span>[</span><span>0</span><span>,</span> <span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>,</span> <span>5</span><span>,</span> <span>6</span><span>,</span> <span>7</span><span>]</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>if</span> <span>(</span><span>queens</span><span>.</span><span>length</span> <span>===</span> <span>8</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>yield</span> <span>queens</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span> <span>else</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>const</span> <span>chosenColumn</span> <span>of</span> <span>candidateColumns</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>candidateQueens</span> <span>=</span> <span>queens</span><span>.</span><span>concat</span><span>(</span><span>[</span><span>[</span><span>queens</span><span>.</span><span>length</span><span>,</span> <span>chosenColumn</span><span>]</span><span>]</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>remainingColumns</span> <span>=</span> <span>without</span><span>(</span><span>candidateColumns</span><span>,</span> <span>chosenColumn</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>if</span> <span>(</span><span>testDiagonals</span><span>(</span><span>candidateQueens</span><span>)</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>        <span>yield</span> <span>*</span> <span>inductive</span><span>(</span><span>candidateQueens</span><span>,</span> <span>remainingColumns</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>allColumns</span> <span>=</span> <span>[</span><span>0</span><span>,</span> <span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>,</span> <span>5</span><span>,</span> <span>6</span><span>,</span> <span>7</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>halfInductive</span> <span>(</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>column</span> <span>of</span> <span>[</span><span>0</span><span>,</span> <span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>]</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>candidateQueens</span> <span>=</span> <span>[</span><span>[</span><span>0</span><span>,</span> <span>column</span><span>]</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>remainingColumns</span> <span>=</span> <span>without</span><span>(</span><span>allColumns</span><span>,</span> <span>column</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>yield</span> <span>*</span> <span>inductive</span><span>(</span><span>candidateQueens</span><span>,</span> <span>remainingColumns</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>verticalReflection</span> <span>(</span><span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>queens</span><span>.</span><span>map</span><span>(</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>(</span><span>[</span><span>row</span><span>,</span> <span>col</span><span>]</span><span>)</span> <span>=&gt;</span> <span>[</span><span>row</span><span>,</span> <span>7</span> <span>-</span> <span>col</span><span>]</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>sortQueens</span> <span>=</span> <span>queens</span> <span>=&gt;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>queens</span><span>.</span><span>reduce</span><span>(</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>(</span><span>acc</span><span>,</span> <span>[</span><span>row</span><span>,</span> <span>col</span><span>]</span><span>)</span> <span>=&gt;</span> <span>(</span><span>acc</span><span>[</span><span>row</span><span>]</span> <span>=</span> <span>[</span><span>row</span><span>,</span> <span>col</span><span>]</span><span>,</span> <span>acc</span><span>)</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>null</span><span>,</span> <span>null</span><span>,</span> <span>null</span><span>,</span> <span>null</span><span>,</span> <span>null</span><span>,</span> <span>null</span><span>,</span> <span>null</span><span>,</span> <span>null</span><span>]</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>rotateRight</span> <span>=</span> <span>queens</span> <span>=&gt;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>sortQueens</span><span>(</span> <span>queens</span><span>.</span><span>map</span><span>(</span><span>(</span><span>[</span><span>row</span><span>,</span> <span>col</span><span>]</span><span>)</span> <span>=&gt;</span> <span>[</span><span>col</span><span>,</span> <span>7</span> <span>-</span> <span>row</span><span>]</span><span>)</span> <span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>rotations</span> <span>=</span> <span>solution</span> <span>=&gt;</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>rotations</span> <span>=</span> <span>[</span><span>null</span><span>,</span> <span>null</span><span>,</span> <span>null</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>let</span> <span>temp</span> <span>=</span> <span>rotateRight</span><span>(</span><span>solution</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>rotations</span><span>[</span><span>0</span><span>]</span> <span>=</span> <span>temp</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>temp</span> <span>=</span> <span>rotateRight</span><span>(</span><span>temp</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>rotations</span><span>[</span><span>1</span><span>]</span> <span>=</span> <span>temp</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>temp</span> <span>=</span> <span>rotateRight</span><span>(</span><span>temp</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>rotations</span><span>[</span><span>2</span><span>]</span> <span>=</span> <span>temp</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>rotations</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>indexQueens</span> <span>=</span> <span>queens</span> <span>=&gt;</span> <span>queens</span><span>.</span><span>map</span><span>(</span><span>(</span><span>[</span><span>row</span><span>,</span> <span>col</span><span>]</span><span>)</span> <span>=&gt;</span> <span>`<span><span>${</span><span>row</span><span>}</span></span>,<span><span>${</span><span>col</span><span>}</span></span>`</span><span>)</span><span>.</span><span>join</span><span>(</span><span>' '</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>fundamentals</span> <span>(</span><span>solutions</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>solutionsSoFar</span> <span>=</span> <span>new</span> <span>Set</span><span>(</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>solution</span> <span>of</span> <span>solutions</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>iSolution</span> <span>=</span> <span>indexQueens</span><span>(</span><span>solution</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>if</span> <span>(</span><span>solutionsSoFar</span><span>.</span><span>has</span><span>(</span><span>iSolution</span><span>)</span><span>)</span> <span>continue</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>solutionsSoFar</span><span>.</span><span>add</span><span>(</span><span>iSolution</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>rSolutions</span> <span>=</span> <span>rotations</span><span>(</span><span>solution</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>irSolutions</span> <span>=</span> <span>rSolutions</span><span>.</span><span>map</span><span>(</span><span>indexQueens</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>let</span> <span>irSolution</span> <span>of</span> <span>irSolutions</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>solutionsSoFar</span><span>.</span><span>add</span><span>(</span><span>irSolution</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>vSolution</span> <span>=</span> <span>verticalReflection</span><span>(</span><span>solution</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>rvSolutions</span> <span>=</span> <span>rotations</span><span>(</span><span>vSolution</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>irvSolutions</span> <span>=</span> <span>rvSolutions</span><span>.</span><span>map</span><span>(</span><span>indexQueens</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>let</span> <span>irvSolution</span> <span>of</span> <span>irvSolutions</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>solutionsSoFar</span><span>.</span><span>add</span><span>(</span><span>irvSolution</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>yield</span> <span>solution</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>mapWith</span> <span>(</span><span>mapFunction</span><span>,</span> <span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>element</span> <span>of</span> <span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>yield</span> <span>mapFunction</span><span>(</span><span>element</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>niceDiagramOf</span> <span>(</span><span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>board</span> <span>=</span> <span>[</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>,</span> <span>"⬛️"</span><span>,</span> <span>"⬜️"</span><span>]</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>[</span><span>row</span><span>,</span> <span>col</span><span>]</span> <span>of</span> <span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>board</span><span>[</span><span>7</span> <span>-</span> <span>row</span><span>]</span><span>[</span><span>col</span><span>]</span> <span>=</span> <span>"👸🏾"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>board</span><span>.</span><span>map</span><span>(</span><span>row</span> <span>=&gt;</span> <span>row</span><span>.</span><span>join</span><span>(</span><span>''</span><span>)</span><span>)</span><span>.</span><span>join</span><span>(</span><span>"\n"</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>mapWith</span><span>(</span><span>niceDiagramOf</span><span>,</span> <span>fundamentals</span><span>(</span><span>halfInductive</span><span>(</span><span>)</span><span>)</span><span>)</span></td>
        </tr>
  </tbody></table>
</div>

        <div>

  


  <table>
        <tbody><tr>
          <td></td>
          <td><span>// Computes the all 92 solutions to the eight queens problem</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// by computing half of the results of the inductive solution </span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// and then adding their vertical reflections.</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>//</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// see http://raganwald.com/2018/08/03/eight-queens.html</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>//</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// search space: 2,750 candidate positions</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>testDiagonals</span> <span>(</span><span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>nesw</span> <span>=</span> <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>nwse</span> <span>=</span> <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>if</span> <span>(</span><span>queens</span><span>.</span><span>length</span> <span>&lt;</span> <span>2</span><span>)</span> <span>return</span> <span>true</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>[</span><span>i</span><span>,</span> <span>j</span><span>]</span> <span>of</span> <span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>if</span> <span>(</span><span>nwse</span><span>[</span><span>i</span> <span>+</span> <span>j</span><span>]</span> <span>!==</span> <span>'.'</span> <span>||</span> <span>nesw</span><span>[</span><span>i</span> <span>+</span> <span>7</span> <span>-</span> <span>j</span><span>]</span> <span>!==</span> <span>'.'</span><span>)</span> <span>return</span> <span>false</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>nwse</span><span>[</span><span>i</span> <span>+</span> <span>j</span><span>]</span> <span>=</span> <span>'x'</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>nesw</span><span>[</span><span>i</span> <span>+</span> <span>7</span> <span>-</span> <span>j</span><span>]</span> <span>=</span> <span>'x'</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>true</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>without</span> <span>=</span> <span>(</span><span>array</span><span>,</span> <span>element</span><span>)</span> <span>=&gt;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>	<span>array</span><span>.</span><span>filter</span><span>(</span><span>x</span> <span>=&gt;</span> <span>x</span> <span>!==</span> <span>element</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>inductive</span> <span>(</span></td>
        </tr>
        <tr>
          <td></td>
          <td>	<span>queens</span> <span>=</span> <span>[</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>candidateColumns</span> <span>=</span> <span>[</span><span>0</span><span>,</span> <span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>,</span> <span>5</span><span>,</span> <span>6</span><span>,</span> <span>7</span><span>]</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>if</span> <span>(</span><span>queens</span><span>.</span><span>length</span> <span>===</span> <span>8</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>yield</span> <span>queens</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span> <span>else</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>const</span> <span>chosenColumn</span> <span>of</span> <span>candidateColumns</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>candidateQueens</span> <span>=</span> <span>queens</span><span>.</span><span>concat</span><span>(</span><span>[</span><span>[</span><span>queens</span><span>.</span><span>length</span><span>,</span> <span>chosenColumn</span><span>]</span><span>]</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>remainingColumns</span> <span>=</span> <span>without</span><span>(</span><span>candidateColumns</span><span>,</span> <span>chosenColumn</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>if</span> <span>(</span><span>testDiagonals</span><span>(</span><span>candidateQueens</span><span>)</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>        <span>yield</span> <span>*</span> <span>inductive</span><span>(</span><span>candidateQueens</span><span>,</span> <span>remainingColumns</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>allColumns</span> <span>=</span> <span>[</span><span>0</span><span>,</span> <span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>,</span> <span>5</span><span>,</span> <span>6</span><span>,</span> <span>7</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>halfInductive</span> <span>(</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>column</span> <span>of</span> <span>[</span><span>0</span><span>,</span> <span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>]</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>candidateQueens</span> <span>=</span> <span>[</span><span>[</span><span>0</span><span>,</span> <span>column</span><span>]</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>remainingColumns</span> <span>=</span> <span>without</span><span>(</span><span>allColumns</span><span>,</span> <span>column</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>yield</span> <span>*</span> <span>inductive</span><span>(</span><span>candidateQueens</span><span>,</span> <span>remainingColumns</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>verticalReflection</span> <span>(</span><span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>queens</span><span>.</span><span>map</span><span>(</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>(</span><span>[</span><span>row</span><span>,</span> <span>col</span><span>]</span><span>)</span> <span>=&gt;</span> <span>[</span><span>row</span><span>,</span> <span>7</span> <span>-</span> <span>col</span><span>]</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>flatMapWith</span> <span>(</span><span>fn</span><span>,</span> <span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>element</span> <span>of</span> <span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>yield</span> <span>*</span> <span>fn</span><span>(</span><span>element</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>withReflections</span> <span>=</span> <span>flatMapWith</span><span>(</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>queens</span> <span>=&gt;</span> <span>[</span><span>queens</span><span>,</span> <span>verticalReflection</span><span>(</span><span>queens</span><span>)</span><span>]</span><span>,</span> <span>halfInductive</span><span>(</span><span>)</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>Array</span><span>.</span><span>from</span><span>(</span><span>withReflections</span><span>)</span><span>.</span><span>length</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>//=&gt; 92</span></td>
        </tr>
  </tbody></table>
</div>

        <div>

  


  <table>
        <tbody><tr>
          <td></td>
          <td><span>// Computes the all 92 solutions to the eight queens problem</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// by testing partial solutions to the "rooks" algorithm</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// as they are created, thus pruning subtrees when possible.</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>//</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// see http://raganwald.com/2018/08/03/eight-queens.html</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>//</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// search space: 5,508 candidate positions</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>testDiagonals</span> <span>(</span><span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>nesw</span> <span>=</span> <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>nwse</span> <span>=</span> <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>if</span> <span>(</span><span>queens</span><span>.</span><span>length</span> <span>&lt;</span> <span>2</span><span>)</span> <span>return</span> <span>true</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>[</span><span>i</span><span>,</span> <span>j</span><span>]</span> <span>of</span> <span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>if</span> <span>(</span><span>nwse</span><span>[</span><span>i</span> <span>+</span> <span>j</span><span>]</span> <span>!==</span> <span>'.'</span> <span>||</span> <span>nesw</span><span>[</span><span>i</span> <span>+</span> <span>7</span> <span>-</span> <span>j</span><span>]</span> <span>!==</span> <span>'.'</span><span>)</span> <span>return</span> <span>false</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>nwse</span><span>[</span><span>i</span> <span>+</span> <span>j</span><span>]</span> <span>=</span> <span>'x'</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>nesw</span><span>[</span><span>i</span> <span>+</span> <span>7</span> <span>-</span> <span>j</span><span>]</span> <span>=</span> <span>'x'</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>true</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>without</span> <span>=</span> <span>(</span><span>array</span><span>,</span> <span>element</span><span>)</span> <span>=&gt;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>	<span>array</span><span>.</span><span>filter</span><span>(</span><span>x</span> <span>=&gt;</span> <span>x</span> <span>!==</span> <span>element</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>inductive</span> <span>(</span></td>
        </tr>
        <tr>
          <td></td>
          <td>	<span>queens</span> <span>=</span> <span>[</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>candidateColumns</span> <span>=</span> <span>[</span><span>0</span><span>,</span> <span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>,</span> <span>5</span><span>,</span> <span>6</span><span>,</span> <span>7</span><span>]</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>if</span> <span>(</span><span>queens</span><span>.</span><span>length</span> <span>===</span> <span>8</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>yield</span> <span>queens</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span> <span>else</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>const</span> <span>chosenColumn</span> <span>of</span> <span>candidateColumns</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>candidateQueens</span> <span>=</span> <span>queens</span><span>.</span><span>concat</span><span>(</span><span>[</span><span>[</span><span>queens</span><span>.</span><span>length</span><span>,</span> <span>chosenColumn</span><span>]</span><span>]</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>remainingColumns</span> <span>=</span> <span>without</span><span>(</span><span>candidateColumns</span><span>,</span> <span>chosenColumn</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>if</span> <span>(</span><span>testDiagonals</span><span>(</span><span>candidateQueens</span><span>)</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>        <span>yield</span> <span>*</span> <span>inductive</span><span>(</span><span>candidateQueens</span><span>,</span> <span>remainingColumns</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>Array</span><span>.</span><span>from</span><span>(</span><span>inductive</span><span>(</span><span>)</span><span>)</span><span>.</span><span>length</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>//=&gt; 92</span></td>
        </tr>
  </tbody></table>
</div>

        <div>

  


  <table>
        <tbody><tr>
          <td></td>
          <td><span>// Computes the all 92 solutions to the eight queens problem</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// by generating all of the solutions to the eight rooks</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// problem using permutations, and then filtering them</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// by testing for diagonal attacks.</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>//</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// see http://raganwald.com/2018/08/03/eight-queens.html</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>//</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// search space: 40,320 candidate positions</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>diagramOf</span> <span>(</span><span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>board</span> <span>=</span> <span>[</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>[</span><span>i</span><span>,</span> <span>j</span><span>]</span> <span>of</span> <span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>board</span><span>[</span><span>i</span><span>]</span><span>[</span><span>j</span><span>]</span> <span>=</span> <span>"Q"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>board</span><span>.</span><span>map</span><span>(</span><span>row</span> <span>=&gt;</span> <span>row</span><span>.</span><span>join</span><span>(</span><span>''</span><span>)</span><span>)</span><span>.</span><span>join</span><span>(</span><span>"\n"</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>test</span> <span>(</span><span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>board</span> <span>=</span> <span>[</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>[</span><span>i</span><span>,</span> <span>j</span><span>]</span> <span>of</span> <span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>if</span> <span>(</span><span>board</span><span>[</span><span>i</span><span>]</span><span>[</span><span>j</span><span>]</span> <span>!=</span> <span>'.'</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>// square is occupied or threatened</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>return</span> <span>false</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>let</span> <span>k</span> <span>=</span> <span>0</span><span>;</span> <span>k</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>k</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>// fill row and column</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>board</span><span>[</span><span>i</span><span>]</span><span>[</span><span>k</span><span>]</span> <span>=</span> <span>board</span><span>[</span><span>k</span><span>]</span><span>[</span><span>j</span><span>]</span> <span>=</span> <span>"x"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>vOffset</span> <span>=</span> <span>k</span><span>-</span><span>i</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>hDiagonal1</span> <span>=</span> <span>j</span> <span>-</span> <span>vOffset</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>hDiagonal2</span> <span>=</span> <span>j</span> <span>+</span> <span>vOffset</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>// fill diagonals</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>if</span> <span>(</span><span>hDiagonal1</span> <span>&gt;=</span> <span>0</span> <span>&amp;&amp;</span> <span>hDiagonal1</span> <span>&lt;=</span> <span>7</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>        <span>board</span><span>[</span><span>k</span><span>]</span><span>[</span><span>hDiagonal1</span><span>]</span> <span>=</span> <span>"x"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>if</span> <span>(</span><span>hDiagonal2</span> <span>&gt;=</span> <span>0</span> <span>&amp;&amp;</span> <span>hDiagonal2</span> <span>&lt;=</span> <span>7</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>        <span>board</span><span>[</span><span>k</span><span>]</span><span>[</span><span>hDiagonal2</span><span>]</span> <span>=</span> <span>"x"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>board</span><span>[</span><span>i</span><span>]</span><span>[</span><span>j</span><span>]</span> <span>=</span> <span>"Q"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>true</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>filterWith</span> <span>(</span><span>predicateFunction</span><span>,</span> <span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>element</span> <span>of</span> <span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>if</span> <span>(</span><span>predicateFunction</span><span>(</span><span>element</span><span>)</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>yield</span> <span>element</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>first</span> <span>(</span><span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>[</span><span>value</span><span>]</span> <span>=</span> <span>iterable</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>value</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>mapWith</span> <span>(</span><span>mapFunction</span><span>,</span> <span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>element</span> <span>of</span> <span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>yield</span> <span>mapFunction</span><span>(</span><span>element</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>permutations</span> <span>(</span><span>arr</span><span>,</span> <span>prefix</span> <span>=</span> <span>[</span><span>]</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>if</span> <span>(</span><span>arr</span><span>.</span><span>length</span> <span>===</span> <span>1</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>yield</span> <span>prefix</span><span>.</span><span>concat</span><span>(</span><span>arr</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span> <span>else</span> <span>if</span> <span>(</span><span>arr</span><span>.</span><span>length</span> <span>&gt;</span> <span>1</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>let</span> <span>i</span> <span>=</span> <span>0</span><span>;</span> <span>i</span> <span>&lt;</span> <span>arr</span><span>.</span><span>length</span><span>;</span> <span>++</span><span>i</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>chosen</span> <span>=</span> <span>arr</span><span>[</span><span>i</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>remainder</span> <span>=</span> <span>arr</span><span>.</span><span>slice</span><span>(</span><span>0</span><span>,</span> <span>i</span><span>)</span><span>.</span><span>concat</span><span>(</span><span>arr</span><span>.</span><span>slice</span><span>(</span><span>i</span><span>+</span><span>1</span><span>,</span> <span>arr</span><span>.</span><span>length</span><span>)</span><span>)</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>yield</span> <span>*</span> <span>permutations</span><span>(</span><span>remainder</span><span>,</span> <span>prefix</span><span>.</span><span>concat</span><span>(</span><span>[</span><span>chosen</span><span>]</span><span>)</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>solutionsToEightRooks</span> <span>=</span> <span>mapWith</span><span>(</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>ii</span> <span>=&gt;</span> <span>ii</span><span>.</span><span>map</span><span>(</span><span>(</span><span>i</span><span>,</span> <span>j</span><span>)</span> <span>=&gt;</span> <span>[</span><span>i</span><span>,</span> <span>j</span><span>]</span><span>)</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>permutations</span><span>(</span><span>[</span><span>0</span><span>,</span> <span>1</span><span>,</span> <span>2</span><span>,</span> <span>3</span><span>,</span> <span>4</span><span>,</span> <span>5</span><span>,</span> <span>6</span><span>,</span> <span>7</span><span>]</span><span>)</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>solutionsToEightQueens</span> <span>=</span> <span>filterWith</span><span>(</span><span>test</span><span>,</span> <span>solutionsToEightRooks</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>diagramOf</span><span>(</span><span>first</span><span>(</span><span>solutionsToEightQueens</span><span>)</span><span>)</span></td>
        </tr>
  </tbody></table>
</div>

        <div>

  


  <table>
        <tbody><tr>
          <td></td>
          <td><span>// Computes the all 92 solutions to the eight queens problem</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// by computing all of the ways eight queens can be arranged</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// on the board using 64 choose 8, then filtering them</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// for horizontal, vertical, and diagonal attacks.</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>//</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// see http://raganwald.com/2018/08/03/eight-queens.html</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>//</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// search space: 4,426,165,368 candidate positions</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>diagramOf</span> <span>(</span><span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>board</span> <span>=</span> <span>[</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>[</span><span>i</span><span>,</span> <span>j</span><span>]</span> <span>of</span> <span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>board</span><span>[</span><span>i</span><span>]</span><span>[</span><span>j</span><span>]</span> <span>=</span> <span>"Q"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>board</span><span>.</span><span>map</span><span>(</span><span>row</span> <span>=&gt;</span> <span>row</span><span>.</span><span>join</span><span>(</span><span>''</span><span>)</span><span>)</span><span>.</span><span>join</span><span>(</span><span>"\n"</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>test</span> <span>(</span><span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>board</span> <span>=</span> <span>[</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>[</span><span>i</span><span>,</span> <span>j</span><span>]</span> <span>of</span> <span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>if</span> <span>(</span><span>board</span><span>[</span><span>i</span><span>]</span><span>[</span><span>j</span><span>]</span> <span>!=</span> <span>'.'</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>// square is occupied or threatened</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>return</span> <span>false</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>let</span> <span>k</span> <span>=</span> <span>0</span><span>;</span> <span>k</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>k</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>// fill row and column</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>board</span><span>[</span><span>i</span><span>]</span><span>[</span><span>k</span><span>]</span> <span>=</span> <span>board</span><span>[</span><span>k</span><span>]</span><span>[</span><span>j</span><span>]</span> <span>=</span> <span>"x"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>vOffset</span> <span>=</span> <span>k</span><span>-</span><span>i</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>hDiagonal1</span> <span>=</span> <span>j</span> <span>-</span> <span>vOffset</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>hDiagonal2</span> <span>=</span> <span>j</span> <span>+</span> <span>vOffset</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>// fill diagonals</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>if</span> <span>(</span><span>hDiagonal1</span> <span>&gt;=</span> <span>0</span> <span>&amp;&amp;</span> <span>hDiagonal1</span> <span>&lt;=</span> <span>7</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>        <span>board</span><span>[</span><span>k</span><span>]</span><span>[</span><span>hDiagonal1</span><span>]</span> <span>=</span> <span>"x"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>if</span> <span>(</span><span>hDiagonal2</span> <span>&gt;=</span> <span>0</span> <span>&amp;&amp;</span> <span>hDiagonal2</span> <span>&lt;=</span> <span>7</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>        <span>board</span><span>[</span><span>k</span><span>]</span><span>[</span><span>hDiagonal2</span><span>]</span> <span>=</span> <span>"x"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>board</span><span>[</span><span>i</span><span>]</span><span>[</span><span>j</span><span>]</span> <span>=</span> <span>"Q"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>true</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>filterWith</span> <span>(</span><span>predicateFunction</span><span>,</span> <span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>element</span> <span>of</span> <span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>if</span> <span>(</span><span>predicateFunction</span><span>(</span><span>element</span><span>)</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>yield</span> <span>element</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>first</span> <span>(</span><span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>[</span><span>value</span><span>]</span> <span>=</span> <span>iterable</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>value</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>mapWith</span> <span>(</span><span>mapFunction</span><span>,</span> <span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>element</span> <span>of</span> <span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>yield</span> <span>mapFunction</span><span>(</span><span>element</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>choose</span> <span>(</span><span>n</span><span>,</span> <span>k</span><span>,</span> <span>offset</span> <span>=</span> <span>0</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>if</span> <span>(</span><span>k</span> <span>===</span> <span>1</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>let</span> <span>i</span> <span>=</span> <span>0</span><span>;</span> <span>i</span> <span>&lt;=</span> <span>(</span><span>n</span> <span>-</span> <span>k</span><span>)</span><span>;</span> <span>++</span><span>i</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>yield</span> <span>[</span><span>i</span> <span>+</span> <span>offset</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span> <span>else</span> <span>if</span> <span>(</span><span>k</span> <span>&gt;</span> <span>1</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>let</span> <span>i</span> <span>=</span> <span>0</span><span>;</span> <span>i</span> <span>&lt;=</span> <span>(</span><span>n</span> <span>-</span> <span>k</span><span>)</span><span>;</span> <span>++</span><span>i</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>remaining</span> <span>=</span> <span>n</span> <span>-</span> <span>i</span> <span>-</span> <span>1</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>otherChoices</span> <span>=</span> <span>choose</span><span>(</span><span>remaining</span><span>,</span> <span>k</span> <span>-</span> <span>1</span><span>,</span> <span>i</span> <span>+</span> <span>offset</span> <span>+</span> <span>1</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>yield</span> <span>*</span> <span>mapWith</span><span>(</span><span>x</span> <span>=&gt;</span> <span>[</span><span>i</span> <span>+</span> <span>offset</span><span>]</span><span>.</span><span>concat</span><span>(</span><span>x</span><span>)</span><span>,</span> <span>otherChoices</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>numberToPosition</span> <span>=</span> <span>n</span> <span>=&gt;</span> <span>[</span><span>Math</span><span>.</span><span>floor</span><span>(</span><span>n</span><span>/</span><span>8</span><span>)</span><span>,</span> <span>n</span> <span>%</span> <span>8</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>numbersToPositions</span> <span>=</span> <span>queenNumbers</span> <span>=&gt;</span> <span>queenNumbers</span><span>.</span><span>map</span><span>(</span><span>numberToPosition</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>combinationCandidates</span> <span>=</span> <span>mapWith</span><span>(</span><span>numbersToPositions</span><span>,</span> <span>choose</span><span>(</span><span>64</span><span>,</span> <span>8</span><span>)</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>solutionsToEightQueens</span> <span>=</span> <span>filterWith</span><span>(</span><span>test</span><span>,</span> <span>combinationCandidates</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>diagramOf</span><span>(</span><span>first</span><span>(</span><span>solutionsToEightQueens</span><span>)</span><span>)</span></td>
        </tr>
  </tbody></table>
</div>

        <div>

  


  <table>
        <tbody><tr>
          <td></td>
          <td><span>// Computes the all 92 solutions to the eight queens problem</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// by computing all of the possible arrangements of eight</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// chess squares (64^8), then filtering them</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// for horizontal, vertical, and diagonal attacks.</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>//</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// see http://raganwald.com/2018/08/03/eight-queens.html</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>//</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>// search space: 281,474,976,710,656 candidate positions</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>diagramOf</span> <span>(</span><span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>board</span> <span>=</span> <span>[</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>[</span><span>i</span><span>,</span> <span>j</span><span>]</span> <span>of</span> <span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>board</span><span>[</span><span>i</span><span>]</span><span>[</span><span>j</span><span>]</span> <span>=</span> <span>"Q"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>board</span><span>.</span><span>map</span><span>(</span><span>row</span> <span>=&gt;</span> <span>row</span><span>.</span><span>join</span><span>(</span><span>''</span><span>)</span><span>)</span><span>.</span><span>join</span><span>(</span><span>"\n"</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>mostPessimumGenerator</span> <span>(</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>let</span> <span>i0</span> <span>=</span> <span>0</span><span>;</span> <span>i0</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>i0</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>let</span> <span>j0</span> <span>=</span> <span>0</span><span>;</span> <span>j0</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>j0</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>for</span> <span>(</span><span>let</span> <span>i1</span> <span>=</span> <span>0</span><span>;</span> <span>i1</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>i1</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>        <span>for</span> <span>(</span><span>let</span> <span>j1</span> <span>=</span> <span>0</span><span>;</span> <span>j1</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>j1</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>          <span>for</span> <span>(</span><span>let</span> <span>i2</span> <span>=</span> <span>0</span><span>;</span> <span>i2</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>i2</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>            <span>for</span> <span>(</span><span>let</span> <span>j2</span> <span>=</span> <span>0</span><span>;</span> <span>j2</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>j2</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>              <span>for</span> <span>(</span><span>let</span> <span>i3</span> <span>=</span> <span>0</span><span>;</span> <span>i3</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>i3</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                <span>for</span> <span>(</span><span>let</span> <span>j3</span> <span>=</span> <span>0</span><span>;</span> <span>j3</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>j3</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                  <span>for</span> <span>(</span><span>let</span> <span>i4</span> <span>=</span> <span>0</span><span>;</span> <span>i4</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>i4</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                    <span>for</span> <span>(</span><span>let</span> <span>j4</span> <span>=</span> <span>0</span><span>;</span> <span>j4</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>j4</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                      <span>for</span> <span>(</span><span>let</span> <span>i5</span> <span>=</span> <span>0</span><span>;</span> <span>i5</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>i5</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                        <span>for</span> <span>(</span><span>let</span> <span>j5</span> <span>=</span> <span>0</span><span>;</span> <span>j5</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>j5</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                          <span>for</span> <span>(</span><span>let</span> <span>i6</span> <span>=</span> <span>0</span><span>;</span> <span>i6</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>i6</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                            <span>for</span> <span>(</span><span>let</span> <span>j6</span> <span>=</span> <span>0</span><span>;</span> <span>j6</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>j6</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                              <span>for</span> <span>(</span><span>let</span> <span>i7</span> <span>=</span> <span>0</span><span>;</span> <span>i7</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>i7</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                                <span>for</span> <span>(</span><span>let</span> <span>j7</span> <span>=</span> <span>0</span><span>;</span> <span>j7</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>j7</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                                  <span>const</span> <span>queens</span> <span>=</span> <span>[</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                                    <span>[</span><span>i0</span><span>,</span> <span>j0</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                                    <span>[</span><span>i1</span><span>,</span> <span>j1</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                                    <span>[</span><span>i2</span><span>,</span> <span>j2</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                                    <span>[</span><span>i3</span><span>,</span> <span>j3</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                                    <span>[</span><span>i4</span><span>,</span> <span>j4</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                                    <span>[</span><span>i5</span><span>,</span> <span>j5</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                                    <span>[</span><span>i6</span><span>,</span> <span>j6</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                                    <span>[</span><span>i7</span><span>,</span> <span>j7</span><span>]</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                                  <span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>                                  <span>yield</span> <span>queens</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                                <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                              <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                            <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                          <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                        <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                      <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>                <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>              <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>            <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>          <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>        <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>test</span> <span>(</span><span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>board</span> <span>=</span> <span>[</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>[</span><span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>,</span> <span>"."</span><span>]</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>[</span><span>i</span><span>,</span> <span>j</span><span>]</span> <span>of</span> <span>queens</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>if</span> <span>(</span><span>board</span><span>[</span><span>i</span><span>]</span><span>[</span><span>j</span><span>]</span> <span>!=</span> <span>'.'</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>// square is occupied or threatened</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>return</span> <span>false</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>let</span> <span>k</span> <span>=</span> <span>0</span><span>;</span> <span>k</span> <span>&lt;=</span> <span>7</span><span>;</span> <span>++</span><span>k</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>// fill row and column</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>board</span><span>[</span><span>i</span><span>]</span><span>[</span><span>k</span><span>]</span> <span>=</span> <span>board</span><span>[</span><span>k</span><span>]</span><span>[</span><span>j</span><span>]</span> <span>=</span> <span>"x"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>vOffset</span> <span>=</span> <span>k</span><span>-</span><span>i</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>hDiagonal1</span> <span>=</span> <span>j</span> <span>-</span> <span>vOffset</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>hDiagonal2</span> <span>=</span> <span>j</span> <span>+</span> <span>vOffset</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>// fill diagonals</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>if</span> <span>(</span><span>hDiagonal1</span> <span>&gt;=</span> <span>0</span> <span>&amp;&amp;</span> <span>hDiagonal1</span> <span>&lt;=</span> <span>7</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>        <span>board</span><span>[</span><span>k</span><span>]</span><span>[</span><span>hDiagonal1</span><span>]</span> <span>=</span> <span>"x"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>if</span> <span>(</span><span>hDiagonal2</span> <span>&gt;=</span> <span>0</span> <span>&amp;&amp;</span> <span>hDiagonal2</span> <span>&lt;=</span> <span>7</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>        <span>board</span><span>[</span><span>k</span><span>]</span><span>[</span><span>hDiagonal2</span><span>]</span> <span>=</span> <span>"x"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>board</span><span>[</span><span>i</span><span>]</span><span>[</span><span>j</span><span>]</span> <span>=</span> <span>"Q"</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>true</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>filterWith</span> <span>(</span><span>predicateFunction</span><span>,</span> <span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>for</span> <span>(</span><span>const</span> <span>element</span> <span>of</span> <span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>if</span> <span>(</span><span>predicateFunction</span><span>(</span><span>element</span><span>)</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>yield</span> <span>element</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>first</span> <span>(</span><span>iterable</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>const</span> <span>[</span><span>value</span><span>]</span> <span>=</span> <span>iterable</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>return</span> <span>value</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>const</span> <span>solutionsToEightQueens</span> <span>=</span> <span>filterWith</span><span>(</span><span>test</span><span>,</span> <span>mostPessimumGenerator</span><span>(</span><span>)</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>diagramOf</span><span>(</span><span>first</span><span>(</span><span>solutionsToEightQueens</span><span>)</span><span>)</span></td>
        </tr>
  </tbody></table>
</div>

        <div>

  


  <table>
        <tbody><tr>
          <td></td>
          <td><span>const</span> <span>OCCUPATION_HELPER</span> <span>=</span> <span>Symbol</span><span>(</span><span>"occupationHelper"</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>class</span> <span>Board</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>constructor</span> <span>(</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>this</span><span>.</span><span>threats</span> <span>=</span> <span>[</span></td>
        </tr>
        <tr>
          <td></td>
          <td>       <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>       <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>       <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>       <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>       <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>       <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>       <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span></td>
        </tr>
        <tr>
          <td></td>
          <td>       <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span><span>,</span>  <span>0</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>this</span><span>.</span><span>queenIndices</span> <span>=</span> <span>[</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  </td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>isValid</span> <span>(</span><span>index</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>return</span> <span>index</span> <span>&gt;=</span> <span>0</span> <span>&amp;&amp;</span> <span>index</span> <span>&lt;=</span> <span>63</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  </td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>isAvailable</span> <span>(</span><span>index</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>return</span> <span>this</span><span>.</span><span>threats</span><span>[</span><span>index</span><span>]</span> <span>===</span> <span>0</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  </td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>isEmpty</span> <span>(</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>return</span> <span>this</span><span>.</span><span>queenIndices</span><span>.</span><span>length</span> <span>===</span> <span>0</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  </td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>isOccupiable</span> <span>(</span><span>index</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>if</span> <span>(</span><span>this</span><span>.</span><span>isEmpty</span><span>(</span><span>)</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>return</span> <span>this</span><span>.</span><span>isValid</span><span>(</span><span>index</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span> <span>else</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>return</span> <span>this</span><span>.</span><span>isValid</span><span>(</span><span>index</span><span>)</span> <span>&amp;&amp;</span> <span>index</span> <span>&gt;</span> <span>this</span><span>.</span><span>lastQueen</span><span>(</span><span>)</span> <span>&amp;&amp;</span> <span>this</span><span>.</span><span>isAvailable</span><span>(</span><span>index</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  </td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>numberOfQueens</span> <span>(</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>return</span> <span>this</span><span>.</span><span>queenIndices</span><span>.</span><span>length</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  </td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>hasQueens</span> <span>(</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>return</span> <span>this</span><span>.</span><span>numberOfQueens</span><span>(</span><span>)</span> <span>&gt;</span> <span>0</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  </td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>queens</span> <span>(</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>return</span> <span>this</span><span>.</span><span>queenIndices</span><span>.</span><span>map</span><span>(</span><span>index</span> <span>=&gt;</span> <span>[</span><span>Math</span><span>.</span><span>floor</span><span>(</span><span>index</span> <span>/</span> <span>8</span><span>)</span><span>,</span> <span>index</span> <span>%</span> <span>8</span><span>]</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>lastQueen</span> <span>(</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>if</span> <span>(</span><span>this</span><span>.</span><span>queenIndices</span><span>.</span><span>length</span> <span>&gt;</span> <span>0</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>return</span> <span>this</span><span>.</span><span>queenIndices</span><span>[</span><span>this</span><span>.</span><span>queenIndices</span><span>.</span><span>length</span> <span>-</span> <span>1</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>*</span> <span>availableIndices</span> <span>(</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>let</span> <span>index</span> <span>=</span> <span>(</span><span>this</span><span>.</span><span>isEmpty</span><span>(</span><span>)</span> ? <span>0</span> : <span>this</span><span>.</span><span>lastQueen</span><span>(</span><span>)</span> <span>+</span> <span>1</span><span>)</span><span>;</span> <span>index</span> <span>&lt;=</span> <span>63</span><span>;</span> <span>++</span><span>index</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>if</span> <span>(</span><span>this</span><span>.</span><span>isAvailable</span><span>(</span><span>index</span><span>)</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>        <span>yield</span> <span>index</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  </td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>[</span><span>OCCUPATION_HELPER</span><span>]</span> <span>(</span><span>index</span><span>,</span> <span>action</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>[</span><span>row</span><span>,</span> <span>col</span><span>]</span> <span>=</span> <span>[</span><span>Math</span><span>.</span><span>floor</span><span>(</span><span>index</span> <span>/</span> <span>8</span><span>)</span><span>,</span> <span>index</span> <span>%</span> <span>8</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    </td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>// the rest of the row</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>endOfTheRow</span> <span>=</span> <span>row</span> <span>*</span> <span>8</span> <span>+</span> <span>7</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>let</span> <span>iThreatened</span> <span>=</span> <span>index</span> <span>+</span> <span>1</span><span>;</span> <span>iThreatened</span> <span>&lt;=</span> <span>endOfTheRow</span><span>;</span> <span>++</span><span>iThreatened</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>action</span><span>(</span><span>iThreatened</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    </td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>// the rest of the column</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>endOfTheColumn</span> <span>=</span> <span>56</span> <span>+</span> <span>col</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>let</span> <span>iThreatened</span> <span>=</span> <span>index</span> <span>+</span> <span>8</span><span>;</span> <span>iThreatened</span> <span>&lt;=</span> <span>endOfTheColumn</span><span>;</span> <span>iThreatened</span> <span>+=</span> <span>8</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>action</span><span>(</span><span>iThreatened</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    </td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>// diagonals to the left</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>lengthOfLeftDiagonal</span> <span>=</span> <span>Math</span><span>.</span><span>min</span><span>(</span><span>col</span><span>,</span> <span>7</span> <span>-</span> <span>row</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>let</span> <span>i</span> <span>=</span> <span>1</span><span>;</span> <span>i</span> <span>&lt;=</span> <span>lengthOfLeftDiagonal</span><span>;</span> <span>++</span><span>i</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>[</span><span>rowThreatened</span><span>,</span> <span>colThreatened</span><span>]</span> <span>=</span> <span>[</span><span>row</span> <span>+</span> <span>i</span><span>,</span> <span>col</span> <span>-</span> <span>i</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>iThreatened</span> <span>=</span> <span>rowThreatened</span> <span>*</span> <span>8</span> <span>+</span> <span>colThreatened</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>action</span><span>(</span><span>iThreatened</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    </td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>// diagonals to the right</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>lengthOfRightDiagonal</span> <span>=</span> <span>Math</span><span>.</span><span>min</span><span>(</span><span>7</span> <span>-</span> <span>col</span><span>,</span> <span>7</span> <span>-</span> <span>row</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>let</span> <span>i</span> <span>=</span> <span>1</span><span>;</span> <span>i</span> <span>&lt;=</span> <span>lengthOfRightDiagonal</span><span>;</span> <span>++</span><span>i</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>[</span><span>rowThreatened</span><span>,</span> <span>colThreatened</span><span>]</span> <span>=</span> <span>[</span><span>row</span> <span>+</span> <span>i</span><span>,</span> <span>col</span> <span>+</span> <span>i</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>iThreatened</span> <span>=</span> <span>rowThreatened</span> <span>*</span> <span>8</span> <span>+</span> <span>colThreatened</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>action</span><span>(</span><span>iThreatened</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    </td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>return</span> <span>this</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  </td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>occupy</span> <span>(</span><span>index</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>occupyAction</span> <span>=</span> <span>index</span> <span>=&gt;</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>++</span><span>this</span><span>.</span><span>threats</span><span>[</span><span>index</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    </td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>if</span> <span>(</span><span>this</span><span>.</span><span>isOccupiable</span><span>(</span><span>index</span><span>)</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>this</span><span>.</span><span>queenIndices</span><span>.</span><span>push</span><span>(</span><span>index</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>return</span> <span>this</span><span>[</span><span>OCCUPATION_HELPER</span><span>]</span><span>(</span><span>index</span><span>,</span> <span>occupyAction</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  </td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>unoccupy</span> <span>(</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>const</span> <span>unoccupyAction</span> <span>=</span> <span>index</span> <span>=&gt;</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>--</span><span>this</span><span>.</span><span>threats</span><span>[</span><span>index</span><span>]</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    </td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>if</span> <span>(</span><span>this</span><span>.</span><span>hasQueens</span><span>(</span><span>)</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>const</span> <span>index</span> <span>=</span> <span>this</span><span>.</span><span>queenIndices</span><span>.</span><span>pop</span><span>(</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      </td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>return</span> <span>this</span><span>[</span><span>OCCUPATION_HELPER</span><span>]</span><span>(</span><span>index</span><span>,</span> <span>unoccupyAction</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>
</td>
        </tr>
        <tr>
          <td></td>
          <td><span>function</span> <span>*</span> <span>inductive</span> <span>(</span><span>board</span> <span>=</span> <span>new</span> <span>Board</span><span>(</span><span>)</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>if</span> <span>(</span><span>board</span><span>.</span><span>numberOfQueens</span><span>(</span><span>)</span> <span>===</span> <span>8</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>yield</span> <span>board</span><span>.</span><span>queens</span><span>(</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span> <span>else</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>for</span> <span>(</span><span>const</span> <span>index</span> <span>of</span> <span>board</span><span>.</span><span>availableIndices</span><span>(</span><span>)</span><span>)</span> <span>{</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>board</span><span>.</span><span>occupy</span><span>(</span><span>index</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>yield</span> <span>*</span> <span>inductive</span><span>(</span><span>board</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>      <span>board</span><span>.</span><span>unoccupy</span><span>(</span><span>)</span><span>;</span></td>
        </tr>
        <tr>
          <td></td>
          <td>    <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td>  <span>}</span></td>
        </tr>
        <tr>
          <td></td>
          <td><span>}</span></td>
        </tr>
  </tbody></table>
</div>


      
</div></div>||||I||||    Skip to content
        All gists Back to GitHub Sign in Sign up
        Sign in Sign up
      You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
            {{ message }}

          Instantly share code, notes, and snippets.

                    raganwald / eight-queens-0-fundamentals.js

                    Last active August 7, 2018 23:22
              Show Gist options
                      * Download ZIP
              * Star ( 1 ) 1 You must be signed in to star a gist
              * Fork ( 0 ) 0 You must be signed in to fork a gist
              * Embed
                        + Embed Embed this gist in your website.
                        + Share Copy sharable link for this gist.
                        + Clone via HTTPS Clone using the web URL.
                        + 
                        + Learn more about clone URLs
                Clone this repository at <script src="https://gist.github.com/raganwald/e8896be8f032ba80019fd6a20fc6bb7d.js"></script>
            * Save raganwald/e8896be8f032ba80019fd6a20fc6bb7d to your computer and use it in GitHub Desktop.
                Code Revisions 20 Stars 1
                Embed
                        * Embed Embed this gist in your website.
                        * Share Copy sharable link for this gist.
                        * Clone via HTTPS Clone using the web URL.
                        * 
                        * Learn more about clone URLs
                Clone this repository at <script src="https://gist.github.com/raganwald/e8896be8f032ba80019fd6a20fc6bb7d.js"></script>
                Save raganwald/e8896be8f032ba80019fd6a20fc6bb7d to your computer and use it in GitHub Desktop.
                Download ZIP
              The Eight Queens Problem
                    Raw
                    eight-queens-0-fundamentals.js
                      This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
                        Show hidden characters
                        // Computes the twelve "fundamental" solutions to the eight queens problem                                  
                        // by filtering the results of the "half-inductive" algorithm.                                              
                        //                                                                                                          
                        // see http://raganwald.com/2018/08/03/eight-queens.html                                                    
                        //                                                                                                          
                        // search space: 2,750 candidate positions                                                                  
                                                                                                                                    
                        function testDiagonals ( queens ) {                                                                         
                        const nesw = [ "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." ] ;  
                        const nwse = [ "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." ] ;  
                                                                                                                                    
                        if ( queens . length < 2 ) return true ;                                                                    
                                                                                                                                    
                        for ( const [ i , j ] of queens ) {                                                                         
                        if ( nwse [ i + j ] !== '.' || nesw [ i + 7 - j ] !== '.' ) return false ;                                  
                                                                                                                                    
                        nwse [ i + j ] = 'x' ;                                                                                      
                        nesw [ i + 7 - j ] = 'x' ;                                                                                  
                        }                                                                                                           
                                                                                                                                    
                        return true ;                                                                                               
                        }                                                                                                           
                                                                                                                                    
                        const without = ( array , element ) =>                                                                      
                        array . filter ( x => x !== element ) ;                                                                     
                                                                                                                                    
                        function * inductive (                                                                                      
                        queens = [ ] ,                                                                                              
                        candidateColumns = [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 ]                                                        
                        ) {                                                                                                         
                        if ( queens . length === 8 ) {                                                                              
                        yield queens ;                                                                                              
                        } else {                                                                                                    
                        for ( const chosenColumn of candidateColumns ) {                                                            
                        const candidateQueens = queens . concat ( [ [ queens . length , chosenColumn ] ] ) ;                        
                        const remainingColumns = without ( candidateColumns , chosenColumn ) ;                                      
                                                                                                                                    
                        if ( testDiagonals ( candidateQueens ) ) {                                                                  
                        yield * inductive ( candidateQueens , remainingColumns ) ;                                                  
                        }                                                                                                           
                        }                                                                                                           
                        }                                                                                                           
                        }                                                                                                           
                                                                                                                                    
                        const allColumns = [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 ] ;                                                      
                                                                                                                                    
                        function * halfInductive ( ) {                                                                              
                        for ( const column of [ 0 , 1 , 2 , 3 ] ) {                                                                 
                        const candidateQueens = [ [ 0 , column ] ] ;                                                                
                        const remainingColumns = without ( allColumns , column ) ;                                                  
                        yield * inductive ( candidateQueens , remainingColumns ) ;                                                  
                        }                                                                                                           
                        }                                                                                                           
                                                                                                                                    
                        function verticalReflection ( queens ) {                                                                    
                        return queens . map (                                                                                       
                        ( [ row , col ] ) => [ row , 7 - col ]                                                                      
                        ) ;                                                                                                         
                        }                                                                                                           
                                                                                                                                    
                        const sortQueens = queens =>                                                                                
                        queens . reduce (                                                                                           
                        ( acc , [ row , col ] ) => ( acc [ row ] = [ row , col ] , acc ) ,                                          
                        [ null , null , null , null , null , null , null , null ]                                                   
                        ) ;                                                                                                         
                                                                                                                                    
                        const rotateRight = queens =>                                                                               
                        sortQueens ( queens . map ( ( [ row , col ] ) => [ col , 7 - row ] ) ) ;                                    
                                                                                                                                    
                        const rotations = solution => {                                                                             
                        const rotations = [ null , null , null ] ;                                                                  
                        let temp = rotateRight ( solution ) ;                                                                       
                                                                                                                                    
                        rotations [ 0 ] = temp ;                                                                                    
                        temp = rotateRight ( temp ) ;                                                                               
                        rotations [ 1 ] = temp ;                                                                                    
                        temp = rotateRight ( temp ) ;                                                                               
                        rotations [ 2 ] = temp ;                                                                                    
                                                                                                                                    
                        return rotations ;                                                                                          
                        }                                                                                                           
                                                                                                                                    
                        const indexQueens = queens => queens . map ( ( [ row , col ] ) => ` ${ row } , ${ col } ` ) . join ( ' ' ) ;
                                                                                                                                    
                        function * fundamentals ( solutions ) {                                                                     
                        const solutionsSoFar = new Set ( ) ;                                                                        
                                                                                                                                    
                        for ( const solution of solutions ) {                                                                       
                        const iSolution = indexQueens ( solution ) ;                                                                
                                                                                                                                    
                        if ( solutionsSoFar . has ( iSolution ) ) continue ;                                                        
                                                                                                                                    
                        solutionsSoFar . add ( iSolution ) ;                                                                        
                        const rSolutions = rotations ( solution ) ;                                                                 
                        const irSolutions = rSolutions . map ( indexQueens ) ;                                                      
                        for ( let irSolution of irSolutions ) {                                                                     
                        solutionsSoFar . add ( irSolution ) ;                                                                       
                        }                                                                                                           
                                                                                                                                    
                        const vSolution = verticalReflection ( solution ) ;                                                         
                                                                                                                                    
                        const rvSolutions = rotations ( vSolution ) ;                                                               
                        const irvSolutions = rvSolutions . map ( indexQueens ) ;                                                    
                                                                                                                                    
                        for ( let irvSolution of irvSolutions ) {                                                                   
                        solutionsSoFar . add ( irvSolution ) ;                                                                      
                        }                                                                                                           
                                                                                                                                    
                        yield solution ;                                                                                            
                        }                                                                                                           
                        }                                                                                                           
                                                                                                                                    
                        function * mapWith ( mapFunction , iterable ) {                                                             
                        for ( const element of iterable ) {                                                                         
                        yield mapFunction ( element ) ;                                                                             
                        }                                                                                                           
                        }                                                                                                           
                                                                                                                                    
                        function niceDiagramOf ( queens ) {                                                                         
                        const board = [                                                                                             
                        [ "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" ] ,                                                 
                        [ "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" ] ,                                                 
                        [ "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" ] ,                                                 
                        [ "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" ] ,                                                 
                        [ "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" ] ,                                                 
                        [ "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" ] ,                                                 
                        [ "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" ] ,                                                 
                        [ "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" , "⬛️" , "⬜️" ]                                                   
                        ] ;                                                                                                         
                                                                                                                                    
                        for ( const [ row , col ] of queens ) {                                                                     
                        board [ 7 - row ] [ col ] = "👸🏾" ;                                                                          
                        }                                                                                                           
                                                                                                                                    
                        return board . map ( row => row . join ( '' ) ) . join ( "\n" ) ;                                           
                        }                                                                                                           
                                                                                                                                    
                        mapWith ( niceDiagramOf , fundamentals ( halfInductive ( ) ) )                                              
                      
                      Raw
                      eight-queens-1-half-inductive.js
                        This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
                          Show hidden characters
                          // Computes the all 92 solutions to the eight queens problem                                              
                          // by computing half of the results of the inductive solution                                             
                          // and then adding their vertical reflections.                                                            
                          //                                                                                                        
                          // see http://raganwald.com/2018/08/03/eight-queens.html                                                  
                          //                                                                                                        
                          // search space: 2,750 candidate positions                                                                
                                                                                                                                    
                          function testDiagonals ( queens ) {                                                                       
                          const nesw = [ "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." ] ;
                          const nwse = [ "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." ] ;
                                                                                                                                    
                          if ( queens . length < 2 ) return true ;                                                                  
                                                                                                                                    
                          for ( const [ i , j ] of queens ) {                                                                       
                          if ( nwse [ i + j ] !== '.' || nesw [ i + 7 - j ] !== '.' ) return false ;                                
                                                                                                                                    
                          nwse [ i + j ] = 'x' ;                                                                                    
                          nesw [ i + 7 - j ] = 'x' ;                                                                                
                          }                                                                                                         
                                                                                                                                    
                          return true ;                                                                                             
                          }                                                                                                         
                                                                                                                                    
                          const without = ( array , element ) =>                                                                    
                          array . filter ( x => x !== element ) ;                                                                   
                                                                                                                                    
                          function * inductive (                                                                                    
                          queens = [ ] ,                                                                                            
                          candidateColumns = [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 ]                                                      
                          ) {                                                                                                       
                          if ( queens . length === 8 ) {                                                                            
                          yield queens ;                                                                                            
                          } else {                                                                                                  
                          for ( const chosenColumn of candidateColumns ) {                                                          
                          const candidateQueens = queens . concat ( [ [ queens . length , chosenColumn ] ] ) ;                      
                          const remainingColumns = without ( candidateColumns , chosenColumn ) ;                                    
                                                                                                                                    
                          if ( testDiagonals ( candidateQueens ) ) {                                                                
                          yield * inductive ( candidateQueens , remainingColumns ) ;                                                
                          }                                                                                                         
                          }                                                                                                         
                          }                                                                                                         
                          }                                                                                                         
                                                                                                                                    
                          const allColumns = [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 ] ;                                                    
                                                                                                                                    
                          function * halfInductive ( ) {                                                                            
                          for ( const column of [ 0 , 1 , 2 , 3 ] ) {                                                               
                          const candidateQueens = [ [ 0 , column ] ] ;                                                              
                          const remainingColumns = without ( allColumns , column ) ;                                                
                          yield * inductive ( candidateQueens , remainingColumns ) ;                                                
                          }                                                                                                         
                          }                                                                                                         
                                                                                                                                    
                          function verticalReflection ( queens ) {                                                                  
                          return queens . map (                                                                                     
                          ( [ row , col ] ) => [ row , 7 - col ]                                                                    
                          ) ;                                                                                                       
                          }                                                                                                         
                                                                                                                                    
                          function * flatMapWith ( fn , iterable ) {                                                                
                          for ( const element of iterable ) {                                                                       
                          yield * fn ( element ) ;                                                                                  
                          }                                                                                                         
                          }                                                                                                         
                                                                                                                                    
                          const withReflections = flatMapWith (                                                                     
                          queens => [ queens , verticalReflection ( queens ) ] , halfInductive ( ) ) ;                              
                                                                                                                                    
                          Array . from ( withReflections ) . length                                                                 
                          //=> 92                                                                                                   
                        
                        Raw
                        eight-queens-2-inductive.js
                          This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
                            Show hidden characters
                            // Computes the all 92 solutions to the eight queens problem                                              
                            // by testing partial solutions to the "rooks" algorithm                                                  
                            // as they are created, thus pruning subtrees when possible.                                              
                            //                                                                                                        
                            // see http://raganwald.com/2018/08/03/eight-queens.html                                                  
                            //                                                                                                        
                            // search space: 5,508 candidate positions                                                                
                                                                                                                                      
                            function testDiagonals ( queens ) {                                                                       
                            const nesw = [ "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." ] ;
                            const nwse = [ "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." , "." ] ;
                                                                                                                                      
                            if ( queens . length < 2 ) return true ;                                                                  
                                                                                                                                      
                            for ( const [ i , j ] of queens ) {                                                                       
                            if ( nwse [ i + j ] !== '.' || nesw [ i + 7 - j ] !== '.' ) return false ;                                
                                                                                                                                      
                            nwse [ i + j ] = 'x' ;                                                                                    
                            nesw [ i + 7 - j ] = 'x' ;                                                                                
                            }                                                                                                         
                                                                                                                                      
                            return true ;                                                                                             
                            }                                                                                                         
                                                                                                                                      
                            const without = ( array , element ) =>                                                                    
                            array . filter ( x => x !== element ) ;                                                                   
                                                                                                                                      
                            function * inductive (                                                                                    
                            queens = [ ] ,                                                                                            
                            candidateColumns = [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 ]                                                      
                            ) {                                                                                                       
                            if ( queens . length === 8 ) {                                                                            
                            yield queens ;                                                                                            
                            } else {                                                                                                  
                            for ( const chosenColumn of candidateColumns ) {                                                          
                            const candidateQueens = queens . concat ( [ [ queens . length , chosenColumn ] ] ) ;                      
                            const remainingColumns = without ( candidateColumns , chosenColumn ) ;                                    
                                                                                                                                      
                            if ( testDiagonals ( candidateQueens ) ) {                                                                
                            yield * inductive ( candidateQueens , remainingColumns ) ;                                                
                            }                                                                                                         
                            }                                                                                                         
                            }                                                                                                         
                            }                                                                                                         
                                                                                                                                      
                            Array . from ( inductive ( ) ) . length                                                                   
                            //=> 92                                                                                                   
                          
                          Raw
                          eight-queens-3-rooks.js
                            This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
                              Show hidden characters
                              // Computes the all 92 solutions to the eight queens problem                             
                              // by generating all of the solutions to the eight rooks                                 
                              // problem using permutations, and then filtering them                                   
                              // by testing for diagonal attacks.                                                      
                              //                                                                                       
                              // see http://raganwald.com/2018/08/03/eight-queens.html                                 
                              //                                                                                       
                              // search space: 40,320 candidate positions                                              
                                                                                                                       
                              function diagramOf ( queens ) {                                                          
                              const board = [                                                                          
                              [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                      
                              [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                      
                              [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                      
                              [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                      
                              [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                      
                              [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                      
                              [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                      
                              [ "." , "." , "." , "." , "." , "." , "." , "." ]                                        
                              ] ;                                                                                      
                                                                                                                       
                              for ( const [ i , j ] of queens ) {                                                      
                              board [ i ] [ j ] = "Q" ;                                                                
                              }                                                                                        
                                                                                                                       
                              return board . map ( row => row . join ( '' ) ) . join ( "\n" ) ;                        
                              }                                                                                        
                                                                                                                       
                              function test ( queens ) {                                                               
                              const board = [                                                                          
                              [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                      
                              [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                      
                              [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                      
                              [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                      
                              [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                      
                              [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                      
                              [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                      
                              [ "." , "." , "." , "." , "." , "." , "." , "." ]                                        
                              ] ;                                                                                      
                                                                                                                       
                              for ( const [ i , j ] of queens ) {                                                      
                              if ( board [ i ] [ j ] != '.' ) {                                                        
                              // square is occupied or threatened                                                      
                              return false ;                                                                           
                              }                                                                                        
                                                                                                                       
                              for ( let k = 0 ; k <= 7 ; ++ k ) {                                                      
                              // fill row and column                                                                   
                              board [ i ] [ k ] = board [ k ] [ j ] = "x" ;                                            
                                                                                                                       
                              const vOffset = k - i ;                                                                  
                              const hDiagonal1 = j - vOffset ;                                                         
                              const hDiagonal2 = j + vOffset ;                                                         
                                                                                                                       
                              // fill diagonals                                                                        
                              if ( hDiagonal1 >= 0 && hDiagonal1 <= 7 ) {                                              
                              board [ k ] [ hDiagonal1 ] = "x" ;                                                       
                              }                                                                                        
                                                                                                                       
                              if ( hDiagonal2 >= 0 && hDiagonal2 <= 7 ) {                                              
                              board [ k ] [ hDiagonal2 ] = "x" ;                                                       
                              }                                                                                        
                                                                                                                       
                              board [ i ] [ j ] = "Q" ;                                                                
                              }                                                                                        
                              }                                                                                        
                                                                                                                       
                              return true ;                                                                            
                              }                                                                                        
                                                                                                                       
                              function * filterWith ( predicateFunction , iterable ) {                                 
                              for ( const element of iterable ) {                                                      
                              if ( predicateFunction ( element ) ) {                                                   
                              yield element ;                                                                          
                              }                                                                                        
                              }                                                                                        
                              }                                                                                        
                                                                                                                       
                              function first ( iterable ) {                                                            
                              const [ value ] = iterable ;                                                             
                                                                                                                       
                              return value ;                                                                           
                              }                                                                                        
                                                                                                                       
                              function * mapWith ( mapFunction , iterable ) {                                          
                              for ( const element of iterable ) {                                                      
                              yield mapFunction ( element ) ;                                                          
                              }                                                                                        
                              }                                                                                        
                                                                                                                       
                              function * permutations ( arr , prefix = [ ] ) {                                         
                              if ( arr . length === 1 ) {                                                              
                              yield prefix . concat ( arr ) ;                                                          
                              } else if ( arr . length > 1 ) {                                                         
                              for ( let i = 0 ; i < arr . length ; ++ i ) {                                            
                              const chosen = arr [ i ] ;                                                               
                              const remainder = arr . slice ( 0 , i ) . concat ( arr . slice ( i + 1 , arr . length ) )
                                                                                                                       
                              yield * permutations ( remainder , prefix . concat ( [ chosen ] ) ) ;                    
                              }                                                                                        
                              }                                                                                        
                              }                                                                                        
                                                                                                                       
                              const solutionsToEightRooks = mapWith (                                                  
                              ii => ii . map ( ( i , j ) => [ i , j ] ) ,                                              
                              permutations ( [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 ] )                                       
                              ) ;                                                                                      
                                                                                                                       
                              const solutionsToEightQueens = filterWith ( test , solutionsToEightRooks ) ;             
                                                                                                                       
                              diagramOf ( first ( solutionsToEightQueens ) )                                           
                            
                            Raw
                            eight-queens-4-combinations.js
                              This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
                                Show hidden characters
                                // Computes the all 92 solutions to the eight queens problem                        
                                // by computing all of the ways eight queens can be arranged                        
                                // on the board using 64 choose 8, then filtering them                              
                                // for horizontal, vertical, and diagonal attacks.                                  
                                //                                                                                  
                                // see http://raganwald.com/2018/08/03/eight-queens.html                            
                                //                                                                                  
                                // search space: 4,426,165,368 candidate positions                                  
                                                                                                                    
                                function diagramOf ( queens ) {                                                     
                                const board = [                                                                     
                                [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                 
                                [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                 
                                [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                 
                                [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                 
                                [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                 
                                [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                 
                                [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                 
                                [ "." , "." , "." , "." , "." , "." , "." , "." ]                                   
                                ] ;                                                                                 
                                                                                                                    
                                for ( const [ i , j ] of queens ) {                                                 
                                board [ i ] [ j ] = "Q" ;                                                           
                                }                                                                                   
                                                                                                                    
                                return board . map ( row => row . join ( '' ) ) . join ( "\n" ) ;                   
                                }                                                                                   
                                                                                                                    
                                function test ( queens ) {                                                          
                                const board = [                                                                     
                                [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                 
                                [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                 
                                [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                 
                                [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                 
                                [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                 
                                [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                 
                                [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                                 
                                [ "." , "." , "." , "." , "." , "." , "." , "." ]                                   
                                ] ;                                                                                 
                                                                                                                    
                                for ( const [ i , j ] of queens ) {                                                 
                                if ( board [ i ] [ j ] != '.' ) {                                                   
                                // square is occupied or threatened                                                 
                                return false ;                                                                      
                                }                                                                                   
                                                                                                                    
                                for ( let k = 0 ; k <= 7 ; ++ k ) {                                                 
                                // fill row and column                                                              
                                board [ i ] [ k ] = board [ k ] [ j ] = "x" ;                                       
                                                                                                                    
                                const vOffset = k - i ;                                                             
                                const hDiagonal1 = j - vOffset ;                                                    
                                const hDiagonal2 = j + vOffset ;                                                    
                                                                                                                    
                                // fill diagonals                                                                   
                                if ( hDiagonal1 >= 0 && hDiagonal1 <= 7 ) {                                         
                                board [ k ] [ hDiagonal1 ] = "x" ;                                                  
                                }                                                                                   
                                                                                                                    
                                if ( hDiagonal2 >= 0 && hDiagonal2 <= 7 ) {                                         
                                board [ k ] [ hDiagonal2 ] = "x" ;                                                  
                                }                                                                                   
                                                                                                                    
                                board [ i ] [ j ] = "Q" ;                                                           
                                }                                                                                   
                                }                                                                                   
                                                                                                                    
                                return true ;                                                                       
                                }                                                                                   
                                                                                                                    
                                function * filterWith ( predicateFunction , iterable ) {                            
                                for ( const element of iterable ) {                                                 
                                if ( predicateFunction ( element ) ) {                                              
                                yield element ;                                                                     
                                }                                                                                   
                                }                                                                                   
                                }                                                                                   
                                                                                                                    
                                function first ( iterable ) {                                                       
                                const [ value ] = iterable ;                                                        
                                                                                                                    
                                return value ;                                                                      
                                }                                                                                   
                                                                                                                    
                                function * mapWith ( mapFunction , iterable ) {                                     
                                for ( const element of iterable ) {                                                 
                                yield mapFunction ( element ) ;                                                     
                                }                                                                                   
                                }                                                                                   
                                                                                                                    
                                function * choose ( n , k , offset = 0 ) {                                          
                                if ( k === 1 ) {                                                                    
                                for ( let i = 0 ; i <= ( n - k ) ; ++ i ) {                                         
                                yield [ i + offset ] ;                                                              
                                }                                                                                   
                                } else if ( k > 1 ) {                                                               
                                for ( let i = 0 ; i <= ( n - k ) ; ++ i ) {                                         
                                const remaining = n - i - 1 ;                                                       
                                const otherChoices = choose ( remaining , k - 1 , i + offset + 1 ) ;                
                                                                                                                    
                                yield * mapWith ( x => [ i + offset ] . concat ( x ) , otherChoices ) ;             
                                }                                                                                   
                                }                                                                                   
                                }                                                                                   
                                                                                                                    
                                const numberToPosition = n => [ Math . floor ( n / 8 ) , n % 8 ] ;                  
                                const numbersToPositions = queenNumbers => queenNumbers . map ( numberToPosition ) ;
                                                                                                                    
                                const combinationCandidates = mapWith ( numbersToPositions , choose ( 64 , 8 ) ) ;  
                                                                                                                    
                                const solutionsToEightQueens = filterWith ( test , combinationCandidates ) ;        
                                                                                                                    
                                diagramOf ( first ( solutionsToEightQueens ) )                                      
                              
                              Raw
                              eight-queens-5-generator-tester.js
                                This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
                                  Show hidden characters
                                  // Computes the all 92 solutions to the eight queens problem                    
                                  // by computing all of the possible arrangements of eight                       
                                  // chess squares (64^8), then filtering them                                    
                                  // for horizontal, vertical, and diagonal attacks.                              
                                  //                                                                              
                                  // see http://raganwald.com/2018/08/03/eight-queens.html                        
                                  //                                                                              
                                  // search space: 281,474,976,710,656 candidate positions                        
                                                                                                                  
                                  function diagramOf ( queens ) {                                                 
                                  const board = [                                                                 
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                             
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                             
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                             
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                             
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                             
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                             
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                             
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ]                               
                                  ] ;                                                                             
                                                                                                                  
                                  for ( const [ i , j ] of queens ) {                                             
                                  board [ i ] [ j ] = "Q" ;                                                       
                                  }                                                                               
                                                                                                                  
                                  return board . map ( row => row . join ( '' ) ) . join ( "\n" ) ;               
                                  }                                                                               
                                                                                                                  
                                  function * mostPessimumGenerator ( ) {                                          
                                  for ( let i0 = 0 ; i0 <= 7 ; ++ i0 ) {                                          
                                  for ( let j0 = 0 ; j0 <= 7 ; ++ j0 ) {                                          
                                  for ( let i1 = 0 ; i1 <= 7 ; ++ i1 ) {                                          
                                  for ( let j1 = 0 ; j1 <= 7 ; ++ j1 ) {                                          
                                  for ( let i2 = 0 ; i2 <= 7 ; ++ i2 ) {                                          
                                  for ( let j2 = 0 ; j2 <= 7 ; ++ j2 ) {                                          
                                  for ( let i3 = 0 ; i3 <= 7 ; ++ i3 ) {                                          
                                  for ( let j3 = 0 ; j3 <= 7 ; ++ j3 ) {                                          
                                  for ( let i4 = 0 ; i4 <= 7 ; ++ i4 ) {                                          
                                  for ( let j4 = 0 ; j4 <= 7 ; ++ j4 ) {                                          
                                  for ( let i5 = 0 ; i5 <= 7 ; ++ i5 ) {                                          
                                  for ( let j5 = 0 ; j5 <= 7 ; ++ j5 ) {                                          
                                  for ( let i6 = 0 ; i6 <= 7 ; ++ i6 ) {                                          
                                  for ( let j6 = 0 ; j6 <= 7 ; ++ j6 ) {                                          
                                  for ( let i7 = 0 ; i7 <= 7 ; ++ i7 ) {                                          
                                  for ( let j7 = 0 ; j7 <= 7 ; ++ j7 ) {                                          
                                  const queens = [                                                                
                                  [ i0 , j0 ] ,                                                                   
                                  [ i1 , j1 ] ,                                                                   
                                  [ i2 , j2 ] ,                                                                   
                                  [ i3 , j3 ] ,                                                                   
                                  [ i4 , j4 ] ,                                                                   
                                  [ i5 , j5 ] ,                                                                   
                                  [ i6 , j6 ] ,                                                                   
                                  [ i7 , j7 ]                                                                     
                                  ] ;                                                                             
                                                                                                                  
                                  yield queens ;                                                                  
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                                                                                                  
                                  function test ( queens ) {                                                      
                                  const board = [                                                                 
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                             
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                             
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                             
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                             
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                             
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                             
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ] ,                             
                                  [ "." , "." , "." , "." , "." , "." , "." , "." ]                               
                                  ] ;                                                                             
                                                                                                                  
                                  for ( const [ i , j ] of queens ) {                                             
                                  if ( board [ i ] [ j ] != '.' ) {                                               
                                  // square is occupied or threatened                                             
                                  return false ;                                                                  
                                  }                                                                               
                                                                                                                  
                                  for ( let k = 0 ; k <= 7 ; ++ k ) {                                             
                                  // fill row and column                                                          
                                  board [ i ] [ k ] = board [ k ] [ j ] = "x" ;                                   
                                                                                                                  
                                  const vOffset = k - i ;                                                         
                                  const hDiagonal1 = j - vOffset ;                                                
                                  const hDiagonal2 = j + vOffset ;                                                
                                                                                                                  
                                  // fill diagonals                                                               
                                  if ( hDiagonal1 >= 0 && hDiagonal1 <= 7 ) {                                     
                                  board [ k ] [ hDiagonal1 ] = "x" ;                                              
                                  }                                                                               
                                                                                                                  
                                  if ( hDiagonal2 >= 0 && hDiagonal2 <= 7 ) {                                     
                                  board [ k ] [ hDiagonal2 ] = "x" ;                                              
                                  }                                                                               
                                                                                                                  
                                  board [ i ] [ j ] = "Q" ;                                                       
                                  }                                                                               
                                  }                                                                               
                                                                                                                  
                                  return true ;                                                                   
                                  }                                                                               
                                                                                                                  
                                  function * filterWith ( predicateFunction , iterable ) {                        
                                  for ( const element of iterable ) {                                             
                                  if ( predicateFunction ( element ) ) {                                          
                                  yield element ;                                                                 
                                  }                                                                               
                                  }                                                                               
                                  }                                                                               
                                                                                                                  
                                  function first ( iterable ) {                                                   
                                  const [ value ] = iterable ;                                                    
                                                                                                                  
                                  return value ;                                                                  
                                  }                                                                               
                                                                                                                  
                                  const solutionsToEightQueens = filterWith ( test , mostPessimumGenerator ( ) ) ;
                                                                                                                  
                                  diagramOf ( first ( solutionsToEightQueens ) )                                  
                                
                                Raw
                                eight-queens-6-pure-tree.js
                                  This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
                                    Show hidden characters
                                    const OCCUPATION_HELPER = Symbol ( "occupationHelper" ) ;                                           
                                                                                                                                        
                                    class Board {                                                                                       
                                    constructor ( ) {                                                                                   
                                    this . threats = [                                                                                  
                                    0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,                                                                     
                                    0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,                                                                     
                                    0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,                                                                     
                                    0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,                                                                     
                                    0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,                                                                     
                                    0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,                                                                     
                                    0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,                                                                     
                                    0 , 0 , 0 , 0 , 0 , 0 , 0 , 0                                                                       
                                    ] ;                                                                                                 
                                    this . queenIndices = [ ] ;                                                                         
                                    }                                                                                                   
                                                                                                                                        
                                    isValid ( index ) {                                                                                 
                                    return index >= 0 && index <= 63 ;                                                                  
                                    }                                                                                                   
                                                                                                                                        
                                    isAvailable ( index ) {                                                                             
                                    return this . threats [ index ] === 0 ;                                                             
                                    }                                                                                                   
                                                                                                                                        
                                    isEmpty ( ) {                                                                                       
                                    return this . queenIndices . length === 0 ;                                                         
                                    }                                                                                                   
                                                                                                                                        
                                    isOccupiable ( index ) {                                                                            
                                    if ( this . isEmpty ( ) ) {                                                                         
                                    return this . isValid ( index ) ;                                                                   
                                    } else {                                                                                            
                                    return this . isValid ( index ) && index > this . lastQueen ( ) && this . isAvailable ( index ) ;   
                                    }                                                                                                   
                                    }                                                                                                   
                                                                                                                                        
                                    numberOfQueens ( ) {                                                                                
                                    return this . queenIndices . length                                                                 
                                    }                                                                                                   
                                                                                                                                        
                                    hasQueens ( ) {                                                                                     
                                    return this . numberOfQueens ( ) > 0 ;                                                              
                                    }                                                                                                   
                                                                                                                                        
                                    queens ( ) {                                                                                        
                                    return this . queenIndices . map ( index => [ Math . floor ( index / 8 ) , index % 8 ] ) ;          
                                    }                                                                                                   
                                                                                                                                        
                                    lastQueen ( ) {                                                                                     
                                    if ( this . queenIndices . length > 0 ) {                                                           
                                    return this . queenIndices [ this . queenIndices . length - 1 ] ;                                   
                                    }                                                                                                   
                                    }                                                                                                   
                                                                                                                                        
                                    * availableIndices ( ) {                                                                            
                                    for ( let index = ( this . isEmpty ( ) ? 0 : this . lastQueen ( ) + 1 ) ; index <= 63 ; ++ index ) {
                                    if ( this . isAvailable ( index ) ) {                                                               
                                    yield index ;                                                                                       
                                    }                                                                                                   
                                    }                                                                                                   
                                    }                                                                                                   
                                                                                                                                        
                                    [ OCCUPATION_HELPER ] ( index , action ) {                                                          
                                    const [ row , col ] = [ Math . floor ( index / 8 ) , index % 8 ] ;                                  
                                                                                                                                        
                                    // the rest of the row                                                                              
                                    const endOfTheRow = row * 8 + 7 ;                                                                   
                                    for ( let iThreatened = index + 1 ; iThreatened <= endOfTheRow ; ++ iThreatened ) {                 
                                    action ( iThreatened ) ;                                                                            
                                    }                                                                                                   
                                                                                                                                        
                                    // the rest of the column                                                                           
                                    const endOfTheColumn = 56 + col ;                                                                   
                                    for ( let iThreatened = index + 8 ; iThreatened <= endOfTheColumn ; iThreatened += 8 ) {            
                                    action ( iThreatened ) ;                                                                            
                                    }                                                                                                   
                                                                                                                                        
                                    // diagonals to the left                                                                            
                                    const lengthOfLeftDiagonal = Math . min ( col , 7 - row ) ;                                         
                                    for ( let i = 1 ; i <= lengthOfLeftDiagonal ; ++ i ) {                                              
                                    const [ rowThreatened , colThreatened ] = [ row + i , col - i ] ;                                   
                                    const iThreatened = rowThreatened * 8 + colThreatened ;                                             
                                                                                                                                        
                                    action ( iThreatened ) ;                                                                            
                                    }                                                                                                   
                                                                                                                                        
                                    // diagonals to the right                                                                           
                                    const lengthOfRightDiagonal = Math . min ( 7 - col , 7 - row ) ;                                    
                                    for ( let i = 1 ; i <= lengthOfRightDiagonal ; ++ i ) {                                             
                                    const [ rowThreatened , colThreatened ] = [ row + i , col + i ] ;                                   
                                    const iThreatened = rowThreatened * 8 + colThreatened ;                                             
                                                                                                                                        
                                    action ( iThreatened ) ;                                                                            
                                    }                                                                                                   
                                                                                                                                        
                                    return this ;                                                                                       
                                    }                                                                                                   
                                                                                                                                        
                                    occupy ( index ) {                                                                                  
                                    const occupyAction = index => {                                                                     
                                    ++ this . threats [ index ] ;                                                                       
                                    } ;                                                                                                 
                                                                                                                                        
                                    if ( this . isOccupiable ( index ) ) {                                                              
                                    this . queenIndices . push ( index ) ;                                                              
                                    return this [ OCCUPATION_HELPER ] ( index , occupyAction ) ;                                        
                                    }                                                                                                   
                                    }                                                                                                   
                                                                                                                                        
                                    unoccupy ( ) {                                                                                      
                                    const unoccupyAction = index => {                                                                   
                                    -- this . threats [ index ] ;                                                                       
                                    } ;                                                                                                 
                                                                                                                                        
                                    if ( this . hasQueens ( ) ) {                                                                       
                                    const index = this . queenIndices . pop ( ) ;                                                       
                                                                                                                                        
                                    return this [ OCCUPATION_HELPER ] ( index , unoccupyAction ) ;                                      
                                    }                                                                                                   
                                    }                                                                                                   
                                    }                                                                                                   
                                                                                                                                        
                                    function * inductive ( board = new Board ( ) ) {                                                    
                                    if ( board . numberOfQueens ( ) === 8 ) {                                                           
                                    yield board . queens ( ) ;                                                                          
                                    } else {                                                                                            
                                    for ( const index of board . availableIndices ( ) ) {                                               
                                    board . occupy ( index ) ;                                                                          
                                    yield * inductive ( board ) ;                                                                       
                                    board . unoccupy ( ) ;                                                                              
                                    }                                                                                                   
                                    }                                                                                                   
                                    }                                                                                                   
                                  
                                  Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

              Footer

                  © 2024 GitHub, Inc.

                Footer navigation

                  * Terms
                  * Privacy
                  * Security
                  * Status
                  * Docs
                  * Contact
                  * Manage cookies
                  * Do not share my personal information
                You can’t perform that action at this time.
The Eight Queens Problem
https://gist.github.com/raganwald/e8896be8f032ba80019fd6a20fc6bb7d
AaronGoldman
2020-07-16T23:33:06Z
<div><div><article><p></p><h2>THE PROBLEM OF THE EIGHT QUEENS</h2><a href="#the-problem-of-the-eight-queens"></a><p></p>
<p></p><h2>Solving one problem in many langweges</h2><a href="#solving-one-problem-in-many-langweges"></a><p></p>
<p>It is requested to make a program generating all configurations of eight
queens on a chessboard of 8*8 squares such that no queen can take any of
the others. This means that in the configurations sought, no two queens
may be on the same row, on the same column or on the same diagonal.</p>
<p><a href="https://t.co/LKWZacSTha">https://t.co/LKWZacSTha</a></p>

<p></p><h2>Implimentations</h2><a href="#implimentations"></a><p></p>
<ul>
<li>Python 3
<div><pre><span>time</span> python3 nine-queens.py
<span>time</span> pypy3 nine-queens.py</pre></div>
</li>
<li>Node

</li>
<li>Julea
<div><pre><span>time</span> julia nine-queens.jl</pre></div>
</li>
<li>Rust
<div><pre><span>time</span> rustc -O nine-queens.rs
<span>time</span> ./nine-queens</pre></div>
</li>
<li>Awk
<div><pre><span>time</span> awk -f nine-queens.awk</pre></div>
</li>
<li>Clojure
<div><pre><span>time</span> java -jar ../clojure/clojure.jar nine-queens.clj</pre></div>
</li>
<li>Java
<div><pre><span>time</span> javac NineQueens.java
<span>time</span> java NineQueens</pre></div>
</li>
<li>Go (Golang)
<div><pre><span>time</span> go build nine-queens.go
<span>time</span> ./nine-queens</pre></div>
</li>
</ul>
</article></div></div>||||I||||    Skip to content

    Navigation Menu

    Toggle navigation
          Sign in
            * Product
                        + Actions
                        Automate any workflow
                        + Packages
                        Host and manage packages
                        + Security
                        Find and fix vulnerabilities
                        + Codespaces
                        Instant dev environments
                        + GitHub Copilot
                        Write better code with AI
                        + Code review
                        Manage code changes
                        + Issues
                        Plan and track work
                        + Discussions
                        Collaborate outside of code
                  Explore
                    + All features
                    + Documentation
                    + GitHub Skills
                    + Blog
            * Solutions
                  By size
                    + Enterprise
                    + Teams
                    + Startups
                  By industry
                    + Healthcare
                    + Financial services
                    + Manufacturing
                  By use case
                    + CI/CD & Automation
                    + DevOps
                    + DevSecOps
            * Resources
                  Topics
                    + AI
                    + DevOps
                    + Security
                    + Software Development
                  Explore
                    + Learning Pathways
                    + White papers, Ebooks, Webinars
                    + Customer Stories
                    + Partners
            * Open Source
                        + GitHub Sponsors
                        Fund open source developers
                        + The ReadME Project
                        GitHub community articles
                  Repositories
                    + Topics
                    + Trending
                    + Collections
            * Enterprise
                        + Enterprise platform
                        AI-powered developer platform
                  Available add-ons
                        + Advanced Security
                        Enterprise-grade security features
                        + GitHub Copilot
                        Enterprise-grade AI features
                        + Premium Support
                        Enterprise-grade 24/7 support
            * Pricing
              Search or jump to...

                Search code, repositories, users, issues, pull requests...

                        Search
                          Clear
                        Search syntax tips

                    Provide feedback

                We read every piece of feedback, and take your input very seriously.

                Include my email address so I can be contacted
                Cancel Submit feedback

                    Saved searches

                    Use saved searches to filter your results more quickly

                    Name
                    Query

                  To see all available qualifiers, see our documentation.

                Cancel Create saved search
              Sign in
            Sign up Reseting focus
      You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
            {{ message }}
              AaronGoldman / nine-queens-problem Public
              * Notifications You must be signed in to change notification settings
              * Fork 0
                * Star 1

            Eight queens puzzle with a programable N

              1 star 0 forks Branches Tags Activity
                  Star
                Notifications You must be signed in to change notification settings
          * Code
          * Issues 0
          * Pull requests 0
          * Actions
          * Projects 0
          * Security
          * Insights
          Additional navigation options
                  * Code
                  * Issues
                  * Pull requests
                  * Actions
                  * Projects
                  * Security
                  * Insights

        AaronGoldman/nine-queens-problem

                  This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
                              master
                          Branches Tags
                            Go to file
                        Code

                        Folders and files

                          Name                              Name                                Last commit message    Last commit date
                            Latest commit                 
                                                          
                                History                   
                                                          
                                20 Commits                
                                  .gitignore                        .gitignore                                                         
                                  NineQueens.java                   NineQueens.java                                                    
                                  nine-queens.awk                   nine-queens.awk                                                    
                                  nine-queens.clj                   nine-queens.clj                                                    
                                  nine-queens.go                    nine-queens.go                                                     
                                  nine-queens.jl                    nine-queens.jl                                                     
                                  nine-queens.jl.65925.cov          nine-queens.jl.65925.cov                                           
                                  nine-queens.js                    nine-queens.js                                                     
                                  nine-queens.pony                  nine-queens.pony                                                   
                                  nine-queens.py                    nine-queens.py                                                     
                                  nine-queens.rs                    nine-queens.rs                                                     
                                  readme.md                         readme.md                                                          
                            View all files                
                          

                              Repository files navigation

                                * README

                                THE PROBLEM OF THE EIGHT QUEENS

                                Solving one problem in many langweges

                              It is requested to make a program generating all configurations of eight queens on a chessboard of 8*8 squares such that no queen can take any of the others. This means that in the configurations sought, no two queens may be on the same row, on the same column or on the same diagonal.

                              https://t.co/LKWZacSTha

                              number of queen      number of solutions  20 µs * nSolutions
                              00                                     1            20.00 µs
                              01                                     1            20.00 µs
                              02                                     0             0.00 µs
                              03                                     0             0.00 µs
                              04                                     2            40.00 µs
                              05                                    10           400.00 µs
                              06                                     4            80.00 µs
                              07                                    40           800.00 µs
                              08                                    92             1.84 ms
                              09                                   352             7.04 ms
                              10                                   724            14.48 ms
                              11                                 2,680            53.60 ms
                              12                                14,200           284.00 ms
                              13                                73,712              1.47 s
                              14                               365,596              7.31 s
                              15                             2,279,184             45.58 s
                              16                            14,772,512              4.92 m
                              17                            95,815,104             31.94 m
                              18                           666,090,624              3.70 h
                              19                         4,968,057,848              1.15 d
                              20                        39,029,188,884              9.03 d
                              21                       314,666,222,712             72.83 d
                              22                     2,691,008,701,644              1.70 y
                              23                    24,233,937,684,440             15.36 y
                              24                   227,514,171,973,736            144.19 y
                              25                 2,207,893,435,808,352          1,399.28 y
                              26                22,317,699,616,364,044         14,144.10 y
                              27               234,907,967,154,122,528        148,875.69 y
                              

                                Implimentations

                                * Python 3
                                    time python3 nine-queens.py
                                    time pypy3 nine-queens.py
                                * Node
                                    time node nine-queens.js
                                * Julea
                                    time julia nine-queens.jl
                                * Rust
                                    time rustc -O nine-queens.rs
                                    time ./nine-queens
                                * Awk
                                    time awk -f nine-queens.awk
                                * Clojure
                                    time java -jar ../clojure/clojure.jar nine-queens.clj
                                * Java
                                    time javac NineQueens.java
                                    time java NineQueens
                                * Go (Golang)
                                    time go build nine-queens.go
                                    time ./nine-queens

                          About

                          Eight queens puzzle with a programable N

                          Resources

                            Readme
                            Activity

                          Stars

                            1 star

                          Watchers

                            0 watching

                          Forks

                            0 forks
                            Report repository

                        Releases

                          No releases published

                        Packages 0

                          No packages published

                        Languages

                          * Rust 15.9%
                          * JavaScript 15.2%
                          * Python 15.2%
                          * Julia 14.3%
                          * Go 9.8%
                          * Java 9.6%
                          * Other 20.0%

    Footer

        © 2024 GitHub, Inc.

      Footer navigation

        * Terms
        * Privacy
        * Security
        * Status
        * Docs
        * Contact
        * Manage cookies
        * Do not share my personal information
      You can’t perform that action at this time.
GitHub - AaronGoldman/nine-queens-problem: Eight queens puzzle with a programable N
https://github.com/AaronGoldman/nine-queens-problem
The D-Functionistas
None
<div>
<pre>Exact cover N-Queens
--------------------
The N-Queens puzzle may be expressed and solved as an exact cover problem:

    queensX←{               ⍝ Exact cover N-Queens.
        m←⍳3/⍵              ⍝ cell coordinate properties.
        r←=/¨1 0 1∘/¨m      ⍝ each rank must contain one queen.
        f←=/¨0 1 1∘/¨m      ⍝  ..  file  ..     ..      ..

        dm←-/¨⍳2/⍵          ⍝ diagonal labels.
        du←{⍵[⍋⍵]}∪,dm      ⍝ unique labels.
        y←⊖x←dm∘.=du        ⍝ x and y diagonals.

        m←,[⍳2]x,y,r,f      ⍝ constraints matrix.

        d←~(⍳1↓⍴m)∊⍳2×⍴du   ⍝ mask of required cols.
        ⍵ ⍵⍴d X m           ⍝ exact cover - matrix of queens.
    }

    ⍝ A solution for each of the first 9 N-Queens problems:

    queensX¨ 0 to 8
┌┬─┬───┬─────┬───────┬─────────┬───────────┬─────────────┬───────────────┐
││1│0 0│0 0 0│0 1 0 0│0 0 0 0 1│0 0 0 0 1 0│0 0 0 0 0 0 1│0 0 0 0 0 0 0 1│
││ │0 0│0 0 0│0 0 0 1│0 1 0 0 0│0 0 1 0 0 0│0 0 0 0 1 0 0│0 0 0 1 0 0 0 0│
││ │   │0 0 0│1 0 0 0│0 0 0 1 0│1 0 0 0 0 0│0 0 1 0 0 0 0│1 0 0 0 0 0 0 0│
││ │   │     │0 0 1 0│1 0 0 0 0│0 0 0 0 0 1│1 0 0 0 0 0 0│0 0 1 0 0 0 0 0│
││ │   │     │       │0 0 1 0 0│0 0 0 1 0 0│0 0 0 0 0 1 0│0 0 0 0 0 1 0 0│
││ │   │     │       │         │0 1 0 0 0 0│0 0 0 1 0 0 0│0 1 0 0 0 0 0 0│
││ │   │     │       │         │           │0 1 0 0 0 0 0│0 0 0 0 0 0 1 0│
││ │   │     │       │         │           │             │0 0 0 0 1 0 0 0│
└┴─┴───┴─────┴───────┴─────────┴───────────┴─────────────┴───────────────┘

Technical notes:

Function [queensX] constructs a boolean constraint matrix m, in which  the  col-
mums representing diagonals are optional.  As an example, the final  constraints
matrix for the inner function for a 4-Queens problem has these regions:

           ┌───────────────────────────────────── x-diagonal requirements
           │             ┌─────────────────────── y-diagonal    ..  ..
           │             │          ┌──────────── rank (row)    ..  ..
           │             │          │       ┌──── file (col)    ..  ..
           │             │          │       │
    ┌─────────────┬─────────────┬───────┬───────┐
    │0 0 0 1 0 0 0│0 0 0 0 0 0 1│1 0 0 0│1 0 0 0│
    │0 0 1 0 0 0 0│0 0 0 0 0 1 0│1 0 0 0│0 1 0 0│
    │0 1 0 0 0 0 0│0 0 0 0 1 0 0│1 0 0 0│0 0 1 0│
    │1 0 0 0 0 0 0│0 0 0 1 0 0 0│1 0 0 0│0 0 0 1│
    │0 0 0 0 1 0 0│0 0 0 0 0 1 0│0 1 0 0│1 0 0 0│
    │0 0 0 1 0 0 0│0 0 0 0 1 0 0│0 1 0 0│0 1 0 0│
    │0 0 1 0 0 0 0│0 0 0 1 0 0 0│0 1 0 0│0 0 1 0│
    │0 1 0 0 0 0 0│0 0 1 0 0 0 0│0 1 0 0│0 0 0 1│
    │0 0 0 0 0 1 0│0 0 0 0 1 0 0│0 0 1 0│1 0 0 0│
    │0 0 0 0 1 0 0│0 0 0 1 0 0 0│0 0 1 0│0 1 0 0│
    │0 0 0 1 0 0 0│0 0 1 0 0 0 0│0 0 1 0│0 0 1 0│
    │0 0 1 0 0 0 0│0 1 0 0 0 0 0│0 0 1 0│0 0 0 1│
    │0 0 0 0 0 0 1│0 0 0 1 0 0 0│0 0 0 1│1 0 0 0│
    │0 0 0 0 0 1 0│0 0 1 0 0 0 0│0 0 0 1│0 1 0 0│
    │0 0 0 0 1 0 0│0 1 0 0 0 0 0│0 0 0 1│0 0 1 0│
    │0 0 0 1 0 0 0│1 0 0 0 0 0 0│0 0 0 1│0 0 0 1│
    ├─────────────┴─────────────┼───────┴───────┤
    │1 0 0 0 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 1 0 0 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 1 0 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 1 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 1 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 1 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 1 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 0 1 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 0 0 1 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 0 0 0 1 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 0 0 0 0 1 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 0 0 0 0 0 1 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 0 0 0 0 0 0 1 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 0 0 0 0 0 0 0 1│0 0 0 0 0 0 0 0│
    └───────────────────────────┴───────────────┘
                  │                     │
                  │                     └──────── padding for required reqts.
                  └────────────────────────────── dummy rows for optional reqts.

See also: <a href="https://dfns.dyalog.com/n_X.htm">X</a> <a href="https://dfns.dyalog.com/n_queens.htm">queens</a>

Back to: <a href="https://dfns.dyalog.com/n_contents.htm">contents</a>

Back to: <a href="https://dfns.dyalog.com/index.htm">Workspaces</a>
</pre>


</div>||||I||||
Exact cover N-Queens
--------------------
The N-Queens puzzle may be expressed and solved as an exact cover problem:

    queensX←{               ⍝ Exact cover N-Queens.
        m←⍳3/⍵              ⍝ cell coordinate properties.
        r←=/¨1 0 1∘/¨m      ⍝ each rank must contain one queen.
        f←=/¨0 1 1∘/¨m      ⍝  ..  file  ..     ..      ..

        dm←-/¨⍳2/⍵          ⍝ diagonal labels.
        du←{⍵[⍋⍵]}∪,dm      ⍝ unique labels.
        y←⊖x←dm∘.=du        ⍝ x and y diagonals.

        m←,[⍳2]x,y,r,f      ⍝ constraints matrix.

        d←~(⍳1↓⍴m)∊⍳2×⍴du   ⍝ mask of required cols.
        ⍵ ⍵⍴d X m           ⍝ exact cover - matrix of queens.
    }

    ⍝ A solution for each of the first 9 N-Queens problems:

    queensX¨ 0 to 8
┌┬─┬───┬─────┬───────┬─────────┬───────────┬─────────────┬───────────────┐
││1│0 0│0 0 0│0 1 0 0│0 0 0 0 1│0 0 0 0 1 0│0 0 0 0 0 0 1│0 0 0 0 0 0 0 1│
││ │0 0│0 0 0│0 0 0 1│0 1 0 0 0│0 0 1 0 0 0│0 0 0 0 1 0 0│0 0 0 1 0 0 0 0│
││ │   │0 0 0│1 0 0 0│0 0 0 1 0│1 0 0 0 0 0│0 0 1 0 0 0 0│1 0 0 0 0 0 0 0│
││ │   │     │0 0 1 0│1 0 0 0 0│0 0 0 0 0 1│1 0 0 0 0 0 0│0 0 1 0 0 0 0 0│
││ │   │     │       │0 0 1 0 0│0 0 0 1 0 0│0 0 0 0 0 1 0│0 0 0 0 0 1 0 0│
││ │   │     │       │         │0 1 0 0 0 0│0 0 0 1 0 0 0│0 1 0 0 0 0 0 0│
││ │   │     │       │         │           │0 1 0 0 0 0 0│0 0 0 0 0 0 1 0│
││ │   │     │       │         │           │             │0 0 0 0 1 0 0 0│
└┴─┴───┴─────┴───────┴─────────┴───────────┴─────────────┴───────────────┘

Technical notes:

Function [queensX] constructs a boolean constraint matrix m, in which  the  col-
mums representing diagonals are optional.  As an example, the final  constraints
matrix for the inner function for a 4-Queens problem has these regions:

           ┌───────────────────────────────────── x-diagonal requirements
           │             ┌─────────────────────── y-diagonal    ..  ..
           │             │          ┌──────────── rank (row)    ..  ..
           │             │          │       ┌──── file (col)    ..  ..
           │             │          │       │
    ┌─────────────┬─────────────┬───────┬───────┐
    │0 0 0 1 0 0 0│0 0 0 0 0 0 1│1 0 0 0│1 0 0 0│
    │0 0 1 0 0 0 0│0 0 0 0 0 1 0│1 0 0 0│0 1 0 0│
    │0 1 0 0 0 0 0│0 0 0 0 1 0 0│1 0 0 0│0 0 1 0│
    │1 0 0 0 0 0 0│0 0 0 1 0 0 0│1 0 0 0│0 0 0 1│
    │0 0 0 0 1 0 0│0 0 0 0 0 1 0│0 1 0 0│1 0 0 0│
    │0 0 0 1 0 0 0│0 0 0 0 1 0 0│0 1 0 0│0 1 0 0│
    │0 0 1 0 0 0 0│0 0 0 1 0 0 0│0 1 0 0│0 0 1 0│
    │0 1 0 0 0 0 0│0 0 1 0 0 0 0│0 1 0 0│0 0 0 1│
    │0 0 0 0 0 1 0│0 0 0 0 1 0 0│0 0 1 0│1 0 0 0│
    │0 0 0 0 1 0 0│0 0 0 1 0 0 0│0 0 1 0│0 1 0 0│
    │0 0 0 1 0 0 0│0 0 1 0 0 0 0│0 0 1 0│0 0 1 0│
    │0 0 1 0 0 0 0│0 1 0 0 0 0 0│0 0 1 0│0 0 0 1│
    │0 0 0 0 0 0 1│0 0 0 1 0 0 0│0 0 0 1│1 0 0 0│
    │0 0 0 0 0 1 0│0 0 1 0 0 0 0│0 0 0 1│0 1 0 0│
    │0 0 0 0 1 0 0│0 1 0 0 0 0 0│0 0 0 1│0 0 1 0│
    │0 0 0 1 0 0 0│1 0 0 0 0 0 0│0 0 0 1│0 0 0 1│
    ├─────────────┴─────────────┼───────┴───────┤
    │1 0 0 0 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 1 0 0 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 1 0 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 1 0 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 1 0 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 1 0 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 1 0 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 0 1 0 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 0 0 1 0 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 0 0 0 1 0 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 0 0 0 0 1 0 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 0 0 0 0 0 1 0 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 0 0 0 0 0 0 1 0│0 0 0 0 0 0 0 0│
    │0 0 0 0 0 0 0 0 0 0 0 0 0 1│0 0 0 0 0 0 0 0│
    └───────────────────────────┴───────────────┘
                  │                     │
                  │                     └──────── padding for required reqts.
                  └────────────────────────────── dummy rows for optional reqts.

See also: X queens

Back to: contents

Back to: Workspaces

Dyalog APL
https://dfns.dyalog.com/n_queensX.htm