Erlang数独解算器-如何找到空白点并递归尝试可能的值

Question

我昨天和今天都在二郎忙着数独游戏。我现在的工作功能是，我可以检查列表形式的数独，例如。，

[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].

通过查看约束（正方形、行和列中没有重复项），可以确定是否有效。

这个函数被称为valid（S），它接受一个数独，如果它是有效的数独，则返回true，如果不是，则返回false。该函数忽略用于表示空值的0。这是同一个数独游戏的一个例子，其中有一些随机的空值：

[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].

下一步是找到列表中的第一个0，并尝试从1到9的值并检查它是否产生有效的数独。如果是这样，我们可以继续到下一个0并尝试那里的值，看看它是否有效。一旦我们不能更进一步，我们就回到前一个0并尝试下一个值等，直到我们最终解决了一个数独。

到目前为止，我的代码是这样的（基于一个几乎可以正常工作的人）：

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（）是一个由从1到9的值组成的列表。这个想法是我们为First输入一个空列表，为[_|Last]输入一个数独列表，在其中我们寻找0（Nom？）。然后我们尝试一个值，如果结果的列表根据我们的函数是有效的，我们将继续直到我们失败的位置或有结果。当我们失败时，我们返回一个新的try_values，其中包含我们可能的剩余（Pos）值。

当然，这不起作用，而且会带来回报：

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)

由于我缺乏经验，我无法掌握我需要做什么才能使代码合乎逻辑并工作。如果有经验的人能给我一些建议，我将不胜感激。

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执行您所描述的操作。它通过遍历Board构建解决方案，在找到0时尝试所有可能的解决方案（来自pos（））并在ValidHead中收集有效解决方案以进一步传递它们以继续。因此，它采用了所有可能的方式，如果在某个时候有多个有效sudoku，它们都将被添加到头中，并将在以下步骤中对有效ity进行测试。解决方案只是调用try_values（[]， Board）的包装器。

基本上，在0上递归迭代的方法是跳过所有非零（最后两个try_值表达式）并在零上执行工作（第四个try_值表达式）。

前三个try_值表达式检查解决方案是否存在，并在这种情况下返回它。