Concurrent Sudoku Solver: Part 3 - Using Cats Effect Queue

Introduction

In Part 2, we used a combination of Ref, Deferred, and IO.race from Cats Effect to implement a concurrent Sudoku solver. In this post, we will use a different concurrency primitive from the Cats Effect standard library, Queue, to write a much simpler Sudoku Solver implementation . As before, you can find all the code we’ll be writing today in the concurrent-sudoku-solver repo.

Queue

You can find queue-like data structures in most languages/frameworks. The Scala standard library itself offers scala.collection.immutable.Queue. In this sense, Cats Effect’s Queue should look quite familiar. What’s nice about Cats Effect Queue however is that it is a purely functional implementation; it’s methods return IO i.e. referentially transparent values. In addition, it can be used in a concurrent fashion safely. Let’s take a closer look at a simplified version of Cats Effect Queue that has only the methods we care about for the purposes of this blogpost:

1. The take method returns an IO that models the effect of dequeueing an element from the front of the queue, potentially blocking (semantically) until an element becomes available.
2. The offer method returns an IO that models the effect of enqueueing the given element at the back of the queue.

Nothing unusual to see there, they’re both relatively simple methods. So how exactly are we going to be using a Queue in our concurrent Sudoku solver?

High level architecture

For our purposes, we will be using Queue as a mechanism for delivering updates to a cell about its peers. Specifically, every time a Cell is solved, we will take its solved Value and offer it to each of its peers’ updatesQueue. Each peer cell will then be able to take Values from their updatesQueue to refine their own internal state of candidates and eventually reach a solution. At which point, they will return their solved Value which will then be offered to each of their peers via their updatesQueue, and so on.

As you can see, this is only slightly different from our solution in Part 2, where each Cell was directly connected to each of its peers via a Deferred. Here, we’ve “decoupled” things a little bit in the sense that we have an external-to-the-cell process that broadcasts changes in the board to each cell, and cells have no awareness of other cells except through their updatesQueue.

Hopefully that all made sense. Before we continue, go ahead and try implementing this yourself! It’s much easier than you think. When you’re done, you can compare with our solution, as follows.

Code

We’ll start by defining a small MissingCell class:

1. To initialize an instance of MissingCell , all we need to provide is a Coord and a Queue.
2. Each MissingCell exposes a solve value of type IO[Candidate.Single] . This IO value models the process of deducing the single candidate solution for this MissingCell, and this is the process we will need to execute for each missing cell in our Sudoku board at the top level of our program.
   
   As you can see though, this value is actually created by the refineToSingleCandidate method which accepts only one argument of type Candidate.Multiple. Recall from Part 1 that the only way to create a Candidate.Multiple is through the Candidate.initial(coord: Coord)method which returns a Candidate.Multiple(coord, Set(1, 2, 3, 4, 5, 6, 7, 8, 9)) i.e. an initial set of candidate values. The purpose of refineToSingleCandidate is to return an IO that refines this down to a Candidate.Single. So let’s take a look at how it does that next.
3. Our refineToSingleCandidate method starts by attempting to take a value from the updatesQueue of this MissingCell. As previously mentioned, this is a semantically blocking action, similar to Deferred.get which we saw in our last post. And again, this blocking behaviour is fine. Until an element is enqueued on this updatesQueue (i.e. until a peer is solved) there is nothing useful we can do anyway so we might as well be blocked.
4. However, once we do obtain a peerValue, we can attempt to refine our existing set of candidates.
5. If we are successful in refining it into a Candidate.Single, we simply return that single value wrapped in an IO.
6. If we are not successful, we call refineToSingleCandidate again with the potentially refined multiple , and we will continue to do this until we hit the terminating condition i.e. step 6. Effectively, what we’ve expressed here is a stateful operation using recursion instead of a mutable variable. Note that IO is naturally stack-safe so we don’t need to write refineToSingleCandidate in a tail-recursive fashion to avoid stack overflow.
7. Eventually though, we will be successful in refining to a Candidate.Single and we return this value (singleCandidate ).

And that’s pretty much it for our MissingCell class. We can provide a convenience make method in the companion object which just takes care of initializing a separate Queue for each instance:

The only worth noting here is that creating a Queue is itself an effectful action.

The last piece of functionality we’re missing is the “broadcast” function that will enqueue solved Value updates to each of the relevant peers’ updatesQueue. This is a trivial matter to code:

1. We filter the list of cells for only those that are peers of the update.
2. We offer (or enqueue) the update on to the updatesQueue of each of the filtered cells. It doesn’t matter for correctness if we did this using parTraverse_ or traverse_ , it just so happens that these are independent actions that we can perform concurrently so we might as well.

Finally, we can take all of these pieces and put them together at the top level of our program in the solve method:

1. First, we generate a Set of givenCoords.
2. Next, we generate a List of missingCoords by filtering out any elements in allCoords that are also in givenCoords.
3. We can now generate a List of MissingCell by passing each element of missingCoords to MissingCell.make.
4. Here we create a broadcast function which is just the broadcastToPeers function we defined earlier with the first argument “filled in” as missingCells.
5. Using the function we created in the previous step, we broadcast the givenValues to the relevant missingCells. All this means is we’re enqueueing the givenValues to the updatesQueue of the relevant MissingCell instances. At this point, we have “seeded” the initial state of the Sudoku board. Now we just need to kick off the process for solving each of the missingCells.
6. We can do that by executing the solve IO on each missingCell and whenever that returns a Candidate.Single, broadcast it to the relevant MissingCell peers. Note that we execute this action concurrently across all missingCells via the parTraverse combinator. If we were to do this sequentially (using just traverse), our program wouldn’t work (unless you were extremely lucky).
7. Lastly, we return the concatenated List of givenValues and the solved missingValues.

And that’s it! We have finished writing another concurrent Sudoku Solver. You can check out the unit tests in the repo if you need more convincing that our code works.

Reflections

Cats EffectQueue offers almost exactly the high-level semantics we needed to solve this problem elegantly. This is in stark contrast with our solution in Part 2 where we had to think explicitly in terms of fibers, shared state, cancellation etc. In general, you should prefer the more structured APIs like Queue from the Cats Effect standard library and only consider using low-level primitives like Ref and Deferred when these fall short of your needs.

One thing you might have noticed about our solution in this post is how, inside the refineToSingleCandidate method, we used Queue to effectively produce a stream of updates about a cell’s peers, and then continuously consumed those updates until we reached a solution. We will take this idea further by writing a streaming oriented solution using the infamous FS2 library in the next and final post of this series.