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:
- Each of the digits
1-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the 93x3sub-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.
