Stuff 'n Things

I’ve loved working on Guardian, but one thing has bothered me. When you logout, vanilla Guardian (and all vanilla JWT implementations) don’t actuall invalidate the token. All the information for the token is stored inside the token itself.

This can lead to short term expiry keys to try and keep a handle on it. Even with this, you can’t actually revoke a token, so when someone logs out, their token is still valid.

Initially my thought was to try and tie the token to the CSRF token, but this turned out not to be such a good idea (and practially impossible with masked CSRF tokens). Instead I wanted a way to keep a tight leash on tokens, when you log out they should no longer be valid. I didn’t want to load up Guardian with a bunch of database assumptions and baggage for everyones app though so it had to stay out of Guardian core.

The result is GuardianDb. This is a simple plugin that integrates via Guardian.Hooks.

With it:

• Every token is stored in the database (keyed by the jti - uuid)
• When it is encoded, a database entry is created
• Every time you verify (page request) a token it is checked. If the entry is missing, it does not verify
• When you logout, or call Guardian.revoke! the entry is removed

You can also clear out stale tokens by using GuardianDb.Token.purge_expired_tokens!

Setup is simple (and included in the README.md). Generate the migration and then add to your config:

config :guardian, Guardian,
       hooks: GuardianDb,
       # …

config :guardian_db, GuardianDb, repo: MyApp.Repo

You’ll need Guardian 0.6.1 or greater to have the right hooks available.

I’ve been getting some feedback that some of the modules and function aren’t named such that their behaviour is immediately apparent, so I’ve renamed them. The rename comes in with 0.6.0 and shouldn’t impact everyone.

The changes are:

Guardian.mint -> Guardian.encode_and_sign
Guardian.verify -> Guardian.decode_and_verify

Guardian.Plug.EnsureSession -> Guardian.Plug.EnsureAuthenticated
Guardian.Plug.VerifyAuthorization -> Guardian.Plug.VerifyHeader

The function signatures and module behaviour remains the same, it’s just a rename.

Some time ago I introduced Hooks to Guardian. Hooks are a mechanism for you to plug-in to lifecycle of authentication. These can be useful to extend or customize the behaviour of Guardian within your application.

A Guardian.Hook is implemented as a behvaiour with default implementations of each callback so you only need to implement what you’re interested in. The available hooks are:

defcallback before_encode_and_sign(resource :: term, type :: atom, claims :: Map)
defcallback after_encode_and_sign(resource :: term, type :: atom, claims :: Map, token :: String.t)
defcallback after_sign_in(conn :: Plug.Conn.t, location :: atom | nil)
defcallback before_sign_out(conn :: Plug.Conn.t, location :: atom | nil)
defcallback on_verify(claims :: Map, jwt :: String.t)
defcallback on_revoke(claims :: Map, jwt :: String.t)

To create your own module just use the Guardian.Hooks module.

defmodule MyHooks do
  use Guardian.Hooks

  def before_encode_and_sign(resource, type, claims) do
    # to keep this as an authenticated token, return { :ok, { resource, type, claims }
    # to fail and prevent the mint from happening return { :error, :reason }
  end
end

before_encode_and_sign

Runs before the jwt is generated. This can be used to add claims, or halt and return an error.

after_encode_and_sign

This runs after the JWT has been encoded. Returning an error will not halt, but can be used to to extend behaviour. For example store the token in a DB.

after_sign_in

Runs after a token is signed in (via a session). Use this to record information about logins etc.

When you’re verifying tokens with Guardian, for API access you probably want to use the Authorization header.

Usually these headers look something like

Authorization: Bearer <token>

The bearer part is known as the realm. You might want to use different realms. I remember writing and OAuth provider, and as part of renewing your token the API required that the client and user tokens were set. For example, the client being the application requesting the renual, and the user for the user who owns the token.

These authentication headers can both be set on the same response.

Authorization: Client <application token>
Authorization: User <user token>

Guardian can handle the easy case of token or many if that’s what you need. These can go in your route file to form a plugin, or you can use them directly in a controller.

Using the above as an example, you can include them in your pipelines

pipeline :api do
  plug :accepts, ["json"]
  plug Guardian.Plug.VerifyHeader, realm: "Client", key: :default
  plug Guardian.Plug.VerifyHeader, realm: "User", key: :user
  plug Guardian.Plug.LoadResource, key: :user
end

Inside your controller action, you can access each set in the usual ways:

  plug Guardian.Plug.EnsureAuthenticated, on_failure: { SomeModule, :client_failure }
  plug Guardian.Plug.EnsureAuthenticated, on_failure: { SomeModule, :user_failure }, key: :user

  def index(conn, params) do
    Guardian.Plug.claims(conn) # Fetch the claims for the client/application
    Guardian.Plug.claims(conn, :user) # Fetch the claims for the user
    # snip
  end

Adding realm support is important for supporting robust API support. Having it integrated seamlessly with Guardian should make it dead simple.

Recently masked CSRF tokens have shown up in Phoenix. Masked CSRF tokens are an important feature to prevent against the BREACH attack.

Unfortunately masked tokens are incompatible with the way Guardian was using them. It’s not all bad though, working through it, it turns out that the way Guardian was putting the CSRF into the JWT wasn’t actually buying much in terms of security. Since you need both pieces of information to connect to a channel, you essentially have the lock and key and can reply the token.

After reviewing it I’ve decided to remove the functionality from Guardian. From here it’s clear that there needs to be a more robust solution for revoking tokens. That’ll be the focus of the next round of work on Guardian.

Update: 30-08-20 updated for the 0.6.0 API

Over my last couple of posts I’ve talked about getting started, permissions and simple email/password auth. It occured to me that I haven’t covered how to do an API authentication.

Part of the beauty of using JWT is that they have an expiry time built into them. In my examples I typically expire them in 30 days, but you can configure (or overwrite) this to be any value.

So we’ve added Guardian, created a user and we so far have the ability to create a ‘login’ where they’re logged into the session, but what about API endpoints.

One thing that Guardian can do easily is authenticate your application for API endpoints. Lets take a quick look at how that works.

In your router, add:

  pipeline :api do
    plug :accepts, ["json"]
    plug Guardian.Plug.VerifyHeader
    plug Guardian.Plug.LoadResource
  end

  scope "/api/v1", PhoenixGuardian.Api.V1 do
    pipe_through [:api]

    resources "/users", UserController
  end

The verify authorization plug will check the Authorization header for a token, and the LoadResource one will load any resource found there.

Ok, so now protecting your API endpoints is just like your web endpoints:

# web/controllers/api/v1/user_controller.ex
defmodule PhoenixGuardian.Api.V1.UserController do
  use PhoenixGuardian.Web, :controller

  alias PhoenixGuardian.User
  alias PhoenixGuardian.SessionController

  plug Guardian.Plug.EnsureAuthenticated, on_failure: { SessionController, :unauthenticated_api }

  # …
  def index(conn, _params) do
    users = Repo.all(User)
    json(conn, %{ data: users, current_user: Guardian.Plug.current_resource(conn) })
  end
  # …
end

The interaction with API clients is just the same as web session clients. I’ve used a different failure method in my SessionController, but other than this the token is fine.

How do I get my token?

So far, we’ve only used the sign_in function on Guardian.Plug. This is great for web pages but not quite enough for APIs. Lets have a look at how to get a token:

user = Repo.get(User, 1)
{ :ok, jwt, full_claims } = Guardian.encode_and_sign(user, :api)

This will generate a JWT that you can provide to your client, valid for the configured ttl. Once you get to the controller it’s the same API as the browser based authentication.

Your client can hand it in via the “Authorization” header.

Authorization: <jwt>

For bonus points, you can also use it for channel authentication!

Update: 30-08-20 updated for the 0.6.0 API

I’ve been head down with thinking about Guardian and how the far out cases it could be used for will work together. Service2Service, Single sign on, OAuth provider, stuff like that. It occured to me that there is a bunch of really easy to handle things that from the outside might look a little daunting. With that in mind, I wanted to walk through setting up an application for simple, every-day email/password authentication. Almost the simplest auth setup around.

A quick top level overview for the uninitiated. Guardian is an authentication library that uses JSON Web Tokens (JWT) as it’s base unit of authentication. It’s a signed collection of claims that can be used in a session or an Authorization header. They’re great, but this post isn’t about them.

I don’t want to get too bogged down in how to create a User resource. This is going to vary for you, but if you want to see an example of setting up a simple User model with email/username using BCrypt you can checkout the one I use in my example application.

This uses a simple email/encrypted password, where the password is hashed with BCrypt (using Comeonin).

So lets assume that you have created a user and you’re ready to get going. Lets get setup.

Installing Guardian

config.exs

config :joken, config_module: Guardian.JWT

config :guardian, Guardian,
      issuer: "PhoenixGuardian",
      ttl: { 10, :days },
      verify_issuer: true,
      secret_key: "lksdjowiurowieurlkjsdlwwer",
      serializer: PhoenixGuardian.GuardianSerializer

web/routes.ex

defmodule PhoenixGuardian.Router do
  use PhoenixGuardian.Web, :router

  pipeline :browser_session do
    plug Guardian.Plug.VerifySession
    plug Guardian.Plug.LoadResource
  end

  scope "/", PhoenixGuardian do
    pipe_through [:browser, :browser_session] # Use the default browser stack

    get "/login", SessionController, :new, as: :login
    post "/login", SessionController, :create, as: :login
    delete "/logout", SessionController, :delete, as: :logout
    get "/logout", SessionController, :delete, as: :logout

    resources "/users", UserController
  end

We’ve setup a pipeline for authenticating browser requests (i.e. requests from the session). Note that this will not actually kick anyone from the app, that will come later.

You’ll need a serializer. I put mine in lib/phoenix_guardian/guardian_serializer.ex

defmodule PhoenixGuardian.GuardianSerializer do
  @behaviour Guardian.Serializer

  alias PhoenixGuardian.Repo
  alias PhoenixGuardian.User

  def for_token(user = %User{}), do: { :ok, "User:#{user.id}" }
  def for_token(_), do: { :error, "Unknown resource type" }

  def from_token("User:" <> id), do: { :ok, Repo.get(User, String.to_integer(id)) }
  def from_token(thing), do: { :error, "Unknown resource type" }
end

The serializer just fetches your resource, or given a resource, it serializes it into the token.

Logging in

We added the SessionController into the routes. This just provides the login form, and handles the result. It is also where the magic happens. Inside this controller, you’re issued a JWT into your session.

defmodule PhoenixGuardian.SessionController do
  use PhoenixGuardian.Web, :controller

  alias PhoenixGuardian.User

  def new(conn, params) do
    changeset = User.login_changeset(%User{})
    render(conn, PhoenixGuardian.SessionView, "new.html", changeset: changeset)
  end

  def create(conn, params = %{}) do
    user = Repo.one(UserQuery.by_email(params["user"]["email"] || ""))
    if user do
      changeset = User.login_changeset(user, params["user"])
      if changeset.valid? do
        conn
        |> put_flash(:info, "Logged in.")
        |> Guardian.Plug.sign_in(user, :token)
        |> redirect(to: user_path(conn, :index))
      else
        render(conn, "new.html", changeset: changeset)
      end
    else
      changeset = User.login_changeset(%User{}) |> Ecto.Changeset.add_error(:login, "not found")
      render(conn, "new.html", changeset: changeset)
    end
  end

  def delete(conn, _params) do
    Guardian.Plug.sign_out(conn)
    |> put_flash(:info, "Logged out successfully.")
    |> redirect(to: "/")
  end
end

There’s a couple of methods, but most of what’s happening is straight forward.

A user lands on the “new” action and we generate a form. We use the User.login_changeset with the form. It’s a simple changeset from the user.ex model:

def login_changeset(model), do: model |> cast(%{}, ~w(), ~w(email password))

def login_changeset(model, params) do
  model
  |> cast(params, ~w(email password), ~w())
  |> validate_password
end

This will just give us a nice error message and interface for checking the password.

Once the form is posted to the create method, we’ll check the login_changeset and make sure it’s a good email/pass match.

Once there, we do the ‘logging in’ part.

  |> Guardian.Plug.sign_in(user, :token)

This line invokes your serializer, generates your token with an expiry of what you configured (10 days for this example), pushes it into the session and makes it available on the request for further use. The :token option is essentially a label to identify the type of token (used in the :aud field). This can be anything but should be consistent.

Protecting your urls

So, now we have a logged in user, lets protect something.

In the user_controller.ex

defmodule PhoenixGuardian.UserController do
  use PhoenixGuardian.Web, :controller

  alias PhoenixGuardian.User
  alias PhoenixGuardian.SessionController
  alias Guardian.Plug.EnsureAuthenticated

  plug EnsureAuthenticated, %{ on_failure: { SessionController, :new } } when not action in [:new, :create]

  # …

  def edit(conn, params) do
    user = Guardian.Plug.current_resource(conn)
    changeset = User.update_changeset(user)
    render(conn, "edit.html", user: user, changeset: changeset)
  end

  # …

I’ve cut most of it, but you can see in the edit action how we fetch the currently logged in user.

This illustrates a very simple use of Guardian. From here there are a lot of places to go.

• api vs session credentials
• custom ‘claims’ in the JWT
• permissions
• hooks
• mashups with existing frameworks

There’s a lot of places to go. I want to make sure the road to getting in is a simple as possible.

I’m really loving using JWT’s for authentication. They’re a great little self contained set of information that I can use, with or without hitting the db.

One thing that was missing was permissions. Anyone who’s implemented OAuth will be familiar with why these are needed on a per token basis. Imagine you head over to a site to OAuth an app. That app will be authenticating as you, but usually with a customizable list of permissions. One of the tricky parts of this is that once you add OAuth, you have to make sure all your relevant endpoints (including downstream s2s) are aware of those permissions and have some way to get to them. Not a fun X hours/days tracking all that down. Don’t worry. Guardian has your back so you can make your apps permission aware as early as you like.

JWTs need to be encoded so that they fit into the header of an HTTP request so keeping them on the small side is pretty important. That’s why guardian encodes all permissions into a bitsting for you.

Enough! Lets see it.

Config

You’ll need to include your list of known permissions in the config. Don’t worry if you have to add some, Guardian will handle unknown permissions by ignoring them.

config :guardian, Guardian,
       permissions: %{
         default: [:read, :write],
         admin: [:dashboard, :make_payments]
       }

Seems pretty straight forward right? The :default and :admin represent different sets of permissions. You can have as many sets as you like. I’d lean towards more permissions per set, than more sets though.

A word of caution. Guardian encodes permissions into bitstrings. The position of the permission in the list is what determines it’s position in the bits. Couple of things to keep in mind:

• Re-ordering is bad
• Renames are fine
• Removals need to keep their place in the list

Ok, now that we’ve got the caveats out of the way, lets use it.

Sign in

You can encode these puppies right when you sign in.

Guardian.Plug.sign_in(conn, resource, :token, perms: %{ default: [:read], admin: [:dashboard]})

Simple right. The same thing is true when encoding manually.

Guardian.encode_and_sign(resource, :token, perms: %{ default: [:read], admin: [:dashboard]})

But what if I add a permission and I want the admin to have access to all the things? (I hear myself asking myself).

Guardian.encode_and_sign(resource, :token, perms: %{ default: [:read], admin: Guardian.Permissions.max})

By using the Guardian.Permissions.max/0 function, you get it all.

Checking permissions

To check them, you’ll need the claims.

# Using a conn
claims = Guardian.Plug.current_claims(conn)

# In a channel
claims = Guardian.Channel.current_claims(socket)

Lets have a look then.

# Check for the existence of all the permissions you need
Guardian.Permissions.from_claims(claims, :admin)
|> Guardian.Permissions.all?([:dashboard, :reconcile], :admin)

# Check for the existence of any the permissions you need
Guardian.Permissions.from_claims(claims, :admin)
|> Guardian.Permissions.any?([:dashboard, :reconcile], :admin)

There’s also a plug version.

defmodule MyApp.MyController do
  use MyApp.Web, :controller
  alias Guardian.Permissions
  alias Guardian.Plug.EnsurePermissions

  plug EnsurePermissions, on_failure: { MyApp.MyController, :forbidden }, admin: [:dashboard]

end

This will do an all? check on the permissions for any that you specify.

One thing to bear in mind with these permission sets. You shouldn’t feel locked in stone on them. If you make a set and then find that you’d like to have a different set, just deprecate the first one and create a new one. No problem.

Lastly, just in case you want to get right down into it.

Guardian.Permissions.to_value([:read, :write], :default)
|> Guardian.Permissions.to_list(:default)

Updated: 2015-08-30 to support the 0.6.0 API.

For some reason, the first thing I look for when I’m building an application is authentication. For me things are interesting when there’s something going on on my apps, and that usually means letting people login.

I’ve been enjoying Elixir and so far there hasn’t been anything for authentication that suited what I wanted. Using Phoenix is so nice, and make things that are difficult or nearly impossible with other frameworks easy (looking at you Channels).

One of the things that I really like about Elixir/Eralng, is that making all elements of you application live in your application is (mostly) reasonable. Web requests, web-sockets, mail even raw TCP sockets are all on the table. Time for something new in auth.

Guardian is based on JWT. They are the self contained package of information that contains all the information you need for your authentication needs. For those unfamiliar I suggest having a look at the Registered Claim Names. These little packets of goodness can be used in a session, authorization header, passed in body params - they can even be used on raw sockets.

Lets look at what Guardian is not (for the moment).

• It does not have any requirements around your model
• It does not try to implement (or assist you to implement) checking login/emails
• It does not try to do oAuth

Not to say that strategies won’t come sometime in the future, but for the moment I’m not convinced that they’re actually within scope of the library. Guardian strives to provide mechanisms for seamless authentication across different access patterns, devices and S2S communications. How you determine that a user is who they say they are is, at the moment beyond the scope.

So what’s it good for?

Guardian provides a mechanism for verifying previously asserted claims that someone is who they say they are. Do this for browser based, api, channel, socket communications or just because you can. The initial login is trivial, it’s the other parts of the system where things get interesting.

Since Guardian is based on JWT, you can share the tokens with other systems that you trust. The same shared secret will allow another system to verify the token which is great for S2S systems. Your Elixir application can mint the credentials (JWT) and other systems can verify them without a call to your Elixir application, or they can mint credentials and have them used by your Elixir app. Screw language differences.

Ok so lets see it then

I’m going to pull the code from my demo application: PhoenixGuardian.

Configuration

Add Guardian to your mix.deps:

defp deps do
  [
    # ...
    {:guardian, "~>0.6.0"},
    # ...
  ]
end

Guardian relies on Joken for it’s JWTs. Guardian will bring it in, but you’ll need to configure it.

config :joken, config_module: Guardian.JWT

config :guardian, Guardian,
      issuer: "MyApp",
      ttl: { 30, :days },
      verify_issuer: true,
      secret_key: "lksdjowiurowieurlkjsdlwwer",
      serializer: PhoenixGuardian.GuardianSerializer

A couple of things to note.

• Jokens config_module should be set to Guardian.JWT
• verify_issuer Set this to true if you want to only accept tokens generated by yourself (even if another app has your secret)
• Please have different secret_keys per environment!

Guardian.Serializer

You’ll need the serializer so your app can serialize into and out of the token. Don’t worry, this is Elixir, they’re easy.

defmodule PhoenixGuardian.GuardianSerializer do
  @behaviour Guardian.Serializer

  alias PhoenixGuardian.Repo
  alias PhoenixGuardian.User

  def for_token(user = %User{}), do: { :ok, "User:#{user.id}" }
  def for_token(_), do: { :error, "Unknown resource type" }

  def from_token("User:" <> id), do: { :ok, Repo.get(User, String.to_integer(id)) }
  def from_token(_), do: { :error, "Unknown resource type" }
end

Need to support different model types? Just add a pattern match in your serializer!

So, at this point, we’re setup to use Guardian, we just need to decide where and how we’re going to apply it. I’ll show you the pieces.

Plug

Guardian comes with Plug integration. I’m going to focus on Phoenix but any plug will work.

There are three phases to Guardians plug integration.

1. Verifying the token
2. Loading the resource
3. Requireing a verified token

pipeline :browser_session do
  plug Guardian.Plug.VerifySession # looks in the session for the token
  plug Guardian.Plug.LoadResource
end

pipeline :api do
  plug :accepts, ["json"]
  plug Guardian.Plug.VerifyHeader # Looks in the Authorization header for the token
  plug Guardian.Plug.LoadResource
end

These two pipelines will verify the token (if present) and load the resource if there was a verified token found. If the token isn’t there or is invalid, nothing bad happens, the load resource won’t do anything.

When we want to ensure that someone is authenticated we can ensure they have a verified token.

defmodule PhoenixGuardian.UserController do
  use PhoenixGuardian.Web, :controller

  alias PhoenixGuardian.User

  plug Guardian.Plug.EnsureAuthenticated, %{ on_failure: { PhoenixGuardian.SessionController, :new } } when not action in [:new, :create]

  # ....
end

Ok, so there’s some stuff going on there. Lets break it down.

The Guardian.Plug.EnsureAuthenticated checks to make sure there was a valid token found. If it finds one we move on.

If the plug cannot find a verified token for the connection, it calls the on_failure function. This function should be arity 2 and receive a Plug.Conn.t and it’s params. It’s up to this function to handle what should happen when things go south.

We could have put this plug in the pipeline, the only reason I didn’t do that for this controller was because I wanted more control over the actions it fires for, hence the when not action stuff.

Signing In.

Ok so, this is all good and well. We’ve configured it, setup a serializer, and created our pipelines, how to sign in?

def create(conn, %{"user" => user_params}) do
  changeset = User.create_changeset(%User{}, user_params)

  if changeset.valid? do
    user = Repo.insert(changeset)

    conn
    |> put_flash(:info, "User created successfully.")
    |> Guardian.Plug.sign_in(user, :token)
    |> redirect(to: user_path(conn, :index))
  else
    render(conn, "new.html", changeset: changeset)
  end
end

See that tiny line in the middle there. Guardian.Plug.sign_in(user, :csrf). That’s it. Once you do that, your token is generated, pumped into the connection and session and off you go.

The :csrf determines the tokens type (stored in the :aud field). This can be anything you want it to be (e.g. ‘token’, ‘csrf’, ‘api’, ‘oauth’ etc).

Logout

Guardian.Plug.logout(conn)
|> redirect_or_something

Channels

Ok so, I did say you could use this for channels right. Here it is:

some_html.html

<%= if Guardian.Plug.current_token(@conn) do %>
  <meta name='guardian_token' content="<%= Guardian.Plug.current_token(@conn) %>">
<% end %>

some_javascript.js

let socket = new Socket("/ws");
socket.connect();

let guardianToken = jQuery('meta[name="guardian_token"]').attr('content');

let chan = socket.chan("pings", { guardian_token: guardianToken });

phoenix_guardian/user_channel.ex

defmodule PhoenixGuardian.UsersChannel do
  use Phoenix.Channel
  use Guardian.Channel

  def join(_room, %{ claims: claims, resource: resource }, socket), do: { :ok, %{ message: "Joined" }, socket }
  def join(room, _, socket), do: { :error,  :authentication_required }

  def handle_in("ping", _payload, socket) do
    user = Guardian.Channel.current_resource(socket)
    broadcast socket, "pong", %{ message: "pong", from: user.email }
    { :noreply, socket }
  end

  def handle_guardian_auth_failure(reason), do: { :error, %{ error: reason } }
end

When Guardian finds a valid token, it extracts the claims and the resource, and calls join with them in the map. The keys to pattern match on for authenticated joins are claims and resource.

When Guardian cannot verify the token, it will call handle_guardian_auth_failure with the reason it failed.

Well, thats a whirlwind tour of Guardian as it stands today. There’s a lot more to say, but for the first post I think that will do.

Last week I was reading my friends blog Robot Dan and came across his sudoku post.

I’ve never written a sudoku solver before, naturally I thought of writing it in Elixir. I spent the evening playing around trying to come up with something that was at least somewhat idomatic.

My first solution was a very similar implementation to what Dan had on his site. It works ok. I found a harder board that made it take a bit longer. Interestingly I found that the memory usage was flat for easy or hard. I’m guessing that I got the tail recursion correct.

defmodule Sudoku do
  def easy, do: Sudoku.solve(Sudoku.easy_board)

  # Just using 0 rather than nil for display purposes
  def easy_board do
    [
      [8,3,0, 1,0,0, 6,0,5],
      [0,0,0, 0,0,0, 0,8,0],
      [0,0,0, 7,0,0, 9,0,0],

      [0,5,0, 0,1,7, 0,0,0],
      [0,0,3, 0,0,0, 2,0,0],
      [0,0,0, 3,4,0, 0,1,0],

      [0,0,4, 0,0,8, 0,0,0],
      [0,9,0, 0,0,0, 0,0,0],
      [3,0,2, 0,0,6, 0,4,7]
    ]
  end

  def solve(board) do
    case solve(board, 0, 0) do
      { :ok, solved_board } -> print_board(solved_board)
      { :error } -> IO.puts("Board is not valid")
    end
  end

  def solve(board, x, _) when x==9, do: { :ok, board }
  def solve(board, x, y) when y==9, do: solve(board, x + 1, 0)

  def solve(board, x, y) do
    if Enum.at(Enum.at(board, x), y) == 0 do
      solve(board, x, y, possible_values(board, x, y))
    else
      solve(board, x, y + 1)
    end
  end

  def solve(_, _, _, []), do: { :error }

  def solve(board, x, y, [head | tail]) do
    new_row = Enum.at(board, x) |> List.replace_at(y, head)
    new_board = List.replace_at(board, x, new_row)

    case solve(new_board, x, y + 1) do
      { :ok, solved_board } -> { :ok, solved_board }
      { :error } -> solve(board, x, y, tail)
    end
  end

  def possible_values(board, x, y) do
    vals = [values_in_row(board, x), values_in_column(board, y), values_in_cell(board, x, y)]
            |> List.flatten
            |> Enum.uniq

    (1..9) |> Enum.reject(&(Enum.member?(vals, &1)))
  end

  def values_in_row(board, x), do: Enum.at(board, x)
  def values_in_column(board, y), do: Enum.map(board, &(Enum.at(&1, y)))

  def values_in_cell(board, x, y) do
    start_x = div(x, 3) * 3
    start_y = div(y, 3) * 3
    Enum.slice(board, start_x, 3) |> Enum.map(&(Enum.slice(&1, start_y, 3))) |> List.flatten
  end

  def print_board([]), do: nil
  def print_board([row | rest]) do
    IO.inspect(row)
    print_board(rest)
  end
end

I wanted to do something a little more Elixiry though. When the recursive function selects all possible values for a cell, and then recurses, that’s the point that I thought I might be able to shoot out a bunch of processes and do all the calculations in parallel. A branching recursive parallel implementation. Sounded fun!

I implemented it using Elixir Tasks and process dictionaries.

Unfortunately I went wrong somewhere. I ran out of processes, or simply timed out. I even increased the number of processes to 5M without helping. It maxed out in RAM, CPU and times out.

I think I’ll stick with the recursive solution, but I’ve included the other below.

# The only board that works with this one on my machine is the easy.
# The others simply timeout.
defmodule PSudoku do
  def easy, do: PSudoku.solve(PSudoku.easy_board)

  # Just using 0 rather than nil for display purposes
  def easy_board do
    [
      [8,3,0, 1,0,0, 6,0,5],
      [0,0,0, 0,0,0, 0,8,0],
      [0,0,0, 7,0,0, 9,0,0],

      [0,5,0, 0,1,7, 0,0,0],
      [0,0,3, 0,0,0, 2,0,0],
      [0,0,0, 3,4,0, 0,1,0],

      [0,0,4, 0,0,8, 0,0,0],
      [0,9,0, 0,0,0, 0,0,0],
      [3,0,2, 0,0,6, 0,4,7]
    ]
  end

  def solve(board) do
    case solve(board, 0, 0) do
      { :ok, solved_board } -> print_board(solved_board)
      { :error } -> IO.puts("ERRRO")
    end
  end

  def solve(board, x, _) when x==9, do: { :ok, board }
  def solve(board, x, y) when y==9, do: solve(board, x + 1, 0)

  def solve(board, x, y) do
    if Enum.at(Enum.at(board, x), y) == 0 do
      vals = possible_values(board, x, y)
      if length(vals) > 0 do
        result = Enum.map(vals, fn(v) -> Task.async(fn -> solve(board, x, y, v) end) end)
        |> Enum.map(&(Task.await(&1, 30_000)))
        |> Enum.find({ :error }, &match?({ :ok, _ }, &1))
      else
        { :error }
      end
    else
      solve(board, x, y + 1)
    end
  end

  def solve(board, x, y, v) when is_integer(v) do
    new_row = Enum.at(board, x) |> List.replace_at(y, v)
    new_board = List.replace_at(board, x, new_row)
    solve(new_board, x, y + 1)
  end

  def possible_values(board, x, y) do
    vals = [values_in_row(board, x), values_in_column(board, y), values_in_cell(board, x, y)]
            |> List.flatten
            |> Enum.uniq

    (1..9) |> Enum.reject(&(Enum.member?(vals, &1)))
  end

  def values_in_row(board, x), do: Enum.at(board, x)
  def values_in_column(board, y), do: Enum.map(board, &(Enum.at(&1, y)))

  def values_in_cell(board, x, y) do
    start_x = div(x, 3) * 3
    start_y = div(y, 3) * 3
    Enum.slice(board, start_x, 3) |> Enum.map(&(Enum.slice(&1, start_y, 3))) |> List.flatten
  end

  def print_board([]), do: nil
  def print_board([row | rest]) do
    IO.inspect(row)
    print_board(rest)
  end
end