在 Erlang 中使用并发回溯算法的数独求解器
Sudoku solver using a concurrent backtracking algorithm in Erlang
我的作业是使用并发在 Erlang 中创建一个数独求解器。我最初的想法是使用回溯算法，它会在做出选择时产生新的线程。
然而，在对项目投入一些时间和思考之后，我开始认为我想要解决这个问题的方法有点太复杂了。过去有没有人做过类似的事情？你会推荐一些不同的算法来更好地处理 Erlang 和并发吗？
如果安装 wx，只需 运行 sudoku:go()。 https://github.com/erlang/otp/blob/86d1fb0865193cce4e308baa6472885a81033f10/lib/wx/examples/sudoku/sudoku.erl
BackTracking 算法不适合使用并发。当然，始终可以并行生成多个以不同初始条件（要求解的第一个或两个第一个单元格的所有可能值）开始的进程。但我不认为这是一个真正的并发应用程序。
更合适的算法是约束的传播。这个想法是为每个单元格创建一个进程，每个单元格知道 20 "connected cells" 个进程（同一列中有 8 个，同一行中有 8 个，同一方格中还有 4 个）。一个单元格有一个状态，其中包含 - 至少 - 它可以采用的所有可能值。如果一个单元只剩下一个可能的值，在初始化之后或在约束传播期间，它会向所有连接的单元发送一条消息{remove,Value}，通知它们从列表中删除该值。
这是一个真正的并发进程，但它有（至少）两个问题：
- 知道何时找到解决方案或何时传播被卡住；
- 只有最简单的谜题才会被这个算法一次解决。
还有一些其他规则可用于解决更复杂的谜题。例如寻找只有一种可能性的数字，寻找对...但是这些规则并不是很容易并行实现，而且我不知道解决任何难题所需的规则集。
注意 在一般情况下，规则集不存在，因为一个谜题可能有多个解决方案，尽管我们在报纸上可以找到的谜题并非如此。
我的想法是用一个搜索算法来完成约束传播算法。一个新的进程，控制器，负责：
- 初始化拼图
- select 最有希望的试验
- 要求对细胞过程进行试验，
- 控制传播过程的结束，
- 检查是否是
- 一个解决方案 -> 打印出来
- 死胡同 -> 要求回到之前的状态，从列表中删除初始试验编号，然后 select 下一个最有希望的试验
- 要求存储当前结果状态并继续下一次试验
所以单元格必须用一个堆栈来完成它们的状态，在堆栈中它们可以压入和弹出它们当前的可能值列表。
最有希望的试验可以是这样 selected：找到剩余可能值较少的单元格，然后取第一个。
下一个问题是同步一切。第一个 "simple" 解决方案是使用超时。但一如既往，超时很难定义，而且最终效率很低。我会仅出于调试目的保留超时，因此具有相当大的价值，因为存在一些风险，即它在第一次尝试时不起作用 :o).
超时的替代方法是使用计数器。每次控制器发送需要同步的消息时，它都会增加其计数器。每当一个单元完成对需要同步的消息的处理时，它就会向控制器发送 returns 一条 {ack_synchro,N} 消息，控制器又将 N 减去其计数器。这样做，在约束传播期间，当一个单元格只剩下一个可能的值时，它可以在将 {remove,Value} 发送到其连接的单元格之前向控制器发送一个 {ack_synchro,-20}，因此控制器 "knows" 还要再等20条消息。有了这个原理，就可以同步push、pop、{try,Value}、{remove,Value}条消息的activity个cell。
我猜它遗漏了很多细节，我不确定它会比命令式回溯更快，但它应该以合理的编码成本工作，并且是并发的。
编辑
我编写了这个提案，它只用了 2 个测试用例，一个简单的谜题，一个复杂的，它运行良好。这是代码：
主模块（实际上运行在shell进程中）解谜使用命令：sudo:start(file,Filename)或sudo:start(table,InitialList):
-module (sudo).
-export ([start/2]).
start(file,File) ->
{ok,[Table]} = file:consult(File),
start(table,Table);
start(table,Table) ->
init_cells(),
solve(Table),
print_result(),
stop().
stop() ->
lists:foreach(fun(X) -> cell:stop(X) end ,cells()).
cells() ->
[a1,a2,a3,a4,a5,a6,a7,a8,a9,
b1,b2,b3,b4,b5,b6,b7,b8,b9,
c1,c2,c3,c4,c5,c6,c7,c8,c9,
d1,d2,d3,d4,d5,d6,d7,d8,d9,
e1,e2,e3,e4,e5,e6,e7,e8,e9,
f1,f2,f3,f4,f5,f6,f7,f8,f9,
g1,g2,g3,g4,g5,g6,g7,g8,g9,
h1,h2,h3,h4,h5,h6,h7,h8,h9,
i1,i2,i3,i4,i5,i6,i7,i8,i9].
init_cells() ->
lists:foreach(fun(X) -> cell:start_link(X) end ,cells()),
Zip = lists:zip(cells(),lists:seq(0,80)),
lists:foreach(fun({N,P}) -> cell:init(N,neighbors(P,Zip)) end, Zip),
wait(81).
neighbors(P,Zip) ->
Line = fun(X) -> X div 9 end,
Col = fun(X) -> X rem 9 end,
Square = fun(X) -> {Line(X) div 3, Col(X) div 3} end,
Linked = fun(X) -> (X =/= P) andalso
( (Line(X) == Line(P)) orelse
(Col(X) == Col(P)) orelse
(Square(X) == Square(P))) end,
[Name || {Name,Pos} <- Zip, Linked(Pos)].
solve(Table) ->
Zip = lists:zip(cells(),Table),
test(Zip),
do_solve(is_solved()).
do_solve({true,_,_,_}) ->
done;
do_solve({false,Name,Value,_}) ->
push(),
test(Name,Value),
do_solve(is_solved());
do_solve(error) ->
pop(),
{false,Name,Value,_} = is_solved(),
remove(Name,Value),
do_solve(is_solved()).
print_result() ->
R = get_cells(),
F = fun({_,[I]},Acc) ->
case Acc of
_ when (Acc rem 27) == 0 -> io:format("~n~n ~p",[I]);
_ when (Acc rem 9) == 0 -> io:format("~n ~p",[I]);
_ when (Acc rem 3) == 0 -> io:format(" ~p",[I]);
_ -> io:format(" ~p",[I])
end,
Acc+1
end,
lists:foldl(F,0,R),
io:format("~n").
test(List) ->
F = fun({_,0},Acc) ->
Acc;
({Name,Value},Acc) ->
cell:test(Name,Value),
Acc+1
end,
NbMessages = lists:foldl(F,0,List),
wait(NbMessages).
test(_,0) -> ok;
test(Name,Value) ->
cell:test(Name,Value),
wait(1).
remove(Name,Value) ->
cell:remove(Name,Value),
wait(1).
push() ->
lists:foreach(fun(X) -> cell:push(X) end, cells()),
wait(81).
pop() ->
lists:foreach(fun(X) -> cell:pop(X) end, cells()),
wait(81).
wait(0) ->
done;
wait(NbMessages) ->
receive
{done,N} -> wait(NbMessages-N);
{add,N} -> wait(NbMessages+N)
after 2000 ->
error
end.
get_cells() ->
F = fun(X) -> cell:get_val(X), receive {possible,M} -> M end, {X,M} end,
[F(X) || X <- cells()].
is_solved() ->
State = get_cells(),
F = fun({_,[]},_) -> error;
(_,error) -> error;
({Name,List},Acc = {_,_CurName,_CurVal,Length}) ->
NL = length(List),
case (NL > 1) andalso( NL < Length) of
true -> {false,Name,hd(List),NL};
false -> Acc
end
end,
lists:foldl(F,{true,none,0,10},State).
Cell 服务器及其接口
-module (cell).
-export ([start_link/1,init/2,push/1,pop/1,test/2,remove/2,stop/1,get_val/1]).
% Interfaces
start_link(Name) ->
Pid = spawn_link(fun() -> init() end),
register(Name,Pid).
init(Name,List) ->
Name ! {init,self(),List}.
push(Name) ->
Name ! push.
pop(Name) ->
Name ! pop.
test(Name,Value) ->
Name ! {test,Value}.
remove(Name,Value) ->
Name ! {remove,Value}.
get_val(Name) ->
Name ! get.
stop(Name) ->
Name ! stop.
% private
init() ->
loop(none,[],[],[]).
loop(Report,Possible,Stack,Neighbors) ->
receive
{init,R,List} ->
R ! {done,1},
loop(R,lists:seq(1,9),[],List);
push ->
Report ! {done,1},
loop(Report,Possible,[Possible|Stack],Neighbors);
pop ->
Report ! {done,1},
loop(Report,hd(Stack),tl(Stack),Neighbors);
{test,Value} ->
NewP = test(Report,Possible,Neighbors,Value),
loop(Report,NewP,Stack,Neighbors);
{remove,Value} ->
NewP = remove(Report,Possible,Neighbors,Value),
loop(Report,NewP,Stack,Neighbors);
get ->
Report ! {possible,Possible},
loop(Report,Possible,Stack,Neighbors);
stop ->
ok
end.
test(Report,Possible,Neighbors,Value) ->
true = lists:member(Value,Possible),
Report ! {add,20},
lists:foreach(fun(X) -> remove(X,Value) end, Neighbors),
Report ! {done,1},
[Value].
remove(Report,Possible,Neighbors,Value) ->
case Possible of
[Value,B] ->
remove(Report,B,Neighbors);
[A,Value] ->
remove(Report,A,Neighbors);
_ ->
Report ! {done,1}
end,
lists:delete(Value,Possible).
remove(Report,Value,Neighbors) ->
Report ! {add,20},
lists:foreach(fun(X) -> remove(X,Value) end, Neighbors),
Report ! {done,1}.
一个测试文件：
[
0,0,0,4,0,6,9,0,0,
0,0,0,0,0,0,1,0,0,
0,0,0,3,0,0,0,7,2,
0,0,5,6,4,0,0,0,0,
0,2,3,0,8,0,0,0,1,
0,8,0,0,0,2,4,0,5,
0,7,8,0,0,0,5,0,0,
6,0,1,0,0,7,2,0,0,
0,0,2,0,0,9,0,0,0
].
在行动：
1> c(sudo).
{ok,sudo}
2> c(cell).
{ok,cell}
3> timer:tc(sudo,start,[file,"test_hard.txt"]).
1 3 7 4 2 6 9 5 8
2 6 9 7 5 8 1 4 3
8 5 4 3 9 1 6 7 2
7 1 5 6 4 3 8 2 9
4 2 3 9 8 5 7 6 1
9 8 6 1 7 2 4 3 5
3 7 8 2 1 4 5 9 6
6 9 1 5 3 7 2 8 4
5 4 2 8 6 9 3 1 7
{16000,ok}
4>
代码中没有注释，但它完全符合我在答案第一部分中提出的建议。
我的作业是使用并发在 Erlang 中创建一个数独求解器。我最初的想法是使用回溯算法，它会在做出选择时产生新的线程。
然而，在对项目投入一些时间和思考之后，我开始认为我想要解决这个问题的方法有点太复杂了。过去有没有人做过类似的事情？你会推荐一些不同的算法来更好地处理 Erlang 和并发吗？
如果安装 wx，只需 运行 sudoku:go()。 https://github.com/erlang/otp/blob/86d1fb0865193cce4e308baa6472885a81033f10/lib/wx/examples/sudoku/sudoku.erl
BackTracking 算法不适合使用并发。当然，始终可以并行生成多个以不同初始条件（要求解的第一个或两个第一个单元格的所有可能值）开始的进程。但我不认为这是一个真正的并发应用程序。
更合适的算法是约束的传播。这个想法是为每个单元格创建一个进程，每个单元格知道 20 "connected cells" 个进程（同一列中有 8 个，同一行中有 8 个，同一方格中还有 4 个）。一个单元格有一个状态，其中包含 - 至少 - 它可以采用的所有可能值。如果一个单元只剩下一个可能的值，在初始化之后或在约束传播期间，它会向所有连接的单元发送一条消息{remove,Value}，通知它们从列表中删除该值。
这是一个真正的并发进程，但它有（至少）两个问题： - 知道何时找到解决方案或何时传播被卡住； - 只有最简单的谜题才会被这个算法一次解决。
还有一些其他规则可用于解决更复杂的谜题。例如寻找只有一种可能性的数字，寻找对...但是这些规则并不是很容易并行实现，而且我不知道解决任何难题所需的规则集。
注意 在一般情况下，规则集不存在，因为一个谜题可能有多个解决方案，尽管我们在报纸上可以找到的谜题并非如此。
我的想法是用一个搜索算法来完成约束传播算法。一个新的进程，控制器，负责： - 初始化拼图 - select 最有希望的试验 - 要求对细胞过程进行试验， - 控制传播过程的结束， - 检查是否是 - 一个解决方案 -> 打印出来 - 死胡同 -> 要求回到之前的状态，从列表中删除初始试验编号，然后 select 下一个最有希望的试验 - 要求存储当前结果状态并继续下一次试验
所以单元格必须用一个堆栈来完成它们的状态，在堆栈中它们可以压入和弹出它们当前的可能值列表。
最有希望的试验可以是这样 selected：找到剩余可能值较少的单元格，然后取第一个。
下一个问题是同步一切。第一个 "simple" 解决方案是使用超时。但一如既往，超时很难定义，而且最终效率很低。我会仅出于调试目的保留超时，因此具有相当大的价值，因为存在一些风险，即它在第一次尝试时不起作用 :o).
超时的替代方法是使用计数器。每次控制器发送需要同步的消息时，它都会增加其计数器。每当一个单元完成对需要同步的消息的处理时，它就会向控制器发送 returns 一条 {ack_synchro,N} 消息，控制器又将 N 减去其计数器。这样做，在约束传播期间，当一个单元格只剩下一个可能的值时，它可以在将 {remove,Value} 发送到其连接的单元格之前向控制器发送一个 {ack_synchro,-20}，因此控制器 "knows" 还要再等20条消息。有了这个原理，就可以同步push、pop、{try,Value}、{remove,Value}条消息的activity个cell。
我猜它遗漏了很多细节，我不确定它会比命令式回溯更快，但它应该以合理的编码成本工作，并且是并发的。
编辑
我编写了这个提案，它只用了 2 个测试用例，一个简单的谜题，一个复杂的，它运行良好。这是代码：
主模块（实际上运行在shell进程中）解谜使用命令：sudo:start(file,Filename)或sudo:start(table,InitialList):
-module (sudo).
-export ([start/2]).
start(file,File) ->
{ok,[Table]} = file:consult(File),
start(table,Table);
start(table,Table) ->
init_cells(),
solve(Table),
print_result(),
stop().
stop() ->
lists:foreach(fun(X) -> cell:stop(X) end ,cells()).
cells() ->
[a1,a2,a3,a4,a5,a6,a7,a8,a9,
b1,b2,b3,b4,b5,b6,b7,b8,b9,
c1,c2,c3,c4,c5,c6,c7,c8,c9,
d1,d2,d3,d4,d5,d6,d7,d8,d9,
e1,e2,e3,e4,e5,e6,e7,e8,e9,
f1,f2,f3,f4,f5,f6,f7,f8,f9,
g1,g2,g3,g4,g5,g6,g7,g8,g9,
h1,h2,h3,h4,h5,h6,h7,h8,h9,
i1,i2,i3,i4,i5,i6,i7,i8,i9].
init_cells() ->
lists:foreach(fun(X) -> cell:start_link(X) end ,cells()),
Zip = lists:zip(cells(),lists:seq(0,80)),
lists:foreach(fun({N,P}) -> cell:init(N,neighbors(P,Zip)) end, Zip),
wait(81).
neighbors(P,Zip) ->
Line = fun(X) -> X div 9 end,
Col = fun(X) -> X rem 9 end,
Square = fun(X) -> {Line(X) div 3, Col(X) div 3} end,
Linked = fun(X) -> (X =/= P) andalso
( (Line(X) == Line(P)) orelse
(Col(X) == Col(P)) orelse
(Square(X) == Square(P))) end,
[Name || {Name,Pos} <- Zip, Linked(Pos)].
solve(Table) ->
Zip = lists:zip(cells(),Table),
test(Zip),
do_solve(is_solved()).
do_solve({true,_,_,_}) ->
done;
do_solve({false,Name,Value,_}) ->
push(),
test(Name,Value),
do_solve(is_solved());
do_solve(error) ->
pop(),
{false,Name,Value,_} = is_solved(),
remove(Name,Value),
do_solve(is_solved()).
print_result() ->
R = get_cells(),
F = fun({_,[I]},Acc) ->
case Acc of
_ when (Acc rem 27) == 0 -> io:format("~n~n ~p",[I]);
_ when (Acc rem 9) == 0 -> io:format("~n ~p",[I]);
_ when (Acc rem 3) == 0 -> io:format(" ~p",[I]);
_ -> io:format(" ~p",[I])
end,
Acc+1
end,
lists:foldl(F,0,R),
io:format("~n").
test(List) ->
F = fun({_,0},Acc) ->
Acc;
({Name,Value},Acc) ->
cell:test(Name,Value),
Acc+1
end,
NbMessages = lists:foldl(F,0,List),
wait(NbMessages).
test(_,0) -> ok;
test(Name,Value) ->
cell:test(Name,Value),
wait(1).
remove(Name,Value) ->
cell:remove(Name,Value),
wait(1).
push() ->
lists:foreach(fun(X) -> cell:push(X) end, cells()),
wait(81).
pop() ->
lists:foreach(fun(X) -> cell:pop(X) end, cells()),
wait(81).
wait(0) ->
done;
wait(NbMessages) ->
receive
{done,N} -> wait(NbMessages-N);
{add,N} -> wait(NbMessages+N)
after 2000 ->
error
end.
get_cells() ->
F = fun(X) -> cell:get_val(X), receive {possible,M} -> M end, {X,M} end,
[F(X) || X <- cells()].
is_solved() ->
State = get_cells(),
F = fun({_,[]},_) -> error;
(_,error) -> error;
({Name,List},Acc = {_,_CurName,_CurVal,Length}) ->
NL = length(List),
case (NL > 1) andalso( NL < Length) of
true -> {false,Name,hd(List),NL};
false -> Acc
end
end,
lists:foldl(F,{true,none,0,10},State).
Cell 服务器及其接口
-module (cell).
-export ([start_link/1,init/2,push/1,pop/1,test/2,remove/2,stop/1,get_val/1]).
% Interfaces
start_link(Name) ->
Pid = spawn_link(fun() -> init() end),
register(Name,Pid).
init(Name,List) ->
Name ! {init,self(),List}.
push(Name) ->
Name ! push.
pop(Name) ->
Name ! pop.
test(Name,Value) ->
Name ! {test,Value}.
remove(Name,Value) ->
Name ! {remove,Value}.
get_val(Name) ->
Name ! get.
stop(Name) ->
Name ! stop.
% private
init() ->
loop(none,[],[],[]).
loop(Report,Possible,Stack,Neighbors) ->
receive
{init,R,List} ->
R ! {done,1},
loop(R,lists:seq(1,9),[],List);
push ->
Report ! {done,1},
loop(Report,Possible,[Possible|Stack],Neighbors);
pop ->
Report ! {done,1},
loop(Report,hd(Stack),tl(Stack),Neighbors);
{test,Value} ->
NewP = test(Report,Possible,Neighbors,Value),
loop(Report,NewP,Stack,Neighbors);
{remove,Value} ->
NewP = remove(Report,Possible,Neighbors,Value),
loop(Report,NewP,Stack,Neighbors);
get ->
Report ! {possible,Possible},
loop(Report,Possible,Stack,Neighbors);
stop ->
ok
end.
test(Report,Possible,Neighbors,Value) ->
true = lists:member(Value,Possible),
Report ! {add,20},
lists:foreach(fun(X) -> remove(X,Value) end, Neighbors),
Report ! {done,1},
[Value].
remove(Report,Possible,Neighbors,Value) ->
case Possible of
[Value,B] ->
remove(Report,B,Neighbors);
[A,Value] ->
remove(Report,A,Neighbors);
_ ->
Report ! {done,1}
end,
lists:delete(Value,Possible).
remove(Report,Value,Neighbors) ->
Report ! {add,20},
lists:foreach(fun(X) -> remove(X,Value) end, Neighbors),
Report ! {done,1}.
一个测试文件：
[
0,0,0,4,0,6,9,0,0,
0,0,0,0,0,0,1,0,0,
0,0,0,3,0,0,0,7,2,
0,0,5,6,4,0,0,0,0,
0,2,3,0,8,0,0,0,1,
0,8,0,0,0,2,4,0,5,
0,7,8,0,0,0,5,0,0,
6,0,1,0,0,7,2,0,0,
0,0,2,0,0,9,0,0,0
].
在行动：
1> c(sudo).
{ok,sudo}
2> c(cell).
{ok,cell}
3> timer:tc(sudo,start,[file,"test_hard.txt"]).
1 3 7 4 2 6 9 5 8
2 6 9 7 5 8 1 4 3
8 5 4 3 9 1 6 7 2
7 1 5 6 4 3 8 2 9
4 2 3 9 8 5 7 6 1
9 8 6 1 7 2 4 3 5
3 7 8 2 1 4 5 9 6
6 9 1 5 3 7 2 8 4
5 4 2 8 6 9 3 1 7
{16000,ok}
4>
代码中没有注释，但它完全符合我在答案第一部分中提出的建议。