I started learning Elixir few months ago and after finishing the Elixir channel on Exercism.io, I was looking for a bigger project. I had this Euler project in my head for a long time and the timing was excellent to start it.
Sudoku is maybe not the most exciting thing but everybody knows what it is and probably already tried once to solve one. So people will be more likely to understand me if I write an article or show the project for job interviews.
First things first, You need to install Elixir on your computer. Then you should see something like this:
elixir --version
Erlang/OTP 18 [erts-7.3] [source] [64-bit] [smp:4:4] [async-threads:10] [kernel-poll:false]
Elixir 1.3.2
mix --version
Erlang/OTP 18 [erts-7.3] [source] [64-bit] [smp:4:4] [async-threads:10] [kernel-poll:false]
Mix 1.3.2Use mix to create and test your project
mix new sudoku
cd sudoku
mix test
Compiling 1 file (.ex)
Generated sudoku app
.
Finished in 0.04 seconds
1 test, 0 failuresBefore we start, I will try to let you the choice of just reading the article or coding the project. Here you will find the source code and the tests. When all the tests are green for a module you can continue.
At the end of this part you will be able to generate an empty board, apply initial values on it and generate this:
- There are 9 rows from 0 to 8 and this one is the first one (be careful this is 0 based)
[{0, 1}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}, {6, 1}, {7, 1}, {8, 1}]
- There are 9 columns from 0 to 8 and this one is the first one
[{1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}]
- There are 9 boxes and this one is the number zero
[{0,0} {1,0} {2,0} {0,1} {1,1} {2,1} {0,2} {1,2} {2,2}]
Rows, columns, boxes are also called units.
We will create 2 modules Sudoku.Board and Sudoku.ApplyValues.
I will follow the Programming Elixir 1.2 book conventions
to create the structure of the project.
├── _build
...
├── config
│ └── config.exs
├── index.js
├── lib
│ ├── sudoku
│ │ ├── board.ex <--
│ │ ├── data_structure_utils.ex <--
│ │ ├── strategies
│ │ │ ├── apply_values.ex <--
│ └── sudoku.ex
├── mix.exs
├── package.json
├── README.md
├── stuff.js
└── test
├── sudoku_board_test.exs <--
├── sudoku_test.exs
└── test_helper.exs# board.ex
defmodule Sudoku.Board do
def generate_row(n, size \\ 9) do
Enum.reduce((size - 1)..0, [], &( [{&1, n} | &2]) )
end
endNotice the default parameter and the way we define our range, by starting at the end, we don't have to
Enum.reversethe list. If you want to test your work you can use iex.
iex -S mix # load the context of our project in the shell
Sudoku.Board.generate_row(4)
[{0,4},{1,4},{2,4},{3,4},{4,4},{5,4},{6,4},{7,4},{8,4}]
Cool ! Let's use our test file:
# sudoku_board_test.exs
defmodule SudokuBoardTest do
use ExUnit.Case, async: true
test "get coordinates of row number 4 (0 based)" do
assert Sudoku.Board.generate_row(4) ==
[{0,4},{1,4},{2,4},{3,4},{4,4},{5,4},{6,4},{7,4},{8,4}]
end
endDid you notice the difference between source code file extension and test one ? *.ex files are source files and will be compiled while *.exs will not be compiled ! They are scripts.
At the root of your project invoke mix test to run your test.
We have to do the same from 0 to 8.
# board.ex
defmodule Sudoku.Board do
...
def generate_rows(size \\ 9) do
Enum.reduce((size - 1)..0, [], &([generate_row(&1, size) | &2]))
end
endand test it
# sudoku_board_test.exs
defmodule SudokuBoardTest do
use ExUnit.Case, async: true
...
test "generate_rows" do
assert Sudoku.Board.generate_rows == [
[{0,0},{1,0},{2,0},{3,0},{4,0},{5,0},{6,0},{7,0},{8,0},],
[{0,1},{1,1},{2,1},{3,1},{4,1},{5,1},{6,1},{7,1},{8,1},],
[{0,2},{1,2},{2,2},{3,2},{4,2},{5,2},{6,2},{7,2},{8,2},],
[{0,3},{1,3},{2,3},{3,3},{4,3},{5,3},{6,3},{7,3},{8,3},],
[{0,4},{1,4},{2,4},{3,4},{4,4},{5,4},{6,4},{7,4},{8,4},],
[{0,5},{1,5},{2,5},{3,5},{4,5},{5,5},{6,5},{7,5},{8,5},],
[{0,6},{1,6},{2,6},{3,6},{4,6},{5,6},{6,6},{7,6},{8,6},],
[{0,7},{1,7},{2,7},{3,7},{4,7},{5,7},{6,7},{7,7},{8,7},],
[{0,8},{1,8},{2,8},{3,8},{4,8},{5,8},{6,8},{7,8},{8,8},],
]
end
endLogic is the same for columns and boxes.
Here you can code a bit to generate columns and boxes and run your code against my test file or check out my version here.
We will finish this part by the init function which will generate our empty board. We will basically map every coordinates with all the possibilities.
# board.ex
defmodule Sudoku.Board do
...
def init do
generate_rows
|> List.flatten
|> Enum.reduce(%{}, fn(tuple,acc) ->
Map.put(acc, tuple, Integer.digits(123456789))
end)
end
endTry it in iex !
iex -S mix
Sudoku.Board.init |> IO.inspect(limit: :infinity)
%{
{3, 3} => [1, 2, 3, 4, 5, 6, 7, 8, 9],
{7, 6} => [1, 2, 3, 4, 5, 6, 7, 8, 9],
{7, 8} => [1, 2, 3, 4, 5, 6, 7, 8, 9],
{4, 0} => [1, 2, 3, 4, 5, 6, 7, 8, 9],
...
...
...
{8, 3} => [1, 2, 3, 4, 5, 6, 7, 8, 9],
{0, 4} => [1, 2, 3, 4, 5, 6, 7, 8, 9],
{4, 4} => [1, 2, 3, 4, 5, 6, 7, 8, 9],
{4, 8} => [1, 2, 3, 4, 5, 6, 7, 8, 9],
{5, 0} => [1, 2, 3, 4, 5, 6, 7, 8, 9],
{0, 1} => [1, 2, 3, 4, 5, 6, 7, 8, 9],
{7, 3} => [1, 2, 3, 4, 5, 6, 7, 8, 9],
}This is our puzzle:
input_str = 003020600900305001001806400008102900700000008006708200002609500800203009005010300
We will create a map (input_map) that represents our input.
# data_structure_utils.ex
defmodule Sudoku.DataStructureUtils do
def input_str_to_map(input_str) do
l = String.length(input_str)
if l !== 81, do: raise Sudoku.DataStructureUtils.BadInputLength
Enum.reduce(0..(l-1), %{}, fn(n, acc) ->
char = String.at(input_str, n)
if char !== "0" do
value = [String.to_integer(char)]
Map.put(acc, {rem(n,9), div(n,9)}, value)
else
acc
end
end)
end
defmodule BadInputLength do
defexception []
def message(_), do: "Please provide an input with 81 numbers"
end
endthen apply the input_map to our board
# strategies/apply_values.ex
def run(map, values) do
Enum.reduce(Map.keys(values), map, fn(key, acc) ->
Map.put(acc, key, Map.get(values, key))
end)
endLet's see that in action:
iex -S mix
input_map = Sudoku.DataStructureUtils.input_str_to_map("003020600900305001001806400008102900700000008006708200002609500800203009005010300")
Sudoku.ApplyValues.run(Sudoku.Board.init, input_map) |> IO.inspect(limit: :infinity)
%{
{3, 3} => [1],
{4, 0} => [2],
{2, 2} => [1],
{2, 0} => [3],
{6, 3} => '\t',
{5, 7} => [3],
{5, 1} => [5],
{0, 7} => '\b',
{8, 7} => '\t',
{3, 1} => [3],
{5, 6} => '\t',
{6, 2} => [4],
{6, 8} => [3],
{3, 5} => '\a',
{2, 8} => [5],
{3, 7} => [2],
{5, 2} => [6],
{3, 6} => [6],
{2, 3} => '\b',
{8, 1} => [1],
{8, 4} => '\b',
{5, 3} => [2],
{2, 6} => [2],
{6, 6} => [5],
{6, 0} => [6],
{6, 5} => [2],
{5, 5} => '\b',
{3, 2} => '\b',
{2, 5} => [6],
{0, 4} => '\a',
{0, 1} => '\t',
{4, 8} => [1],
{7, 6} => [1, 2, 3, 4, 5, 6, 7, 8, 9],
...
...
...
{7, 3} => [1, 2, 3, 4, 5, 6, 7, 8, 9],
}UGLY right ?! Let's fix that
├── _build
...
├── config
│ └── config.exs
├── index.js
├── lib
│ ├── sudoku
│ │ ├── board.ex
│ │ ├── display.ex <--
│ │ ├── strategies
│ │ │ ├── apply_values.ex
│ └── sudoku.ex
├── mix.exs
├── package.json
├── README.md
├── stuff.js
└── test
├── sudoku_board_test.exs
├── sudoku_test.exs
└── test_helper.exsThis part is not mandatory to run our project but if something goes wrong it's will be helpful !
If you want to code this part, one thing to know is that every item has to have the same size.
For that you can use String.pad_trailing.
Then try to:
- drawing a item
- drawing a line of items
- drawing a line of separation
If everything goes well, you will see a less ugly representation now ;) using iex
iex -S mix
input_map = Sudoku.DataStructureUtils.input_str_to_map("003020600900305001001806400008102900700000008006708200002609500800203009005010300")
Sudoku.ApplyValues.run(Sudoku.Board.init, input_map) |> Sudoku.Display.pretty(false)That all for Part-1 ! And we don’t even solve a puzzle :(. In Part-2 we will start for real by using the backtracking algorithm.