0

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.

4

1 回答 1

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做你描述的。它通过遍历来构建解决方案，当它找到并收集解决方案时Board尝试所有可能的解决方案（来自）以进一步传递它们以继续。因此，它会采用所有可能的方式，如果在某个时候有多个数独，它们都将被添加到并在以下步骤中进行测试。只是调用的包装器。pos()0validValidHeadsvalidHeadsvalidsolvetry_values([], Board)

基本上，方法iterate recursively over 0's是跳过所有非零（最后一个try_values表达式 2）并在零上完成工作（第四个try_values表达式）。

前三个try_values表达式检查解决方案是否存在并且是单一的，并在这种情况下返回它。

于 2013-10-05T01:03:26.563 回答