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:

Anonymous Anonymous said...

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

15 November, 2006 02:57  
Blogger orbitz said...

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

15 November, 2006 23:47  
Anonymous Anonymous said...

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.

16 November, 2006 15:51  
Blogger Jordan Wilberding said...

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.

30 March, 2007 23:20  
Anonymous Anonymous said...

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

27 November, 2007 07:54  
Blogger John said...

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"

28 May, 2009 22:48  
Blogger Bruce Fredman said...

Hi,
We at Chessboss.com strongly believe in necessity of chess to increase both knowledge and understanding. It is unfortunate that the oldest game in the world (Chess) has a very little fan base, ChessBoss.com aims to change that. We understand the importance of blogs and the information made available on them. We are working towards building a strong fan base around our FREE chess server to better increase the use of Chess online. Your blog seems to have a large viewing public and seems to hold great information which I would love to make available to my viewing public.

I have included the code for the ChessBoss.com banner within the body of this email along with textual link information. I would be pleased to offer you the ChessBoss.com featured blogger badge to post on your site, recognizeing your blog as a leading contributor to the Chess community. Thank you for your great work and dedication, we look forward to your response!Please reply me back with subject line of your Url to avoid spam and to make sure YOU get the Award.

Thank you.

23 November, 2009 14:05  

Post a Comment

<< Home