Erlang sudoku solver - How to find the empty spots and try possible values recursively

Question

I have been busy with a sudoku solver in Erlang yesterday and today. The working functionality I have now is that I can check if a sudoku in the form of a list, e.g.,

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

is valid or not by looking at the constraints (no duplicates in squares, rows, and columns).

This function is called valid(S) which takes a sudoku S and returns true if it is a valid sudoku and false if it is not. The function ignores 0's, which are used to represent empty values. This is an example of the same sudoku with some random empty values:

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

The next step is to find the first 0 in the list, and try a value from 1 to 9 and check if it produces a valid sudoku. If it does we can continue to the next 0 and try values there and see if it is valid or not. Once we cannot go further we go back to the previous 0 and try the next values et cetera until we end up with a solved sudoku.

The code I have so far looks like this (based on someone who got it almost working):

solve(First,Nom,[_|Last]) -> try_values({First,Nom,Last},pos()).

try_values(_,[]) -> {error, "No solution found"};
try_values({First,Nom,Last},[N|Pos]) ->
  case valid(First++[N]++Last) of
    true ->
      case solve({First++[N]},Nom,Last) of
        {ok,_} -> {ok, "Result"};
        {error,_} -> try_values({First,N,Last},Pos)
      end;
    false -> try_values({First,N,Last},Pos)
  end.

pos() is a list consisting of the values from 1 to 9. The idea is that we enter an empty list for First and a Sudoku list for [_|Last] in which we look for a 0 (Nom?). Then we try a value and if the list that results is valid according to our function we continue till we fail the position or have a result. When we fail we return a new try_values with remaining (Pos) values of our possibitilies.

Naturally, this does not work and returns:

5> sudoku:solve([],0,S).
** exception error: bad argument
     in operator  ++/2
        called as {[6]}
                  ++
                  [1,1,8,2,3,4,0,5,5,4,9,0,7,6,3,2,8,3,2,8,5,4,9,1,6,7,1,3,2|...]
     in call from sudoku:try_values/2 (sudoku.erl, line 140)
     in call from sudoku:try_values/2 (sudoku.erl, line 142)

With my inexperience I cannot grasp what I need to do to make the code logical and working. I would really appreciate it if someone with more experience could give me some pointers.

Answer 1

try_values([], []) -> error("No solution found");
try_values([Solution], []) -> Solution;
try_values(_, []) -> error("Bad sudoku: multiple solutions");
try_values(Heads, [0|Tail]) ->
    NewHeads = case Heads of
                   [] -> [[P] || P <- pos()];
                   _ -> [Head++[P] || P <- pos(), Head <- Heads]
              end,
    ValidHeads = [Head || Head <- NewHeads, valid(Head++Tail)],
    try_values(ValidHeads, Tail);
try_values([], [H|Tail]) -> try_values([[H]], Tail);
try_values(Heads, [H|Tail]) -> try_values([Head++[H] || Head <- Heads], Tail).

solve(Board) ->
    case valid(Board) of
        true -> try_values([], Board);
        false -> error("No solution found")
    end.

try_values does what you described. It builds solution by going through Board, trying all possible solutions (from pos()) when it finds 0 and collecting valid solutions in ValidHeads to pass them further to continue. Thus, it goes all possible ways, if at some point there are multiple valid sudoku they all will be added to Heads and will be tested on validity on following steps. solve is just a wrapper to call try_values([], Board).

Basically, the way to iterate recursively over 0's is to skip all non-zeros (2 last try_values expression) and do the job on zeros (fourth try_values expression).

First three try_values expressions check if solution is exist and single and return it in that case.