The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion A sudoku solver in Erlang compared to Python

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Mar 26 2011, 6:33 pm
From: "Evans, Matthew" <mev...@verivue.com>
Date: Sat, 26 Mar 2011 18:33:31 -0400
Local: Sat, Mar 26 2011 6:33 pm
Subject: [erlang-questions 41] Re: A sudoku solver in Erlang compared to Python
Awesome point, I was going to actually suggest that since this is all calculating static data he just pre-calculates it and puts it in a -define. Or even better, if he is brave he could write a parse transform.

Using Ulf's ct_expand module (http://forum.trapexit.org/viewtopic.php?p=20260) I get even better performance:

Without the parse transform (but using native):

4> sudoku:print_results("top95.txt", "\n").
Solved 95 of 95 puzzles from top95.txt in 0.827966 secs (114.74 Hz)
(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).
ok

With a parse transform:

2>  sudoku:print_results("top95.txt", "\n").
Solved 95 of 95 puzzles from top95.txt in 0.469908 secs (202.17 Hz)
(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).

The code looks like:

-compile({parse_transform, ct_expand}).

squares() ->
%% Returns a list of 81 square names, including "A1" etc.
ct_expand:term(
[[X,Y] || X <- "ABCDEFGHI", Y <- "123456789"]
).
col_squares() ->
%% All the square names for each column.
ct_expand:term(
[[[X,Y] || X <- "ABCDEFGHI", Y <- [C]] || C <- "123456789"]
).
row_squares() ->
%% All the square names for each row.
ct_expand:term(
[[[X,Y] || X <- [R], Y <- "123456789"] || R <- "ABCDEFGHI"]
).
box_squares() ->
%% All the square names for each box.
ct_expand:term(
[[[X,Y] || X <- R, Y <- C] || R <- ["ABC", "DEF", "GHI"], C <- ["123", "456", "789"]]
).

________________________________________
From: Ahmed Omar [spawn.th...@gmail.com]
Sent: Saturday, March 26, 2011 4:39 PM
To: Evans, Matthew
Cc: Andreas Pauley; erlang-questi...@erlang.org
Subject: Re: [erlang-questions 20] Re: A sudoku solver in Erlang compared to Python

BTW, beside looking into reducing eleminations (which requires deep dive), if u do some time profiling using eprof u will find that most of the time spent actually in the cross functions
sudoku:'-cross/2-lc\$^1/1-1-'/4                       96558660  37.46  35024918  [      0.36]

On Sat, Mar 26, 2011 at 9:33 PM, Ahmed Omar <spawn.th...@gmail.com<mailto:spawn.th...@gmail.com>> wrote:

NonUniquePeers = shallow_flatten([S || S <- units(Square)]),

PeerSet = sets:from_list(NonUniquePeers),

PeersWithSelf = sets:to_list(PeerSet),

can't u just do

PeersWithSelf = lists:usort(NonUniquePeers).

?

On Sat, Mar 26, 2011 at 9:14 PM, Evans, Matthew <mev...@verivue.com<mailto:mev...@verivue.com>> wrote:

Good call....gb_sets should be faster. Compiled to native it runs faster still

9> sudoku:print_results("top95.txt", "\n").
Solved 95 of 95 puzzles from top95.txt in 0.810156 secs (117.26 Hz)
(901201 total eliminations, avg 9486.33, median 6267, max 56820, min 1792).
ok

________________________________________
From: Ahmed Omar [spawn.th...@gmail.com<mailto:spawn.th...@gmail.com>]
Sent: Saturday, March 26, 2011 3:08 PM
To: Andreas Pauley
Cc: Evans, Matthew; erlang-questi...@erlang.org<mailto:erlang-questi...@erlang.org>
Subject: Re: [erlang-questions 20] Re: A sudoku solver in Erlang compared to Python

using gb_sets instead of sets could decrease eliminations a bit and give u some boost. However, i didn't dive deeper into the code or the algorithm.

On Sat, Mar 26, 2011 at 9:41 AM, Andreas Pauley <apau...@gmail.com<mailto:apau...@gmail.com><mailto:apau...@gmail.com<mailto:apau...@gmail.com>>> wrote:
Thanks, I've changed the compile options and this definitely makes it
somewhat faster:
https://github.com/apauley/sudoku-in-erlang/commit/b7ce2abb6ca013850e...

Strangely the native flag is not documented here:
http://www.erlang.org/doc/man/compile.html#file-2

The more interesting improvement would be to decrease the number of
eliminations performed, but for that I'll have to go deep into the
code :-)

On Sat, Mar 26, 2011 at 12:16 AM, Evans, Matthew <mev...@verivue.com<mailto:mev...@verivue.com><mailto:mev...@verivue.com<mailto:mev...@verivue.com>>> wrote:

> Without going deep into the code, one thing to try is compile with the native flag (running the tests from the VM shell here):

> Without native set:
> 18> c(sudoku).
> {ok,sudoku}
> 19>  sudoku:print_results("top95.txt", "\n").
> Solved 95 of 95 puzzles from top95.txt in 2.038825 secs (46.60 Hz)
> (922678 total eliminations, avg 9712.40, median 6596, max 55370, min 1797).
> ok

> With native set:
> 20> c(sudoku,[native]).
> {ok,sudoku}
> 21>  sudoku:print_results("top95.txt", "\n").
> Solved 95 of 95 puzzles from top95.txt in 1.613416 secs (58.88 Hz)
> (922678 total eliminations, avg 9712.40, median 6596, max 55370, min 1797).

> -----Original Message-----
> From: erlang-questions-boun...@erlang.org<mailto:erlang-questions-boun...@erlang.org><mailto:erlang-questions-boun...@erlang.org<mailto:erlang-questions-boun...@erlang.org>> [mailto:erlang-questions-boun...@erlang.org<mailto:erlang-questions-boun...@erlang.org><mailto:erlang-questions-boun...@erlang.org<mailto:erlang-questions-boun...@erlang.org>>] On Behalf Of Andreas Pauley
> Sent: Friday, March 25, 2011 8:15 AM
> To: erlang-questi...@erlang.org<mailto:erlang-questi...@erlang.org><mailto:erlang-questi...@erlang.org<mailto:erlang-questi...@erlang.org>>
> Subject: [erlang-questions 4] A sudoku solver in Erlang compared to Python

> Hi all,

> In my quest to learn Erlang I've translated Peter Norvig's sudoku
> solver into Erlang:
> https://github.com/apauley/sudoku-in-erlang

> For comparison, my slightly modified version of Norvig's Python code
> can be found here:
> https://github.com/apauley/sudoku-by-norvig

> I like the pattern matching, it was fun to do the entire solution
> without a single if or case statement :-)
> Something that bothers me though is that the Python solution seems to
> be faster, even after I've made the Erlang solution use multiple
> processors.

> In order to compare the two solutions I counted the number of
> eliminations each performed.
> The eliminate function is the core of the solution, for example
> assigning a single value to a square is implemented as the elimination
> of all other values.

> With the Erlang implementation I get:
> sudoku-in-erlang\$ ./sudoku
> All tests passed :-)
> Solved 50 of 50 puzzles from easy50.txt in 2.890978 secs (17.30 Hz)
>  (93403 total eliminations, avg 1868.06, median 1810, max 2517, min 1770).
> Solved 95 of 95 puzzles from top95.txt in 22.004369 secs (4.32 Hz)
>  (922678 total eliminations, avg 9712.40, median 6596, max 55370, min 1797).
> Solved 11 of 11 puzzles from hardest.txt in 0.851678 secs (12.92 Hz)
>  (32339 total eliminations, avg 2939.91, median 2894, max 4779, min 1781).

> And with the Python implementation:
> sudoku-by-norvig\$ ./sudoku.py
> All tests pass.
> Solved 50 of 50 puzzles from easy50.txt in 0.792008 secs (63.13 Hz)
>  (33059 total eliminations, avg 661.00, median 648, max 830, min 648).
> Solved 95 of 95 puzzles from top95.txt in 5.903875 secs (16.09 Hz)
>  (221997 total eliminations, avg 2336.00, median 1492, max 11512, min 648).
> Solved 11 of 11 puzzles from hardest.txt in 0.237532 secs (46.31 Hz)
>  (9436 total eliminations, avg 857.00, median 817, max 1198, min 648).

> So according to the stats above, the Python solution performs less
> computations when given exactly the same input.
> The Erlang code is as close to the Python as I could make it, I've
> done more or less a direct translation of the algorithms used.

> I suspect that there are some lazy evaluation happening in the Python
> version, possibly generators, although I haven't pinpointed it yet.

> How can I improve my Erlang code in this solution?

> Kind regards,
> Andreas
> _______________________________________________
> erlang-questions mailing list
> erlang-questi...@erlang.org<mailto:erlang-questi...@erlang.org><mailto:erlang-questi...@erlang.org<mailto:erlang-questi...@erlang.org>>
> http://erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
erlang-questi...@erlang.org<mailto:erlang-questi...@erlang.org><mailto:erlang-questi...@erlang.org<mailto:erlang-questi...@erlang.org>>
http://erlang.org/mailman/listinfo/erlang-questions

--
Best Regards,
- Ahmed Omar

--
Best Regards,
- Ahmed Omar

--
Best Regards,
- Ahmed Omar

_______________________________________________
erlang-questions mailing list
erlang-questi...@erlang.org
http://erlang.org/mailman/listinfo/erlang-questions