Solve your sudoku puzzles with Elixir — Part-3

Introduction

Now, we can solve easy sudoku puzzles with our algorithm and this is great !
In our implementation, I made a simplification on the ApplyValues module.
It just sets the value but do not apply constraints on the units containing the value. Which means if we apply {0,0} -> 3, the 3 units containing {0,0} have to remove the value 3 from the possibilities.

It’s huge because it removes 24 possibilities:

row + column + box = 27 possibilities
and as the element {0,0} appears 3 times, once in each unit
27 - 3 = 24

In this part we will update our apply values process to do what we have just said. Then use a new strategy to reduce the number of possibilities before using backtracking. And to finish, we will create a Main module to orchestrate our algorithms.

Project structure

├── _build
...
├── config
│   └── config.exs
├── index.js
├── lib
│   ├── sudoku
│   │   ├── board.ex
│   │   ├── backtracking.ex
│   │   ├── data_structure_utils.ex
│   │   ├── strategies
│   │   │   ├── apply_values.ex  <-- (update)
│   │   │   └── naked_single.ex <--
│   │   ├── main.ex <--
│   │   └── validation.ex
│   └── sudoku.ex
├── mix.exs
├── package.json
├── README.md
├── stuff.js
└── test
    ├── sudoku_board_test.exs
    ├── sudoku_apply_values_test.exs <--
    ├── sudoku_naked_single_test.exs <--
    ├── sudoku_test.exs
    └── test_helper.exs

Improve the apply values process

source code
test file

Let’s refactoring our Sudoku.ApplyValues module.

Remember our update_map from the Backtracking module ?
Every time this function is called in order to apply new values now, it removes up to 24 possibilities !!

Let’s try that in iex.

Wow in part-2 input_str_5 took us ~15s and now it’s less than a sec ! It’s time to try our “out of memory” puzzles

Fast !!!

OMG… again ?! It took us ages to solve this one ! but we solved it … input_str4 is probably one of the most difficult ! but anyway it’s too long ! What can we do now ? Well it turns out that there are a lot of strategies in sudoku ! We will use a simple one call naked single

Using the naked single strategy

Introduction

Here is an example of what it does:

On row 0, There is only one element where we can apply 6 ! so apply it !

Implementation

source file
test file

This function is the most important to understand this strategy, again, if you want you can try to implement it yourself copy/paste my test file and use mix test to see if it’s green.

Then continue implementing or copy/paste my files

Create the Main module to orchestrate algorithms

Is it enough for our well known revolted sudoku called input_str_4 ? Well as usual try it in iex !

Conclusion

Well I guess it’s over ! we reach the goal ! There are tons of way to improve this project but for now it’s fast enough for what I want to do with it ;)
I’m counting on you to improve it.
I feel really comfortable writing this project thanks to Exercism.io. so again use it without moderation.

Thank you for reading.

PS: I solve Euler project n96 do you ?