Sudoku

Orbitz - orbitz - November 15, 2006

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.

Categories: Blogs  Orbitz  

Comments

No comments so far, you could be the first.

Add comment

Name:

Email:

URL:

Smileys

Remember my personal information

Notify me of follow-up comments?