N-Queens Combinatorial Puzzle meets Cats

Published: Aug 3rd 2023

Description: view

Video Recording: view on YouTube (recommended quality: 720p or 1080p)

Slideshow: view

All slides, with transcript: view

Slides PDF: download(for perfect image quality)

Speakerdeck: slideshow

Slideshare: slideshow

Scala code: github repo

• This talk was presented on Aug 3rd 2023 during the following Scala in the City event @ ITV https://www.meetup.com/scala-in-the-city/events/292844968/


• At the centre of this talk is the N-Queens combinatorial puzzle. The reason why this puzzle features in the Scala book and functional programming course by Martin Odersky (the language’s creator), is that such puzzles are a particularly suitable application area of for comprehensions.


• We’ll start by (re)acquainting ourselves with the puzzle, and seeing the role played in it by permutations. Next, we’ll see how, when wanting to visualise candidate puzzle solutions, Cats’ monoidal functions fold and foldMap are a great fit for combining images.


• While we are all very familiar with the triad providing the bread, butter and jam of functional programming, i.e. map, filter and fold, not everyone knows about the corresponding functions in Cats’ monadic variant of the triad, i.e. mapM, filterM and foldM, which we are going to learn about next.


• As is often the case in functional programming, the traverse function makes an appearance, and we shall grab the opportunity to point out the symmetry that exists in the interrelation of flatMap / foldMap / traverse and flatten / fold / sequence.


• Armed with an understanding of foldM, we then look at how such a function can be used to implement an iterative algorithm for the N-Queens puzzle.


• The talk ends by pointing out that the iterative algorithm is smarter than the recursive one, because it ‘remembers’ where it has already placed previous queens.