Solve your sudoku puzzles with Elixir — Part-2

Introduction

In Part-1, we parsed an input_str, create an input_map and apply this map to the initial board. To be ready to follow Part-2, you need this to work.

We will now operate on this representation, which is our map.
If you use my repository then switch to part-2 branch ;)

Project structure

In this part we will create 2 files:

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

Using backtracking : the dumb way

source code
test file

Here is the backtracking algorithm on wikipedia but basically the idea is trying values until it fails, go back, change the values and continue like that until it works.

I tried to explain with words what is going to happend here but it’s always better with a graph.

Data structure

We will work on a list of two-element tuple. Notice that even if we have only one value left, the value is still a list.

stack = [  {{0,0}, [1,2,3,4,5,6,7,8,9]},  {{1,0}, [4]}, ...]

Isolate coordinates that need actions

We will use adding, changing and droping a lot in backtracking. Input values (input_str and input_map) will never change. So let’s put them aside and create a list of coordinates that will change.

Actions

Named functions support multiple clauses. I tend to use this concept a lot so if you are not familiar with anonymous/named functions or multiple clauses (which is pattern matching for functions) you can go here.
You can implement this part to fully understand what’s going on if you want to.

Add

Iterate

Drop

Validating our solutions

source code
test file

Here is the validation code for a row

Logic is the same for columns and boxes, here is your turn ! You can implement the functions for columns, boxes and the general is_valid? which validate the whole board or grab the source file.

Updating our map of possibilities with the stack

The stack is going to be manipulate a lot of time and if we want to have a valid map of possibilities we need to keep it up to date ! This is the goal of update_map which under the hood use our ApplyValues module from
Part-1

Let’s compute !

We will define our run function that will initialize and prepare our data then we will define the do_run that will do the real job

If you want you can try to implement the do_run it’s nothing more than reading the graph.

Do you think it’s working now ?? well let’s test in iex !

Hey ! Hey ! Look at this ! Our first sudoku solved ! Let’s try these:

OMG… the last one was reeaaaaally long what’s going on ? Well we only apply values and start computing by trying all the combinations so it’s not really optimize.
We have 81 elements and 9 possibilities by element and we apply 22 values (81–22) * 9 = 707! which is …

207576258524337698896177151524225074854242955648175239210643078761475202602108525077559515290891351351110307034016495123444464412364875524350597645140229620868130790032690138530694695049246367054571130946075033064302134940333011628172367260056361148177960246555557638036341878499524770808391208897813724084007759298477938328488923286434425930399228800483783090887065470399651578319692252092490954338930291366833402262865330545078294538901950484875337725401943473671983506244470528009322849286081426071406096729103196693674660228748525205262348093188692605376388025207705157999820069430612689808556539222798144084031983619178120136385820181634635005990248117949329794554485037504335845219366098306335802245732242132337295695664043158164143872103485312250361050081386404411236480104069992760729468352458679891764276547593173557861524257747082045633843960761040250390634517554818732489381641894337561016224248814144403491649406679238246764114432288266849768427698831969371306913645073744060296303524557236589864305359003590755226850459437798920413748912158018425189847442165695797649592452650771708792657955433944204771908968431467662297177553896343365004331320534605782038836738323758132680194701583721343079514280001994132460153664463508706711959447486492139554951443193670524598286769870069023743879639231259887834889688540500378555288588856190949617944532068144366614778941951370188796978421351365032025236646451485884580993527815027370460640036522858439827715384411034403297311262733271385601318924824468209728378727043258071656693760000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

possibilities… I’m not kidding. So that’s why it’s a bit long.

I will keep my ‘score’ here in order to compare later:

input_str_1 --> ~400ms
input_str_2 --> ~330ms
input_str_3 --> out of memory on my computer
input_str_4 --> out of memory on my computer
input_str_5 --> ~15s
The euler project n96 --> out of memory on my computer

Conclusion

We finally solve our first puzzles successfully but the satisfaction was short-lived, Our algorithm is slow…
In PART-3 we will find a way to reduce the number of possibilities before using backtracking.