# Sudoku Solver in Elixir

Hey! Hope everyone is having a great day or night.

My question for today is has anyone worked on the Leetcode problem Sudoku Solver in Elixir? For people unfamiliar with the problem, basically we are provided with an unsolved sudoku grid and we have to come up with an algorithm that solves a Sudoku puzzle by filling the empty cells. A few constraints over here are that:

1. Each of the digits `1-9` must occur exactly once in each row.
2. Each of the digits `1-9` must occur exactly once in each column.
3. Each of the digits `1-9` must occur exactly once in each of the 9 `3x3` sub-boxes of the grid.

Our unsolved board looks something like the following where `.` represents empty cell:

``````[["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
``````

The solved Sudoku board should look like the following:

``````[["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]]
``````

I have tried coming up with a solution, however, it doesnâ€™t work properly which is given below:

``````defmodule SudokuSolver do
def solve_sudoku(board) do
solve(board, 0, 0) |> elem(1)
end

# Get value of board
def get_board_value(board, index), do: Enum.at(board, index)

def solve(board, row, col) do
# Getting values of matrix
outer_arr = get_board_value(board, row)
inner_arr = get_board_value(outer_arr, col)
cond do
# Checking if we reached end of matrix
row == 9 -> {true, board}
# Checking if we reached end of column, then move to next row
col == 9 -> solve(board, row + 1, col)
# If no empty space exists on current col, move to next col
inner_arr != "." -> solve(board, row, col + 1)

true ->
# Reduce over digits
1..9 |> Enum.reduce_while({false, board}, fn(d, {flag, board}) ->

cond do
# Check if the piece can be played on the current spot
isValid(board, row, col, to_string(d)) == true ->

# If yes, update the board and move to next col of current row
updated_board = List.insert_at(board, row, List.insert_at(outer_arr, col, to_string(d)))
{flag, board} = solve(updated_board, row, col + 1)

# Check if the flag is true, then mark it true else continue with existing flag
if flag, do: {:halt, {true, board}}, else: {:cont, {flag, board}}

# If the piece is not valid, move to next digit
true -> {:cont, {flag, board}}
end

end)
end
end

def isValid(board, row, col, digit) do

# Check row and column to see if it already contains the digit
flag =
0..8 |> Enum.reduce_while(true, fn(i, res) ->
row_val = get_board_value(board, row) |> get_board_value(i)
col_val = get_board_value(board, i) |> get_board_value(col)
if row_val == digit and col_val == digit, do: {:halt, false}, else: {:cont, res}
end)

# Check the submatrixes
{row_start, row_end} = {3 * div(row, 3), 3 * div(row, 3) + 3}
{col_start, col_end} = {3 * div(col, 3), 3 * div(col, 3) + 3}

# Loop over the rows and cols and check to see if it already contains the digit
flag2 =
row_start..row_end-1 |> Enum.reduce_while(true, fn(i, res) ->
col_start..col_end-1 |> Enum.reduce_while(res, fn(j, res) ->
board_val = get_board_value(board, i) |> get_board_value(j)
if board_val == digit, do: {:halt, false}, else: {:cont, res}
end)

if res == false, do: {:halt, false}, else: {:cont, res}
end)

flag and flag2
end
end
``````

In this, I first check the border conditions to see if either the `row` or `col` get to the end of the sudoku board and then run their specific conditions. If no empty space exists on current cell, move to next one. After this, we will check if it is possible to place a digit on the board and after placing it, we move to the next cell. Over here, we also check to see if `true` has been called or not which would terminate the `reduce_while`.

This, however, gives me the following wrong output:

``````[["5", "3", "1", "2", "1", "1", "1", "1", "1", ".", ".", "7", ".", ".", ".",
"."],
["5", "3", "1", "2", "1", "1", "1", "1", ".", ".", "7", ".", ".", ".", "."],
["5", "3", "1", "2", "1", "1", "1", ".", ".", "7", ".", ".", ".", "."],
["5", "3", "1", "2", "1", "1", ".", ".", "7", ".", ".", ".", "."],
["5", "3", "1", "2", "1", ".", ".", "7", ".", ".", ".", "."],
["5", "3", "1", "2", ".", ".", "7", ".", ".", ".", "."],
["5", "3", "1", ".", ".", "7", ".", ".", ".", "."],
["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"]]
``````

Would anyone happen to know what seems to be wrong with my solution? Has anyone themselve worked on this and would be willing to share their solution?

Thank you!

PS: I understand this might have a lot of complexity issues, however, for now, I donâ€™t really care about that. I just want the code to work first after which I will try optimizing it.

2 Likes

This is a nice problem to solve.
I donâ€™t have time right now to take a closer look at your code.
Did you try to implement standard solving techniques? (sudoku techniques)

The first 2 should be relatively easy to implement. #3 a little more involved but still straightforward.
After that one could try to implement the more complex ones or just start trying (backtracking).

First thing Iâ€™d do is to think about a suitable data structure.

1 Like

I havenâ€™t dug through the whole algorithm, but this line doesnâ€™t seem right. `List.insert_at` is going to make rows/columns longer, thus the first part of your output `[["5", "3", "1", "2", "1", "1", "1", "1", "1", ".", ".", "7", ".", ".", ".","."],`.

Here is my sudoku solver, havenâ€™t worked on it for a few years though. It tries not to guess (however, you can solve any puzzle by guessing so quickly that this was largely for practice writing elixir)

The other thing I was experimenting with at the time was the use of â€śfunctionalâ€ť approaches. So whereas Peter Norvigâ€™s classic solution tends to â€śrun a function and get a new mutated board backâ€ť, this has one function to choose next move and then the mutation is handled separately. This was novel to me at that point

Have fun!

1 Like

this looks great, will take some time to get it.
I was thinking about this problem earlier today, and did not come up with a solution that could compete (in simplicity and for sure speed) with some solutions that came to mind that utilize mutable data structures. What do you think having already done this?

My solver can solve all the â€śhardâ€ť 17 clue sudoku puzzles in a few millisecs. So there are no known traditional sized puzzles which take a noticeable amount of time to solve.

I think the readme said something like:
On my Mid 2014, 2.5Ghz Macbook Pro, it takes under 600 seconds to solve the 49151 puzzles from minimum_sudoku_17.txt, which is a rate of around 80 per/second

Without checking my own code, I think the solver is single threaded, so you could increase those speeds linearly by partitioning the solving processâ€¦