Cyclops Java by example : N-Queens

John McClean
Dec 2, 2016 · 2 min read

The handy e-book Scala By Example contains a lot of nice worked examples to build up your knowledge of the Scala language. As we progress though the book there are many succinct examples, leveraging ever more advanced Scala features. One that particularly caught my eye was the n-queens implementation using for comprehensions, in this post we will show the Scala implementation and also a Java equivalent that also makes use of For Comprehensions and Pattern Matching using cyclops.

Image for post
Image for post
Queens Movement pic by Alma Cebrian, CC3 licence

N-Queens

In the n-queens problem we have to place a number (n) of chess pieces (the Queen) in such a way that they cannot attack each other on a chess board with n rows and columns. Queens can attack along a row, column or diagonal, so any given Queen cannot be placed on a diagonal / row or column with another.

For comprehensions allow us to generate a cartesian product over the data structures provided as inputs. That is they match every combination of each element in each referenced data structure and provide them as input to a user function. This makes them particularly useful for solving combinatorial problems like N-Queens.

The scala solution with a for comprehension looks something like

The n-queens solution from Scala by example

The Java solution using cyclops for comprehensions, is equally succinct.

In the code we recursively check each combination of positions on the board, and when we identify a position from which a Queen is not attacked by the other Queens on the board — we add that piece as a solution and continue until all possibilities are exhausted.

From Scala by example

Write the function

def isSafe(col: Int, queens: List[Int], delta: Int): Boolean

which tests whether a queen in the given column col is safe with respect to the queens already placed. Here, delta is the difference between the row of the queen to be placed and the row of the first queen in the list.

Robert Söding defines a pretty neat solution using pattern matching.

In cyclops all types define a visit method that allows us to visit the decomposed parts of that type. This is what Scala pattern matching does under the hood (see Scala pattern matching a Java Developers perspective for more). In Java we can define isSafe as follows

We can define a show method that will output a pretty-print version of all our solutions

Putting it all together

An finally in a single place — a unit test that runs NQueens for a pre-configured number of Queens.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store