I love to solve sudokus. Every cell must have the exact digit. If you are wrong, you fix a row but at the same time you break a column or a square (it happens the same when you deal with complex software systems, but this is another story…).

To solve them, I have gathered a set of tricks I can apply sistematically. It requires focus and discipline. But they usually let me get the work done.

One day, I wondered… Can I implement these tricks into an application? And I starting building in my mind the classes needed to implement a sudoku solver. And I came up with this implementation in PHP (you can find it in my github repository).

The classes

Structural classes

• 

• They are kept in the namespace Domain\Sudoku\Entity.
• Their responsibility is to keep the status of the sudoku while it is solved.
• You will find classes like Board, Cell, Column or Square.

Strategy classes

• They are kept in the namespace Domain\Sudoku\Strategy\Strategy.
• Their responsibility is to solve the sudoku.
• I have added a Strategy class for every trick I have implemented.
• When the algorithm is too complex, I have splitted part of the strategy into a Substrategy class.
• They are grouped into a collection, returned by a class implementing the interface Domain\Sudoku\Strategy\StragiesLoader.

Use case classes

• They are kept in namespace Domain\Sudoku\Application\Handler.
• They are the entry point into the domain.
• There should be a class for each use case.
• There is one single class of this type so far: SolveSudoku, responsible to orchestrate the solving of the provided sudoku.

Value object classes

• They are kept in Domain\Sudoku\ValueObject.
• You will find value objects like Position, Status or Result.
• There is one special subtype of value objects in Domain\Sudoku\ValueObject\CellContent. They are the different types of content a cell can have: Fixed, Found, Nothing or Tied.
• There is another subtype Domain\Sudoku\ValueObject\Event. These are the different events the application will publish.

The Domain namespace

You will notice all these classes are into the same namespace Domain.

I have followed this guideline: all classes involved with the implementation of the solution are in this namespace.

It is the namespace where almost all the work is done.

The infrastructure namespace

The other main namespace is Infrastructure where I have the classes responsible of:

• Implementing the interface with the outer world (right now, the only interface is a command line application implemented by Infrastructure\Command\Sudoku.
• Implementing any interface needed by the domain (the only class of this type so far is Infrastructure\Domain\Sudoky\Strategy\StrategiesLoaderHardcoded.

Command line version

So far, the only way to use this application is by its command line version (when I have some time, I will implement a REST API version…).

It is implemented in Infrastucture\Command\SolveSudoku. This is a Symfony command console:

• It will expect the following parameters:
  • A file with the initial sudoku.
  • A parameter return_steps to return the performed steps (apart from the solution).
  • A parameter max_iterations to setup how many iterations to try before giving up.
• It will setup the desired logging level (from optional argument –v).
• It will read the provided file and convert it into a valid array.
• It will call the use case class Domain\Sudoku\Application\Handler\SolveSudoku.
• It will convert the result of the command (optionally, including the steps) to json and will return it to the console.

The domain command handler workflow

• 

• Domain\Sudoku\Application\Handler\SolveSudoku will receive the sudoku to solve (inside a Domain\Sudoku\Application\SolveSudoku payload, built and passed by the infrastructure).
• SolveSudoku will build a Domain\Sudoku\Entity\Board object with the data.
• SolveSudoku will use the injected Domain\Strategy\StrategiesLoader to load the different Domain\Sudoku\Strategy\Strategy classes.
• SolveSudoku will start applying the loaded strategies to the board up until:
  • The sudoku is solved.
  • The max number of iterations is reached.
  • The sudoku is in a wrong status.

The strategies

For every trick I can apply to solve a sudoku, I have implemented one strategy. They are on Domain\Sudoku\Application\Strategy\Strategy.

If the strategy is too complex to phpunit it, I have sometimes splitted part of it into a class (in the subfolder Substrategy).

I don’t have a definite option to load all these strategies into the SolveSudoku command handler:

• I may use a Symfony configuration.
• Or perhaps a folder scanner.

This is the reason I am using an interface Domain\Sudoku\Strategy\StrategiesLoader to delay my decision.

So far, I have implemented it returning a hardcoded array of strategies. It is in class Infrastructure\Domain\Sudoku\Strategy\StrategiesLoaderHardcoded.

Conclusions?

For me, the most important part is not the result but the journey itself. It is nice to work without any deadlines so you have room to discover new behaviours and refactor whatever you need.

This post is getting too long. So I have skipped explaining some details. Like event managing, logging and exception handling. I have written another post about it.

In the future, I would like to test it more thoroughly (more complex sudokus) and implement some pending strategies (they are a bit more difficult to code, I am afraid).

I would also like to implement a REST API. Even a javascript front end.

I hope you have enjoyed it as much as I did.