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.
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
The scala solution with a for comprehension looks something like
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.
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
Solutions to the Exercises in the 'Scala By Example' Manual
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.