Tuesday, November 14, 2006

Sudoku

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.

7 comments:

  1. Nice. As a comparision; perhaps you could solve it by using the new Prolog plugin for Erlang (see User Contrib at trapexit.org).

    ReplyDelete
  2. Hrm solving it in Prolog does seem rather interesting. I unfortunately don't know much Prolog but I will look into it, thanks

    ReplyDelete
  3. Some ideas to make the world's leading scalable sudoku solver:
    * solving alphabetical sudoku's (with a, b, c,.. instead of 1, 2 and 3)
    * solving graphical sudoku's (with pictures instead of numbers)
    * integrate it in ErlyWeb for a userfriendly front end
    * solving other special sudoku's (e.g. there exists a sudoku in which you also need to have the numbers 1 to 9 diagonally on the sudoku.

    ReplyDelete
  4. Just thought you might be interested in this.

    http://dnovatchev.spaces.live.com/Blog/cns!44B0A32C2CCF7488!355.entry

    I ran your code, it took me 1.7 seconds with it.

    ReplyDelete
  5. I have used Orbitz, hotwire, Expedia and Travelocity, all have their pro's and con's.

    I spotted a site called Anyfares.com, found air tickets so cheap that my savings were about 35% cheaper than Orbitz, hotwire, Expedia and Travelocity. Flights internationally such as Europe in particular that are great and South America, China and middle East countries, they have excellent rates. Domestic though there are some what competitive where I used either Hotwire or the airlines direct from their web sites.

    What I really like about Anyfares.com is they sell tickets on US dollars in foreign countries and all their tickets are e-tickets so if you are in France and need a fight to St.Petersburg Russia or London or Frankfurt, they sell everything in US dollars and you have your tickets emailed in 10 minutes so you can just travel just like that. Orbitz, Expedia and Travelocity, they sell their tickets if you are out of the US, they will charged you the currency in that country if you want to fly from there to somewhere else. So if I was in France for example and I want to fly to London, Frankfurt or anywhere, they will charge me in Euros or Pound Notes (it is like charging you double when the US dollar is so weak) when if you are an American and want to save, you can't save because Orbitz, Expedia, Travelocity will charged the currency if you are outside the United States but with Anyfares.com, they don't. Euros, Swiss Marks, British Pounds, Russian Rubles and etc, they currencies are high to the US dollar and if you are an American, you are stuck if you have to meet those currencies if you have only US dollars.

    So consider if you have a money budget and you can't afford the high currencies, try http://www.anyfares.com

    Jim

    ReplyDelete
  6. We would like to nominate you for a FreedomToBlog.com Best of Blog Entry.

    Please visit our site at: http://www.freedomtoblog.com to submit your blog entry!

    Benefits include:
    1) Permanent Backlinks to your blog
    2) Fully SEO optimized for maximum exposure
    3) A chance to be published into a top 500 best of blog book"

    ReplyDelete
  7. Unfortunately doesn't seem to work. e.g.:

    1> {solved, Res} = sudoku:solve([
    1> [4, b, 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).
    4 1 9 8 5 6 4 7 2
    4 5 8 7 3 2 9 6 1
    6 2 7 4 9 1 8 5 3
    5 8 2 9 6 4 3 1 7
    9 3 1 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

    ReplyDelete