I've got sudoku fever! Actually, no, I don't, I don't really like sudoku at all but I decided to write a solver in erlang. It was pretty trivial. The basic algorithm is as follows:
1) Create a list of every blank square and the possible values that can go into that square
2) Find the square with the least number of possible values
3) Iterate over the list of possible numbers that can be in that square, create a new board with that value in it and recurse on the new board
4) Continue until there are no more possible values (in which case it failed) or the puzzle is solved.
The code is not the prettiest stuff in the world but it appears to solve the problem (specifically the remove_* functions).
Usage looks like:
Eshell V5.5.1 (abort with ^G)
1> {solved, Res} = sudoku:solve([
1> [9, 5, b, b, b, 6, 4, 7, b],
1> [4, b, 8, 7, b, 2, b, b, b],
1> [6, 2, b, 4, b, b, b, 5, b],
1> [5, b, 2, b, 6, b, 3, b, b],
1> [b, b, b, 2, b, 7, b, b, b],
1> [b, b, 4, b, 1, b, 2, b, 8],
1> [b, 7, b, b, b, 9, b, 3, 4],
1> [b, b, b, 1, b, 3, 7, b, 5],
1> [b, 4, 3, 5, b, b, b, 2, 9]]).
...
2> sudoku:print(Res).
9 5 1 8 3 6 4 7 2
4 3 8 7 5 2 9 6 1
6 2 7 4 9 1 8 5 3
5 8 2 9 6 4 3 1 7
3 1 9 2 8 7 5 4 6
7 6 4 3 1 5 2 9 8
8 7 5 6 2 9 1 3 4
2 9 6 1 4 3 7 8 5
1 4 3 5 7 8 6 2 9
ok
Code (can be downloaded
here):
-module(sudoku).
-export([solve/1, print/1]).
solve(Puzzle) when is_list(Puzzle) ->
solve_puzzle(dict_from_list(Puzzle)).
print(Puzzle) ->
lists:foreach(fun(X) ->
lists:foreach(fun(Y) ->
io:format("~w ", [dict:fetch({X, Y}, Puzzle)])
end, lists:seq(0, 8)),
io:format("~n", [])
end, lists:seq(0, 8)).
dict_from_list(List) ->
element(2, lists:foldl(fun(Elm, {X, Dict}) ->
{_, DDict} = lists:foldl(fun(Elem, {Y, NDict}) ->
{Y + 1, dict:store({X, Y}, Elem, NDict)}
end, {0, Dict}, Elm),
{X + 1, DDict}
end, {0, dict:new()}, List)).
solve_puzzle(Puzzle) ->
case generate_open_spots(Puzzle) of
[{{X, Y}, Set} | _] ->
try_value({X, Y}, Set, Puzzle);
[] ->
{solved, Puzzle}
end.
try_value(_, [], Puzzle) ->
print(Puzzle),
io:format("~n", []),
failed;
try_value({X, Y}, [H | R], Puzzle) ->
case solve_puzzle(dict:store({X, Y}, H, Puzzle)) of
{solved, RPuzzle} ->
{solved, RPuzzle};
failed ->
try_value({X, Y}, R, Puzzle)
end.
generate_open_spots(Puzzle) ->
OpenSquareList = dict:fold(fun(Key, b, Acc) ->
[Key | Acc];
(_Key, _Value, Acc) ->
Acc
end, [], Puzzle),
lists:sort(fun({{_X1, _Y1}, E1}, {{_X2, _Y2}, E2}) when length(E1) < length(E2) ->
true;
(_E1, _E2) ->
false
end, generate_open_values(OpenSquareList, Puzzle)).
generate_open_values(List, Puzzle) ->
generate_open_values(List, [], Puzzle).
generate_open_values([], Acc, _Puzzle) ->
Acc;
generate_open_values([{X, Y} | R], Acc, Puzzle) ->
generate_open_values(R, [{{X, Y}, remove_region_vals({X, Y},
remove_x_vals(Y,
remove_y_vals(X, lists:seq(1, 9),
Puzzle),
Puzzle),
Puzzle)} | Acc],
Puzzle).
remove_x_vals(Y, List, Puzzle) ->
lists:foldl(fun(Idx, Acc) ->
case dict:fetch({Idx, Y}, Puzzle) of
b ->
Acc;
E ->
lists:delete(E, Acc)
end
end,
List, lists:seq(0, 8)).
remove_y_vals(X, List, Puzzle) ->
lists:foldl(fun(Idx, Acc) ->
case dict:fetch({X, Idx}, Puzzle) of
b ->
Acc;
E ->
lists:delete(E, Acc)
end
end,
List, lists:seq(0, 8)).
remove_region_vals({X, Y}, List, Puzzle) ->
{RX, RY} = find_region(X, Y),
lists:foldl(fun(IX, AccX) ->
lists:foldl(fun(IY, AccY) ->
case dict:fetch({IX, IY}, Puzzle) of
b ->
AccY;
E ->
lists:delete(E, AccY)
end
end, AccX, lists:seq(RY, RY + 2))
end, List, lists:seq(RX, RX + 2)).
find_region(X, Y) ->
{find_region(X), find_region(Y)}.
find_region(V) when V >= 0, V < 3 ->
0;
find_region(V) when V >= 3, V < 6 ->
3;
find_region(V) when V >= 6, V < 9 ->
6.
