On Wednesday, 15 August 2012 at 20:13:10 UTC, Era Scarecrow wrote:
> On Wednesday, 15 August 2012 at 15:39:26 UTC, ixid wrote:
>> Could you supply your code? Which one are you using as the hardest? If you're solving the 1400 second one in 12 seconds that's very impressive, I can't get it below 240 seconds.
>
> Expanded to 225 lines after comments and refactoring for names. I think it should be fairly easy to follow.
>
> https://github.com/rtcvb32/D-Sudoku-Solver
>
> Output:
>
> $ dmd sudoku_solve.d -g -O
> $ time ./sudoku_solve.exe .....6....59.....82....8....45........3........6..3.54...325..6..................
>
> .....6...
> .59.....8
> 2....8...
> .45......
> ..3......
> ..6..3.54
> ...325..6
> .........
> .........
>
>
> 138246579
> 659137248
> 274598163
> 745682391
> 813459627
> 926713854
> 487325916
> 362971485
> 591864732
>
> Start: TickDuration(3610965141031)
> End:   TickDuration(3611099830488)
> Time:  TickDuration(134689457)
>
> real    0m9.565s
> user    0m0.015s
> sys     0m0.046s

How many solutions do you find for that one?

Jonathan M Davis:

> and the code is lightning fast. It would probably have to be tweaked to match
> whatever Bearophile's code does though as far is input goes (I haven't looked
> at the code that he linked to). It also makes no attempt at being compact
> (e.g. it actually checks the command line arguments).

The point of this thread is not to write a good idiomatic D Sudoku solver, but to translate the original Python code to D, and look at how good and how short the resulting code is (just like he has done in C++11).

It's like how much pythonic code you are allowed to write in C++11/D :-) It sounds like a silly purpose, but there's a lot of Python code out there, and I translate quite often Python code to D.

Bye,
bearophile

Jonathan M Davis:

> It would probably have to be tweaked to match
> whatever Bearophile's code does though as far is input goes (I haven't looked at the code that he linked to).

And the original Python code is not mine, it's from the AI researcher Peter Norvig :-)

Bye,
bearophile

On 08/15/2012 12:31 AM, bearophile wrote:
> http://www.reddit.com/r/cpp/comments/y6gwk/norvigs_python_sudoku_solver_ported_to_c11/
>
>
> http://nonchalantlytyped.net/blog/2012/08/13/sudoku-solver-in-c11/
>
> His C++11 port is 316 lines long:
> https://gist.github.com/3345676
>
> How many lines for a (not golfed) D translation of the original Python
> code?
>
> Bye,
> bearophile

Probably not what you want, but solves sudoku quite well:
dpaste.dzfl.pl/69669b05

On Wednesday, 15 August 2012 at 22:38:58 UTC, ixid wrote:
> How many solutions do you find for that one?

 Don't know, it actually just stops after finding the first one. Modifying it to give all possible outputs wouldn't be too hard... So far having it running it's found over 23k+ combinations after about 3 minutes. Course if it's going to be a lot of output (like it is) then I'm probably going to have it forgo printing every single one.

On Thursday, 16 August 2012 at 01:05:20 UTC, Era Scarecrow wrote:
> So far having it running it's found over 23k+ combinations after about 3 minutes.

 Unless I introduced a bug... Now I'll have to speed it up to make sure and won't take an afternoon to calculate.

This is my attempt at a D solver, it's a pretty direct translation of a C++ version I wrote but it's a lot slower in D, around 1/4 the speed sadly, 2x because of the compiler I think and 2x because in C++ I can use proper bitfields which seem to give another 2x speed up (halving the size of the main data structure) while in D trying to use bitfields just slows it down significantly.

module main;
import std.stdio, std.datetime, std.conv, std.string;

enum DIMY = 9;
enum DIMX = 9;
sudoku[] solved;

struct sudoku {
    struct bits {
        uint value = 0;
        uint b = 0;
    }
    bits[DIMY][DIMX] s;
    uint blk = 0;
}

//Output
void output(sudoku a) {
	foreach(i;0..DIMY) {
		foreach(j;0..DIMX) {
			a.s[i][j].value == 0? '.'.write : a.s[i][j].value.write;		
			if(j == 2 || j == 5)
                " ".write;
		}
		if(i == 2 || i == 5)
			"\n".writeln;
		else writeln;;
	}
	"\n".writeln;
}

string[] mixin1() {
    string[] res;
    foreach(i;0..9)
        res ~= "case " ~ (511 - 2^^i).to!string ~ " : {a.s[i][j].value = "
            ~ (i + 1).to!string ~ "; bl(a,i,j); break;}";
    return res;
}

//Block
void bl(ref sudoku a, uint i, uint j) {
	++a.blk; //Count new blocking
	//Determines which 3x3 block the square is in
	const uint c = i / 3 * 3;
	const uint d = j / 3 * 3;
	const uint temp = 1 << (a.s[i][j].value - 1); //Block this value

    foreach(k;0..3)
        foreach(m;0..3)
            a.s[c + k][d + m].b |= temp;

    foreach(n;0..9) {
        a.s[n][j].b |= temp;
        a.s[i][n].b |= temp;
    }
}

//Solving Function
void solve(sudoku a) {
	while(solved.length == 0) {
		foreach(i;0..DIMY)
            foreach(j;0..DIMX)
				if(a.s[i][j].value == 0)
					//Bitmask values where one is unblocked so should be filled in
                    switch (a.s[i][j].b) {
						case 511 : return; //Square unfilled but blocked so incorrect
                        mixin(mixin1.join);
                        default :
					}

		//If we have won
		if(a.blk == DIMY * DIMX) {
			solved ~= a;
            return;
		}
        else {
		    //Make new copy of board and blockers with the guess and call solve function
		    sudoku b = a;
		    foreach(i;0..DIMY)
                foreach(j;0..DIMX)
				    if(b.s[i][j].value == 0) {
					    foreach(k;0..9)
                            if((b.s[i][j].b & 2^^k) == false) {
                                b.s[i][j].value = k + 1;
                                bl(b,i,j); a.s[i][j].b |= 2^^k;
                                break;
                            }
					    goto from;
				    }
            from: solve(b);
        }
	}
}

//Main
void main() {
	StopWatch sw;
    sw.start;

    /*
    //Easy
    uint[DIMY][DIMX] board = [[7,9,0, 0,0,0, 3,0,0],
    [0,0,0, 0,0,6, 9,0,0],
    [8,0,0, 0,3,0, 0,7,6],

    [0,0,0, 0,0,5, 0,0,2],
    [0,0,5, 4,1,8, 7,0,0],
    [4,0,0, 7,0,0, 0,0,0],

    [6,1,0, 0,9,0, 0,0,8],
    [0,0,2, 3,0,0, 0,0,0],
    [0,0,9, 0,0,0, 0,5,4]];
    */


    //Platinum Blond Sudoku
    uint[DIMY][DIMX] board = [[0,0,0, 0,0,0, 0,1,2],
    [0,0,0, 0,0,0, 0,0,3],
    [0,0,2, 3,0,0, 4,0,0],

    [0,0,1, 8,0,0, 0,0,5],
    [0,6,0, 0,7,0, 8,0,0],
    [0,0,0, 0,0,9, 0,0,0],

    [0,0,8, 5,0,0, 0,0,0],
    [9,0,0, 0,4,0, 5,0,0],
    [4,7,0, 0,0,6, 0,0,0]];


	sudoku a;
    foreach(i;0..DIMY)
        foreach(j;0..DIMX)
            if(board[i][j]) {
                a.s[i][j].value = board[i][j];
                bl(a, i, j);
            }

    a.output;
    a.solve;

	writeln("usecs: ", sw.peek.usecs, "\n");
    foreach(s;solved)
        s.output;
}

Hmm, sorry odd things have happened to the formatting. Visual D's spacing doesn't seem to work very well outside of itself.

solving sudoku's well too : http://dpaste.dzfl.pl/903e34b5
I have one question though, how can you make it find all possible solutions?

2012/8/16, Era Scarecrow <rtcvb32@yahoo.com>:
> On Thursday, 16 August 2012 at 01:05:20 UTC, Era Scarecrow wrote:
>> So far having it running it's found over 23k+ combinations after about 3 minutes.
>
>   Unless I introduced a bug... Now I'll have to speed it up to
> make sure and won't take an afternoon to calculate.
>

On 08/16/2012 03:56 AM, maarten van damme wrote:
> solving sudoku's well too : http://dpaste.dzfl.pl/903e34b5
> I have one question though, how can you make it find all possible solutions?
>

Keep on backtracking when you find one until there are no more
possibilities to explore. (i.e. get rid of the return value of 'fill')