Thanks to Andre for his talk on Friday; I spent Saturday writing a Sudoku
solver in Erlang. You can suck it down using bzr from
http://repo.spacepants.org/sudoku/sudoku.dev (and note it's a bzr repo, so
you can't browse the source at that url).
I'd like some feedback on my code, so I've attached it here. Both seasoned
Erlang professionals and green newbs are welcome to comment and ask
questions. (I'm also taking the opportunity to use the [RFR] tag in the
subject as a Request for Review ;-)
(I'm more interested in coding style, or suggestions on ways to make things
more concise, rather than comments on algorithm or telling me that it
doesn't actually solve anything harder than an "easy" sudoku, though you're
welcome to pass judgement on that, too.)
Particular things that I'm sure I'm doing wrong is excessive use of
anonymous functions (Funs) but apparently I can't use a real function as the
argument to, say, lists:map? Does Erlang support currying or is this hacked
through the use of Funs? Also I'm sure I'm using 'case' too much, and
should be using guards or pattern matches, but everything I tried ended up
causing the compiler to complain ;-)
-module(sudoku).
%-export([solve/1]).
-compile(export_all).
%solve(Grid) ->
% Daily Sudoku 28/6/2005 (medium)
-define(test_grid, [[x,x,3,x,x,x,x,1,x],
[9,x,1,x,3,x,8,x,7],
[x,x,x,9,5,x,x,3,4],
[1,5,7,x,x,x,x,x,x],
[x,x,x,x,7,x,x,x,x],
[x,x,x,x,x,x,7,8,6],
[3,9,x,x,8,6,x,x,x],
[6,x,5,x,4,x,1,x,8],
[x,1,x,x,x,x,2,x,x]]).
%%%
-record(cell, {x, y, block, possibles}).
calc_possibles(V) when V == x ->
lists:seq(1, 9);
calc_possibles(V) ->
[V].
test_calc_possibles() ->
[1,2,3,4,5,6,7,8,9] = calc_possibles(x),
[1] = calc_possibles(1),
ok.
calc_block(X, Y) ->
(X-1) div 3 + ((Y-1) div 3) * 3 + 1.
test_calc_block() ->
1 = calc_block(1, 1),
1 = calc_block(2, 1),
1 = calc_block(3, 1),
2 = calc_block(4, 1),
5 = calc_block(5, 5),
9 = calc_block(9, 9),
ok.
compile_cell(X, Y, V) ->
Block = calc_block(X, Y),
Possibles = calc_possibles(V),
#cell{x=X, y=Y, block=Block, possibles=Possibles}.
test_compile_cell() ->
#cell{x=1, y=1, block=1, possibles=[1]} = compile_cell(1, 1, 1),
#cell{x=1, y=1, block=1, possibles=[1,2,3,4,5,6,7,8,9]} =
compile_cell(1, 1, x),
ok.
compile_row([], _) ->
[];
compile_row(Row, Y) ->
EnumeratedRow = lists:zip(lists:seq(1, length(Row)), Row),
lists:map(fun({X, V}) -> compile_cell(X, Y, V) end, EnumeratedRow).
test_compile_row() ->
[] = compile_row([], 0),
[{cell, 1, 1, 1, [1]}] = compile_row([1], 1),
[{cell, 1, 1, 1, [1]}, {cell, 2, 1, 1, [2]}] = compile_row([1, 2], 1),
[{cell, 1, 4, 4, [1,2,3,4,5,6,7,8,9]}] = compile_row([x], 4),
ok.
compile_sudoku([]) ->
[];
compile_sudoku(Grid) ->
EnumeratedGrid = lists:zip(lists:seq(1, length(Grid)), Grid),
lists:flatmap(fun({Y, V}) -> compile_row(V, Y) end, EnumeratedGrid).
test_compile_sudoku() ->
[] = compile_sudoku([]),
[{cell,1,1,1,[1]}] = compile_sudoku([[1]]),
ok.
% pull out the definitely solved cells from the neighbour list
definites(Cells) ->
lists:filter(fun(C) -> length(C#cell.possibles) == 1 end,
Cells).
test_definites() ->
[{cell,1,1,1,[1]}] = definites([{cell,1,2,1,[1,2]},{cell,1,1,1,[1]}]),
ok.
% not defined in lists module!
keyfilter(Key, N, List) ->
lists:filter(fun(T) -> Key == element(N, T) end, List).
test_keyfilter() ->
[{1,1}] = keyfilter(1, 1, [{2,2},{2,1},{1,1}]),
ok.
% find all affecting neighbours and recalculate this cells' possibles
% this one does all the grunt work of solving the sudoku, add
% new operations on the list of possibles here
collapse_possibles(Cell, Sudoku) ->
% neighbours in the same column that are solved
Cols = lists:flatmap(fun(C) -> C#cell.possibles end,
definites(keyfilter(Cell#cell.x, 2, Sudoku))),
%io:format("Cols: ~p~n", [Cols]),
Rows = lists:flatmap(fun(C) -> C#cell.possibles end,
definites(keyfilter(Cell#cell.y, 3, Sudoku))),
%io:format("Rows: ~p~n", [Rows]),
Blocks = lists:flatmap(fun(C) -> C#cell.possibles end,
definites(keyfilter(Cell#cell.block, 4, Sudoku))),
%io:format("Blocks: ~p~n", [Blocks]),
((Cell#cell.possibles -- Cols) -- Rows) -- Blocks.
test_collapse_possibles() ->
Sudoku = compile_sudoku([[x,x,3,x,x,x,x,1,x],
[9,x,1,x,3,x,8,x,7],
[x,x,x,9,5,x,x,3,4],
[1,5,7,x,x,x,x,x,x],
[x,x,x,x,7,x,x,x,x],
[x,x,x,x,x,x,7,8,6],
[3,9,x,x,8,6,x,x,x],
[6,x,5,x,4,x,1,x,8],
[x,1,x,x,x,x,2,x,x]]),
Cell = lists:nth(1, Sudoku),
P = collapse_possibles(Cell, Sudoku),
%io:format("Poss: ~p~n", [P]),
P = [2,4,5,7,8],
ok.
% look at the neighbours of Cell and work out if Cell can only have one
% value from it's list of possibles
% e.g. if Cell is the only unsolved cell in a row that has a particular
% value, then Cell must be that value
deduce_possibles(Cell, Sudoku) ->
Unsolveds = lists:filter(fun(C) ->
((C#cell.x == Cell#cell.x) or
(C#cell.y == Cell#cell.y) or
(C#cell.block == Cell#cell.block)) and
(length(C#cell.possibles) > 1) and
(C /= Cell)
end, Sudoku),
%io:format("Unsolveds: ~p~n", [Unsolveds]),
% remove all possibles that other cells can also be
Shareds = lists:flatmap(fun(C) ->
C#cell.possibles
end, Unsolveds),
%io:format("Shareds: ~p~n", [Shareds]),
Possibles = Cell#cell.possibles -- Shareds,
%io:format("Possibles: ~p~n", [Possibles]),
Possibles.
test_deduce_possibles() ->
Sudoku = [{cell,9,1,3,[2,9]},
{cell,9,2,3,[7]},
{cell,9,3,3,[4]},
{cell,9,4,6,[2,9]},
{cell,9,5,6,[1,2,9]},
{cell,9,6,6,[6]},
{cell,9,7,9,[5]},
{cell,9,8,9,[8]},
{cell,9,9,9,[3]}],
Cell = {cell,9,5,6,[1,2,9]},
[1] = deduce_possibles(Cell, Sudoku),
ok.
do_solve(Solveds, []) -> Solveds;
do_solve(Solveds, Unsolveds) ->
{Changed, Unchanged} = iter_unsolved(Unsolveds, Solveds ++ Unsolveds),
%io:format("Changed: ~p~n", [Changed]),
case length(Changed) == 0 of
true -> Solveds ++ Unsolveds;
false ->
{NewSolveds, NewUnsolveds} = lists:partition(fun(C) ->
length(C#cell.possibles) == 1
end, Changed),
%io:format("NewSolveds: ~p~n", [NewSolveds]),
do_solve(Solveds ++ NewSolveds,
NewUnsolveds ++ Unchanged)
end.
iter_unsolved([], _) -> {[], []};
iter_unsolved([Cell|Rest], Sudoku) ->
{Changed, Unchanged} = iter_unsolved(Rest, Sudoku),
Deduceds = deduce_possibles(Cell, Sudoku),
case length(Deduceds) == 1 of
true -> {[Cell#cell{possibles=Deduceds}] ++ Changed,
Unchanged};
false ->
NewPossibles = collapse_possibles(Cell, Sudoku),
case (length(NewPossibles) == 0) or
(Cell#cell.possibles == NewPossibles) of
true -> {Changed, [Cell] ++ Unchanged};
false -> {[Cell#cell{possibles=NewPossibles}]
++ Changed,
Unchanged}
end
end.
test_do_solve() ->
% solved
[{cell,1,1,1,[1]}] = do_solve([], [{cell,1,1,1,[1]}]),
% unsolved
Sudoku = compile_sudoku([[x,x,3,x,x,x,x,1,x],
[9,x,1,x,3,x,8,x,7],
[x,x,x,9,5,x,x,3,4],
[1,5,7,x,x,x,x,x,x],
[x,x,x,x,7,x,x,x,x],
[x,x,x,x,x,x,7,8,6],
[3,9,x,x,8,6,x,x,x],
[6,x,5,x,4,x,1,x,8],
[x,1,x,x,x,x,2,x,x]]),
S = do_solve([], Sudoku),
io:format("S: ~p~n", [format_solution(S)]),
ok.
split_rows([], _) ->
[];
split_rows(Cells, Y) ->
{This, Rest} = lists:partition(fun(C) -> C#cell.y == Y end, Cells),
%io:format("this: ~p, rest: ~p~n", [This, Rest]),
Row = lists:map(fun(C) -> C#cell.possibles end, lists:keysort(2, This)),
%io:format("Row: ~p~n", [Row]),
[Row] ++ split_rows(Rest, Y + 1).
extract_values([]) -> [];
extract_values([Row|Rest]) ->
ORow = lists:flatmap(fun(C) ->
%io:format("C: ~p~n", [C]),
if
length(C) == 1 -> C;
true -> [x]
end
end, Row),
%io:format("ORow: ~p~n", [ORow]),
[ORow] ++ extract_values(Rest).
split_rows_and_extract_value(Cells, N) ->
extract_values(split_rows(Cells, N)).
test_split_rows_and_extract_value() ->
[] = split_rows_and_extract_value([], 0),
[[x]] = split_rows_and_extract_value([{cell,1,1,1,[1,2]}], 1),
[[1,2],[3,4]] =
split_rows_and_extract_value([{cell,1,1,1,[1]},{cell,2,1,1,[2]},{cell,1,2,1,[3]},{cell,2,2,1,[4]}],
1),
[[1,2],[3,4],[5,6]] =
split_rows_and_extract_value([{cell,2,3,1,[6]},{cell,2,2,1,[4]},{cell,1,2,1,[3]},{cell,2,1,1,[2]},{cell,1,3,1,[5]},{cell,1,1,1,[1]}],
1),
ok.
format_solution(Solution) ->
split_rows_and_extract_value(Solution, 1).
test_format_solution() ->
[[1]] = format_solution([{cell,1,1,1,[1]}]),
[[1,2]] = format_solution([{cell,1,1,1,[1]}]),
% perverse test
[[1,2,3,4],
[2,3,4,5],
[3,4,5,6],
[4,5,6,7]] = format_solution([{cell,4,4,x,[7]},
{cell,1,4,x,[4]},
{cell,1,1,x,[1]},
{cell,4,1,x,[4]},
{cell,2,2,x,[3]},
{cell,3,3,x,[5]},
{cell,2,1,x,[2]},
{cell,3,1,x,[3]},
{cell,1,2,x,[2]},
{cell,1,3,x,[3]},
{cell,2,3,x,[4]},
{cell,3,2,x,[4]},
{cell,2,4,x,[5]},
{cell,3,4,x,[6]},
{cell,4,2,x,[5]},
{cell,4,3,x,[6]}]),
ok.
pretty_print_cell(x) -> " ";
pretty_print_cell(C) -> integer_to_list(C).
pretty_print_row([]) ->
io:format("~n"),
ok;
pretty_print_row([Cell|Rest]) ->
case (length(Rest) + 1) rem 3 == 0 of
true -> io:format("|");
false -> ok
end,
io:format(" ~s ", [pretty_print_cell(Cell)]),
pretty_print_row(Rest).
pretty_print([]) -> ok;
pretty_print([Row|Rest]) ->
case (length(Rest) + 1) rem 3 == 0 of
true -> io:format("~s~n", [lists:map(fun(_) -> "-" end,
lists:seq(1, length(Row) * 3 + 2) )]);
false -> ok
end,
pretty_print_row(Row),
io:format("~n"),
pretty_print(Rest).
solve(Grid) ->
Sudoku = compile_sudoku(Grid),
format_solution(do_solve([], Sudoku)).
test_solve() ->
solve(?test_grid).
%% tests
test_all() ->
%ok = test_row(),
%ok = test_col(),
%ok = test_box(),
%ok = test_cell(),
%ok = test_is_empty(),
ok = test_calc_block(),
ok = test_calc_possibles(),
ok = test_compile_cell(),
ok = test_compile_row(),
ok = test_compile_sudoku(),
ok = test_split_rows_and_extract_value(),
ok = test_definites(),
ok = test_collapse_possibles(),
ok = test_keyfilter(),
ok = test_do_solve(),
ok.
_______________________________________________
coders mailing list
coders@slug.org.au
http://lists.slug.org.au/listinfo/coders
