Hi everybody!
I knew that, in one of the Scala Central meetup, a talk was about creating a Sudoku solver. Unfortunately I didn’t attend that talk, but the challenge was nice, so I decided to try by myself to code a solver. Unfortunately I did it in my free time, so I didn’t want to spend too much time on it, this compromised a bit the quality of the code, moreover I want to use this project to revise all the features of Scala, because in BBC we work mainly with Java and Ruby, and Scala is becoming an hobby, so something was made in a weird way just to have the possibility to use some features of the language. But still, I like the result, and I decided to discuss it here.
You can find the repository on Github, and I will follow it to explain everything. I took some sudokus from this page. So, my first idea was that the model for my code should have been simply straightforward: I won’t explain the rules of Sudoku, you can find them here, so basically how should I model a Sudoku? First of all thinking about the grid: the grid is composed by cells that can store a value (I will call those cells Final Value) or not (I will call those cells Optional Value). A Final Value is immutable, an Optional Value it is a cell that is not yet filled, so it stores a list of possible final values. Optional Values need a method (I called it remove) to remove from the list of possibilities a single value. I added also a copy method on both the types of value, because I was thinking to store all the statuses that the Sudoku passed, just for having the complete solution, or to do backtracking in case of non deterministic choices (that, honestly, I thought it was not possible to happen, but unfortunately some difficult sudokus has at least one of them). You can find the two classes, their base trait and all the companion objects here, at that point of the coding I was not really hurrying up yet, so you can find also tests (TDD approach) here.
Then I needed to model the grid. The grid is nothing more than an array of 81 values. But it needs several methods: two for convert coordinates (in the form of (x, y) as expected) from and to index number in the array (position methods), the apply method with the coordinates to return the value in that coordinates, two update method: one with coordinates that is removing a single value, int, from the list of optional values and one that takes a generic value (optional of final) and put it in a cell, six methods for getting and updating a row, a column (vertical row) or a sector related to a cell (x, y).
In the Sudoku class (you can see it here) you can see also a solve method. This is checking all the Optional Values and the ones with only one possibility, it mutates them into Final Values, and it removes from the Optional Values in the row, column and sector its final value. This method is enough for solving the easiest sudokus. But for medium and hard ones we have to apply also a search method that is checking for each row, column and sector if there are remaining final values as option on a single Optional Value. To explain it better, if in a row (or column, or sector) you have not assigned the number 4 and this number is still a valid choice only in one Optional Value in that row, THAT Optional Value should be a Final Value 4.
As an exercise I split the search method in 3 parts: one is the method that takes a generic list of Value Objects and computes the values not yet found and for all of them check how many Optional have that value as an option, an applyLogic that applies a logic by row, column or sector (I used the same method also to write the method to check if a sudoku is in an invalid state or to get the Optional with the minimum number of choices) and a search with no parenthesis (I know, I know, it is not following code conventions but for me it is easier to use) that applies the previous two. To end the explanation of this class, a spawn method to copy a sudoku (I like the word spawn, copy is banal) a method to check if the sudoku is completed and a toString for printing the sudoku state. I wrote some tests, here, but I basically stopped here my TDD approach.
Last but not least, the Solver class (you can find it here). It is not really complicated, the only interesting thing to discuss is the non deterministic path: some very hard sudoku can reach a state in which no Optional can be converted into a Final. So you can basically chose different values to go on. I don’t know if there is some very advanced trick to apply. For me the only solution was to start different threads, one for any optional value in the Optional Value with less choices. I used a Promise to track the first future which completes successfully.
Of course there is a class to read a file with a sudoku, and a main object which extends the App trait. There are also other small details that I didn’t explain (for example, when I search with the method of the sudoku class, a final value that is found is substituted as an Optional with one value: this to have the method solve as the only method that mutates an Optional into a Final… for the same reason the values at the beginning of the computation are read as Optionals with a single choice), but this is, at high level, how the project works.
And obviously it is working fine. Of course in the repository there is an impossible to solve sudoku, that is one sudoku with zero final values: this makes your machine start lot of threads and I left it compute for a lot of time without any result.
Stay tuned!
Leave a Reply