maarten van damme:

> http://dpaste.dzfl.pl/8a2aef5b

Some suggestions about the code:
- Put a space before and after operators, after a commas and semicolon, around "..", etc.
- Compile with "-wi -property";
- Try to add pure/const/nothrow/immutable where possible;
- Minimize the need of cast();
- Sometimes it's useful to localize the imports (stdio e datetime are used just by the main);
- Minimize the usage of magical constants like 0b10_0000_0000, possibly define it only once. And often adding underscores inside long numbers is handy (here I have put them every 4 digits because it's binary);
- Repeating things like "short[81]" in many function signatures is quite bad. Better to define a global type with alias (or someday better with std.typecons.Typedef when it will work), and then use it;
- Generally it's better to use unsigned values for array indexes;
- If you look for performance and your program is single thread, then it's better to annotate global variables with __gshared;

- This:
    ubyte[81] taken = false;
is better than this:
    ubyte[81] taken;
    taken[] = false;


This is your code modified, it's also a little faster:
http://dpaste.dzfl.pl/06510dcd

I will try to replace the int[] of cachedBitsetToRange with something more static, to reduce indirection.

Bye,
bearophile

> I will try to replace the int[] of cachedBitsetToRange with something more static, to reduce indirection.

Yeah, it's a bit faster, but not a lot:
http://dpaste.dzfl.pl/b04a0127

Bye,
bearophile

> Some suggestions about the code:
Thank you very much for your criticism, there are indeed a lot of points where I have to improve on.

> - Put a space before and after operators, after a commas and semicolon,
> around "..", etc.
> - Compile with "-wi -property";
> - Try to add pure/const/nothrow/immutable where possible;

I realize the usefullness of keywords like these but having to type
them over and over again tends to become rather annoying. There are
functions where the implementation is shorter than it's declaration...
Is there a special reason I should use them in little programs like these?

> - Minimize the need of cast();
> - Sometimes it's useful to localize the imports (stdio e datetime are used
> just by the main);
> - Minimize the usage of magical constants like 0b10_0000_0000, possibly
> define it only once. And often adding underscores inside long numbers is
> handy (here I have put them every 4 digits because it's binary);
> - Repeating things like "short[81]" in many function signatures is quite
> bad. Better to define a global type with alias (or someday better with
> std.typecons.Typedef when it will work), and then use it;
> - Generally it's better to use unsigned values for array indexes;
> - If you look for performance and your program is single thread, then it's
> better to annotate global variables with __gshared;

I'm not all that familiar with __gshared, why does it increase performance?

>
> - This:
>     ubyte[81] taken = false;
> is better than this:
>     ubyte[81] taken;
>     taken[] = false;

I know and I think I can even leave false out because the default value of ubyte is 0 => false. I had a big in my code and it took me a long time to find it. That line is a leftover of a desperate attempt at finding it :) (as is line 101)

I even tried using array!bool but even instantiating failed so I gave up. Would performance increase be noticeable? I guess not.
>
>
> This is your code modified, it's also a little faster: http://dpaste.dzfl.pl/06510dcd
>

Thank you. I see you also used contracts, looks better now :)
(using contracts is really something I should start doing...)

> I will try to replace the int[] of cachedBitsetToRange with something more static, to reduce indirection.
>
> Bye,
> bearophile


I should also add a little check to see if every value I put is indeed numerical.

On 08/24/2012 09:32 PM, maarten van damme wrote:
> I've distiled what I understood from your source and the resulting
> executable managed to solve the impossible one in 27 seconds while
> your source takes 41 seconds.
>

It is 10s vs 13s with GDC on my machine.

and everythingPossible should also be changed to something ala 2 ^(side) -1

2012/8/25 Timon Gehr <timon.gehr@gmx.ch>:
> On 08/24/2012 09:32 PM, maarten van damme wrote:
>>
>> I've distiled what I understood from your source and the resulting executable managed to solve the impossible one in 27 seconds while your source takes 41 seconds.
>>
>
> It is 10s vs 13s with GDC on my machine.
>

I've only tried dmd but I'm installing gdc on this laptop too.
When that's done I'm going to see how they both perform on this puzzle
: http://en.wikipedia.org/wiki/File:Sudoku_puzzle_hard_for_brute_force.jpg

maarten van damme:

> Is there a special reason I should use them in little programs like these?

In my experience small programs contain lot of the issues and ideas contained in large programs. Using things like "pure" and "const/immutable" helps avoid/catch some bugs even in small programs.
Generally try to make your code as strong as possible, to avoid chances of introducing bugs.


> I'm not all that familiar with __gshared, why does it increase performance?

That implements global variables as in C. Take a look at the D docs, about thread-local memory, etc.


> Would performance increase be noticeable? I guess not.

In your code I have seen performance increase replacing ubyte[] with bool[].


> (using contracts is really something I should start doing...)

Yep. It's a matter of self-training.


> I should also add a little check to see if every value I put is indeed numerical.

That's very easy to do:

    if (args[1].length != size || args[1].countchars("0-9") != args[1].length) {
        writeln("A sudoku is 81 0-9 digits, not ", args[1].length, " digits");
        return;
    }

Bye,
bearophile

On 08/25/2012 01:01 AM, Timon Gehr wrote:
> On 08/24/2012 09:32 PM, maarten van damme wrote:
>> I've distiled what I understood from your source and the resulting
>> executable managed to solve the impossible one in 27 seconds while
>> your source takes 41 seconds.
>>
>
> It is 10s vs 13s with GDC on my machine.
>

I have inlined some ranges.

http://dpaste.dzfl.pl/4a7e4038

I now measure 10.5s vs 6.7s (GDC) and 20s vs 12s (DMD).

On 08/25/2012 02:38 AM, Timon Gehr wrote:
> On 08/25/2012 01:01 AM, Timon Gehr wrote:
>> On 08/24/2012 09:32 PM, maarten van damme wrote:
>>> I've distiled what I understood from your source and the resulting
>>> executable managed to solve the impossible one in 27 seconds while
>>> your source takes 41 seconds.
>>>
>>
>> It is 10s vs 13s with GDC on my machine.
>>
>
> I have inlined some ranges.
>
> http://dpaste.dzfl.pl/4a7e4038
>
> I now measure 10.5s vs 6.7s (GDC) and 20s vs 12s (DMD).

I meant to paste this: http://dpaste.dzfl.pl/8fa23a97

On Friday, 24 August 2012 at 23:14:02 UTC, maarten van damme wrote:
> http://en.wikipedia.org/wiki/File:Sudoku_puzzle_hard_for_brute_force.jpg

It occurs to me that one of the main reasons why this particular puzzle would be hard for brute force is that the first line is blank and more than half of the second line is blank, and it seems like it is designed to have as many choices as possible before a set square is encountered.

I bet it could be solved much quicker by a computer by doing it in reverse.

I've got some ideas, maybe I'll write a solution to this myself. :)