[erlang-questions] Re: [erlang-questions 39] Re: A sudoku solver in Erlang compared to Python

Andreas Pauley apauley@REDACTED
Tue Mar 29 12:02:11 CEST 2011


Unfortunately it's not that easy this time.
The major reduction in eliminations happens because is_unit_solved/2
always returns true after the proposed change.
If you open any of the .out files (eg hardest.out) you'll see that the
puzzles aren't really solved.

Luckily the unit tests pointed this out.

But all is not lost, I still got a simplification out of the deal.
We still need to check the non-unique length of UnitValues in that
function, but the second clause does not need to use sets anymore:
https://github.com/apauley/sudoku-in-erlang/commit/f092e55df292d1f12ff8406ce60bb435e7a83667


On Mon, Mar 28, 2011 at 4:39 PM, Ahmed Omar <spawn.think@REDACTED> wrote:
> Hi Andreas,
> For some reason, lists:usort is your friend again!
> Looking into the code deeper, one line can give u huge boost!
> You compare the unit values with digits with
>   (length(UnitValues) == 9)
>     and (gb_sets:from_list(UnitValues) == gb_sets:from_list(digits())).
> I understand (correct me if i'm wrong) u check first the length to make sure
> it's 9 digits then u convert to sets to make sure they r unique and compare
> them. But if you think about it, if the unique list of values is of length
> 9, u don't need more comparisons!
> so u can actually just do
> (length(lists:usort(UnitValues)==9)
> before the change:
> sudoku:print_results("top95.txt").
> Solved 95 of 95 puzzles from top95.txt in 1.937175 secs (49.04 Hz)
>   (210794 total eliminations, avg 2218.88, median 1536, max 10664, min 648).
> after the change :
> sudoku:print_results("top95.txt").
> Solved 95 of 95 puzzles from top95.txt in 0.382337 secs (248.47 Hz)
>   (45002 total eliminations, avg 473.71, median 479, max 518, min 427).
>
> On Mon, Mar 28, 2011 at 3:32 PM, Andreas Pauley <apauley@REDACTED> wrote:
>>
>> Hi Tristan,
>>
>> I tried the code in your repo, but it wasn't significantly faster on my
>> machine.
>>
>> It was interesting though to go through your refactorings.
>> I see you changed the signature for solve so that the empty puzzle and
>> the list of square names are passed in from the start.
>> Maybe I should try this approach in conjunction with the conversion to
>> atoms...
>>
>> Regards,
>> Andreas
>>
>> On Sat, Mar 26, 2011 at 10:56 PM, Tristan Sloughter
>> <tristan.sloughter@REDACTED> wrote:
>> > With a few refactorings (https://github.com/tsloughter/sudoku-in-erlang
>> > --
>> > note I used ewl_plists just to make the code simpler:
>> > https://github.com/erlware/erlware/tree/master/lib/ewlib) and compile
>> > with
>> > native, hipe o3 it beats python's:
>> > $ ./sudoku.py
>> > All tests pass.
>> > Solved 50 of 50 puzzles from easy50.txt in 0.529119 secs (94.50 Hz)
>> >   (33059 total eliminations, avg 661.00, median 648, max 830, min 648).
>> > Solved 95 of 95 puzzles from top95.txt in 3.889944 secs (24.42 Hz)
>> >   (221997 total eliminations, avg 2336.00, median 1492, max 11512, min
>> > 648).
>> > Solved 11 of 11 puzzles from hardest.txt in 0.157520 secs (69.83 Hz)
>> >   (9436 total eliminations, avg 857.00, median 817, max 1198, min 648).
>> > $ ./sudoku
>> > All tests passed :-)
>> > Solved 50 of 50 puzzles from easy50.txt in 0.556385 secs (89.87 Hz)
>> >   (92538 total eliminations, avg 1850.76, median 1811, max 2628, min
>> > 1767).
>> > Solved 95 of 95 puzzles from top95.txt in 3.593476 secs (26.44 Hz)
>> >   (901201 total eliminations, avg 9486.33, median 6267, max 56820, min
>> > 1792).
>> > Solved 11 of 11 puzzles from hardest.txt in 0.162107 secs (67.86 Hz)
>> >   (33653 total eliminations, avg 3059.36, median 3023, max 5346, min
>> > 1786).
>> > I ran a number of times, those are pretty much what it always comes out
>> > to.
>> > But I haven't really tried a full refactoring, I think a number of
>> > things
>> > can be reduced to less iterations.
>> >
>> > Tristan
>> > On Sat, Mar 26, 2011 at 3:39 PM, Ahmed Omar <spawn.think@REDACTED>
>> > wrote:
>> >>
>> >> 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.think@REDACTED>
>> >> wrote:
>> >>>
>> >>> actually instead of doing
>> >>>
>> >>>     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 <mevans@REDACTED>
>> >>> 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.think@REDACTED]
>> >>>> Sent: Saturday, March 26, 2011 3:08 PM
>> >>>> To: Andreas Pauley
>> >>>> Cc: Evans, Matthew; erlang-questions@REDACTED
>> >>>> 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
>> >>>> <apauley@REDACTED<mailto:apauley@REDACTED>> wrote:
>> >>>> Thanks, I've changed the compile options and this definitely makes it
>> >>>> somewhat faster:
>> >>>>
>> >>>>
>> >>>> https://github.com/apauley/sudoku-in-erlang/commit/b7ce2abb6ca013850ed8f3e8fd7f5f6be7004cbb
>> >>>>
>> >>>> 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
>> >>>> <mevans@REDACTED<mailto:mevans@REDACTED>> 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-bounces@REDACTED<mailto:erlang-questions-bounces@REDACTED>
>> >>>> >
>> >>>> > [mailto:erlang-questions-bounces@REDACTED<mailto:erlang-questions-bounces@REDACTED>]
>> >>>> > On Behalf Of Andreas Pauley
>> >>>> > Sent: Friday, March 25, 2011 8:15 AM
>> >>>> > To: erlang-questions@REDACTED<mailto:erlang-questions@REDACTED>
>> >>>> > 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-questions@REDACTED<mailto:erlang-questions@REDACTED>
>> >>>> > http://erlang.org/mailman/listinfo/erlang-questions
>> >>>> >
>> >>>> _______________________________________________
>> >>>> erlang-questions mailing list
>> >>>> erlang-questions@REDACTED<mailto:erlang-questions@REDACTED>
>> >>>> http://erlang.org/mailman/listinfo/erlang-questions
>> >>>>
>> >>>>
>> >>>>
>> >>>> --
>> >>>> Best Regards,
>> >>>> - Ahmed Omar
>> >>>> http://nl.linkedin.com/in/adiaa
>> >>>> Follow me on twitter
>> >>>> @spawn_think<http://twitter.com/#!/spawn_think>
>> >>>>
>> >>>
>> >>>
>> >>>
>> >>> --
>> >>> Best Regards,
>> >>> - Ahmed Omar
>> >>> http://nl.linkedin.com/in/adiaa
>> >>> Follow me on twitter
>> >>> @spawn_think
>> >>
>> >>
>> >>
>> >> --
>> >> Best Regards,
>> >> - Ahmed Omar
>> >> http://nl.linkedin.com/in/adiaa
>> >> Follow me on twitter
>> >> @spawn_think
>> >>
>> >> _______________________________________________
>> >> erlang-questions mailing list
>> >> erlang-questions@REDACTED
>> >> http://erlang.org/mailman/listinfo/erlang-questions
>> >>
>> >
>> >
>
>
>
> --
> Best Regards,
> - Ahmed Omar
> http://nl.linkedin.com/in/adiaa
> Follow me on twitter
> @spawn_think
>



More information about the erlang-questions mailing list