Cyclops Java by example : N-Queens

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.

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

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

The scala solution with a for comprehension looks something like

The n-queens solution from Scala by example

The Java Solution

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.

An Exercise

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.

'Scala By Example' Exercises: Solutions

Defining ‘isSafe’ in Java

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

Showing the solutions

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.