Concurrent Sudoku Solver: Part 1 - Single Candidate Technique + Domain Modelling

Introduction

The Cats Effect family of libraries is well known in the Scala ecosystem. In addition to functional programming capabilities, they also offer a number of primitives for writing concurrent programs in a referentially transparent and highly composable fashion. In this series of blogposts, we’ll be exploring how we can leverage these capabilities to write a concurrent Sudoku solver in a few different ways. This will be a four-part series consisting of:

• Part 1 - Single Candidate Technique + Domain Modelling
• Part 2 - Using Cats Effect Ref + Deferred + IO.race
• Part 3 - Using Cats Effect Queue
• Part 4 - Using FS2 Stream + Topic

In this first post, we will be mostly laying the groundwork for future posts by going over basic Sudoku theory and modelling some reusable elements in the Sudoku domain.

Heads-up

Some things to be aware of before you decide to embark on this journey:

1. The “algorithm” we’ll be implementing is very basic and only capable of solving easy Sudoku puzzles. The point of this blogpost series is not to build a super-duper Sudoku solver but rather to demonstrate concurrent programming capabilities in Cats Effect and FS2.
2. For the sake of brevity, we will assume you already have some familiarity with Cats Effect and FS2. For example, while we won’t explain what .traverse does, we will discuss its concurrent sibling .parTraverse.
3. We’ll write most of the code together but we’ll skip things like imports. You can find all of the code in the concurrent-sudoku-solver repository.

Single Candidate Technique

Simple Sudoku puzzles can be solved using just the Single (or Sole) Candidate technique. We can summarize the whole technique in a couple of sentences. Basically, if we have eliminated all other possibilities for a cell and only one choice remains, this must be the correct value. You can eliminate possibilities by applying the rules of Sudoku i.e. a particular digit (1 – 9) can only occur once in each row, column, and box. For example, let’s say we have the following Sudoku board and we’re trying to figure out what digit goes into the cell shaded in yellow:

In this case, we can logically deduce that the yellow cell:

• Can’t be 1 or 2 or 3 because they already exist in the same row.
• Can’t be 4 or 5 or 6 because they already exist in the same column.
• Can’t be 7 or 8 because they already exist in the same box.
• Must be 9 as that is the only remaining digit.

What’s great about this technique is that we can model it as a process that can be independently executed for each and every cell on the board, making it amenable to a concurrency based implementation. More specifically, each cell should:

• Maintain an internal state of candidates
• React whenever any of its 20 peers (cells in the same row, column, or box as this cell) are solved by removing the peer’s value from the internal state of possible candidates
• Return the cell’s solution when the internal state of candidates is reduced to exactly one possibility

The key thing to note about this process is that every time a cell is solved, it sets off a chain reaction in which the solved cell’s peers react by attempting to use the solved cell’s value to to solve themselves. Any peers that are then solved would then in turn cause their own (unsolved) peers to react by attempting to solve themselves, and so on in a virtuous loop until eventually all the cells on the board are solved.

In this series, we will see how we can express this program in a number of different ways. However, before we dive into the wonderful world of concurrency, we’ll need to do the bare minimum in domain modelling to set ourselves up for success later.

Domain Modelling

We’ll start by defining the interface our concurrent Sudoku solver implementations will need to satisfy:

As you can see, there is just one method solve that we need to define to satisfy this interface and this will take one argument, a List of Given values (i.e. the initial clues on the board), and is expected to return an F of a List containing the solved Value for all 81 cells on a Sudoku board. We’ll talk more about Value and Value.Given shortly. Note that while this signature isn’t completely type-safe (e.g. we could just return IO.pure(List.empty[Value])), writing the compile-time machinery to fix this is an unnecessary distraction for our purposes here. Also, don’t worry too much about the higher-kinded F type either; for most of this series this will just be hardcoded to IO.

Next, we have the Coord class:

The Coord class features two fields; row and col (short for “column”) and the intersection of those two fields can be used to uniquely identify a cell’s position on a Sudoku board. In addition, we have a isPeerOf method attached to each instance of Coord which accepts another Coord as an argument (that) and returns a boolean indicating whether that coord is a peer of this coord. Lastly, we have a few useful values in the companion object including allCoords which is a list of all the valid Coord values in a typical 9x9 Sudoku board.

Finally, let’s talk about the following code:

First, we have a couple of sealed traits and classes that express the following sub-typing hierarchy:

• Value: Represents the idea of a final value that belongs to a co-ordinate. This could be either a:
  - a Given i.e. one of the initial clues given to us on the board or
  - a Single i.e. the single candidate that we’ve deduced for a cell.
• Candidate: Represents the idea of candidate values for a coordinate. This could be either a:
  - Multiple i.e. there are multiple candidates that could fill this cell or
  - Single i.e. there is only one valid candidate that could fill this cell

The interesting thing to note is that Single is both a Value and a Candidate.

Secondly, through our use of the private[Candidate] access modifier, we have enforced at compile time the following:

• a Candidate.Multiple can only be constructed via the initial method which initializes it with the natural default value ofSet(1, 2, 3, 4, 5, 6, 7, 8, 9)
• a Candidate.Single cannot be constructed directly through any method; a Candidate.Single can only be obtained using the refine method on a Candidate.Multiple instance.

Thirdly, you can think of the refine method as codifying the Single Candidate technique. It takes any Value (either a Given or Single) and removes the given Value.value from the set of candidates if the Value.coord is a peer of the coord, returning either a Multiple or Single based on the number of remaining candidates. Given the constraints enforced by private[Candidate] access modifiers, anyone attempting to use these domain objects is forced to use our implementation of the Single Candidate technique via the refine method to reach a solution.

There’s potentially other simpler ways we could have modelled this domain, but this particular approach has netted us some compile-time guarantees. It’s far from perfect but if we really wanted more than this, we’d be better off using something like Idris (possibly a topic for a future blogpost).

That’s it for domain modelling. We didn’t write a whole lot of code in this post, and we haven’t even so much as imported anything from Cats Effect yet! For that and more, join us in Part 2 of the series.