Elixir Sudoku Solver CLI App

CLI application to solve Sudoku written in Elixir based on Peter Norvig's algorithm.

---

🚀 Features:

In 2006, computer scientist Peter Norvig created a wonderful algorithm for automating Sudoku solving, notable for its relative simplicity and conciseness. This is also partly due to the fact that he developed it in Python. Obviously, languages offer different difficulties for translating algorithms, mainly depending on whether they are high-level or low-level languages.

Here I have tried to make an implementation in Elixir that is not excessively complicated in relation to Python, just a little more verbose, a fact related above all to its character as a functional language, although it must be said that the immutability offered by Elixir is an enormous advantage over Python, which frequently forces us to make "contortions" that are a little confusing for a novice to avoid the difficulty of shared mutability (a nuisance when implementing depth-first search), common in imperative languages.

The algorithm is based primarily on constraint propagation (see this article and this one) and the aforementioned depth-first search. I won't go into detail about them here, but it's worth taking a look at Peter Norvig's post on his own blog.

Finally, to create a command-line application with the module containing the functions that implement the algorithm, I opted for Mix Escripts. Basically, we generate a single executable that packages all the artifacts created in the compilation along with Elixir itself. However, it's not a 100% distributable solution because it requires you to have Erlang/OTP (the runtime and BEAM) installed on your machine. For CLIs creation, you can consult this and this . For other CLI builds, you can see this other repository where I explain other considerations.

---

👨‍🚀 Getting Started:

• Installation

  Obviously, you'll need Elixir and Erlang/OTP installed on your system. I recommend doing this using asdf and following the advice I give here.

  Once this is done, clone this repository, point it to the project root and run the following command (you don't need to run mix deps.get because there are no external dependencies):

  $ MIX_ENV=prod mix do escript.build + escript.install
  

  The above command will compile and install the executable (escript or "Elixir script") in your system directory ~/.mix/escripts/ (or in ~/.asdf/installs/elixir/1.18.4/.mix/escripts/, if you installed Elixir/Erlang via asdf)

  After installation, the escript can be invoked as

  $ ~/.mix/escripts/sudoku  # Or `~/.asdf/installs/elixir/1.18.4/.mix/escripts/sudoku`
  

  For convenience, consider adding ~/.mix/escripts directory to your $PATH environment variable. For more information, check the wikipedia article on PATH: https://en.wikipedia.org/wiki/PATH_(variable).

• Developing/modifying the application in dev mode

  Edit and/or play with the code as you like, but every time you want to verify the output on the command line you'll have to build the escript executable in dev mode (although the truth is that this compiles very quickly):

  $ mix escript.build
  

  The binary is created in the root of the project so you can invoke it directly from the terminal like this:

  $ ./sudoku
  

  Alternatively, you can interact with the code from Elixir's interactive console (IEx), calling the functions you need to test. For example:

  iex -S mix # ==>
  Erlang/OTP 27 [erts-15.2.7] [source] [64-bit] [smp:8:8] [ds:8:8:10] [async-threads:1] [jit:ns]
  
  Interactive Elixir (1.18.4) - press Ctrl+C to exit (type h() ENTER for help)
  iex(1)> import Sudoku.{NorvigSolver, Helper}
  [Sudoku.NorvigSolver, Sudoku.Helper]
  iex(2)> {t, r} = measure(fn -> solve(~c"............1....2..3...56..8.769.35...432.8......1...........9....9.............") end)
  {3.462632,
    {:ok,
     %{
       ~c"E6" => ~c"2",
       ~c"F1" => ~c"7",
      ...
    }}}
  iex(3)> IO.puts("This puzzle took #{Float.round(t, 3)}s to solve:")
  This puzzle took 3.463s to solve:
  :ok
  iex(4)> r |> fmap(&display/1)
  
  ====================
  2 4 9 |6 7 5 |8 1 3 
  5 7 6 |1 8 3 |9 4 2 
  8 1 3 |9 2 4 |5 6 7 
  ------+------+------
  4 8 1 |7 6 9 |2 3 5 
  9 6 5 |4 3 2 |7 8 1 
  7 3 2 |8 5 1 |6 9 4 
  ------+------+------
  6 2 4 |5 1 8 |3 7 9 
  1 5 8 |3 9 7 |4 2 6 
  3 9 7 |2 4 6 |1 5 8 
  ====================
  
  :ok
  iex(5)>    
  

---

🖥️ Using the application

If you've already installed the application as explained above and set it to your system's PATH, you can start interacting with it. Launch it from the terminal by running:

$ sudoku -h # e.g.

This prints the application's help, although it's hardly necessary. To give the application a Sudoku puzzle to solve, simply do the following:

$ sudoku -s 8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..
# ==>

====================
8 1 2 |7 5 3 |6 4 9 
9 4 3 |6 8 2 |1 7 5 
6 7 5 |4 9 1 |2 8 3 
------+------+------
1 5 4 |2 3 7 |8 9 6 
3 6 9 |8 4 5 |7 2 1 
2 8 7 |1 6 9 |5 3 4 
------+------+------
5 2 1 |9 7 4 |3 6 8 
4 3 8 |5 2 6 |9 1 7 
7 9 6 |3 1 8 |4 5 2 
====================

The argument 8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4.. is the input to be solved, although the dots (representing blank spaces) can also be replaced by zeros.

To generate a sudoku puzzle to solve, run this:

$ sudoku -g
# ==>

====================
. 1 4 |6 . . |. . . 
. . . |8 . . |1 4 . 
. . . |1 . 4 |. . 5 
------+------+------
. . . |. . . |. . . 
. . . |. . . |. . 2 
8 . . |. . 5 |. . 4 
------+------+------
. . . |. . 3 |. . . 
. . . |2 1 . |. . . 
. 9 . |. . 7 |. 3 . 
====================

This grid returned by the previous command can also be passed directly to our CLI application to resolve:

$  sudoku -s '. 1 4 |6 . . |. . . 
. . . |8 . . |1 4 . 
. . . |1 . 4 |. . 5 
------+------+------
. . . |. . . |. . . 
. . . |. . . |. . 2 
8 . . |. . 5 |. . 4 
------+------+------
. . . |. . 3 |. . . 
. . . |2 1 . |. . . 
. 9 . |. . 7 |. 3 .' # Don't forget to put quotes around the grid!

And that's all it takes!!

---

📚 Learn more

• About Mix Escript: https://hexdocs.pm/mix/main/Mix.Tasks.Escript.html [and following pages]

• About the Elixir OptionParser module: https://hexdocs.pm/elixir/OptionParser.html#parse/2-examples

• Executables (for creating CLI apps - at Elixir School): https://elixirschool.com/en/lessons/intermediate/escripts

• CLI apps in Elixir. Part 2: https://brewingelixir.com/cli-apps-in-elixir-part-2

  
  

  Other references (mostly for Python):

• Solving Every Sudoku Puzzle by Peter Norvig: https://norvig.com/sudoku.html

• Solving Every Sudoku Puzzle Quickly: https://norvig.com/CQ/sudoku.html

• Beautiful Sudoku Solver by Peter Norvig: https://kikaben.com/sudoku-solver-by-peter-norvig/

• How to Play and Win Sudoku - Using Math and Machine Learning to Solve Every Sudoku Puzzle: https://www.freecodecamp.org/news/how-to-play-and-win-sudoku-using-math-and-machine-learning-to-solve-every-sudoku-puzzle/

• Sudoku Solver by Peter Norvig (python3): https://naokishibuya.medium.com/peter-norvigs-sudoku-solver-25779bb349ce

• Solving Sudoku efficiently with Dancing Links: https://www.kth.se/social/files/58861771f276547fe1dbf8d1/HLaestanderMHarrysson_dkand14.pdf

• The World’s Hardest Sudoku by Arto Inkala: https://abakcus.com/article/the-worlds-hardest-sudoku-by-arto-inkala/

• See: https://www.sudokuwiki.org/sudoku.htm?bd=800000000003600000070090200050007000000045700000100030001000068008500010090000400

---

Happy coding 😀!!