www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Sudoku Py / C++11 / D?

reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Aug 14 2012
next sibling parent reply "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Tuesday, 14 August 2012 at 22:31:16 UTC, 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


  Not Golfed? I don't recognize that term. I don't see the python 
source off hand, but I don't understand python anyways.

  I've managed to make a full solver in about 187 lines (4.5k) in 
the last hour (although lacking a few unittests); It does 2 
methods to attempt to solve it (Only possible option & brute 
force). Unoptimized it takes 82 seconds with the hardest supplied 
puzzle; But when optimized it goes down to 12 seconds.
Aug 15 2012
next sibling parent Ed McCardell <edmccard hotmail.com> writes:
On 08/15/2012 03:01 AM, Era Scarecrow wrote:

   Not Golfed? I don't recognize that term. I don't see the python source
 off hand, but I don't understand python anyways.


It refers to "code golf", where you try to solve a problem with the 
smallest program possible (one-letter variable names, no whitespace, 
etc.) There are sudoku solvers in under 200 bytes in Perl and Python; a 
D version would just prove that we too can write code that looks like 
line noise.

--Ed
Aug 15 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Era Scarecrow:


 I don't see the python source off hand,


The original Python code:
http://norvig.com/sudopy.shtml

Bye,
bearophile
Aug 15 2012
prev sibling parent reply "ixid" <nuaccount gmail.com> writes:
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.
Aug 15 2012
next sibling parent reply "Era Scarecrow" <rtcvb32 yahoo.com> writes:
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.


  1400 seconds? Well my CPU is a quad-core 3.2Ghz, but it's not 
using threading so...

  I have made a C version a while back that solves any sudoku 
puzzle in 1/8th of a second. The code for that though was 
considerably longer and involved several forms of pattern 
matching and detecting how to solve the puzzle before it went to 
brute force as a last resort.

  Give me about 30 minutes, I'm going to clean the code up since 
several parts of it do rely on single character variables. I'll 
also add a little documentation so the 187 lines will likely 
expand to about 200, if I add all the actual unittests I need 
likely 250 lines.
Aug 15 2012
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, August 15, 2012 21:14:07 Era Scarecrow wrote:

 I have made a C version a while back that solves any sudoku
 puzzle in 1/8th of a second. The code for that though was
 considerably longer and involved several forms of pattern
 matching and detecting how to solve the puzzle before it went to
 brute force as a last resort.


Brute force is so fast that there's no really any point in trying to solve it 
any other way except for the challenge of doing so. I answered a question on 
this using D at codegolf.stackexchange.com a while back:

http://codegolf.stackexchange.com/questions/378/implement-a-brute-force-


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). It's at just over 150 
lines and could be much shorter if I really tried to properly golf it rather 
than just solve the problem.

- Jonathan M Davis
Aug 15 2012
next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Wednesday, 15 August 2012 at 20:28:19 UTC, Jonathan M Davis 
wrote:

 Brute force is so fast that there's no really any point in 
 trying to solve it any other way except for the challenge of 
 doing so. I answered a question on this using D at 
 codegolf.stackexchange.com a while back:


  


 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). It's at just over 150 lines 
 and could be much shorter if I really tried to properly golf it 
 rather than just solve the problem.


  Interesting... Against the same input that brute force only one 
succeeded in 2 seconds vs my 9-12. And on the puzzle supplied on 
the Page, about 250ms compared to mine at 400ms.

  If I add a few lines to remove the only real bottle-neck (cache 
result of 4 functions) I'm sure mine would easily out-perform 
that one; But I wasn't going for absolute speed and keeping 
things simpler.
Aug 15 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Aug 15 2012
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Aug 15 2012
prev sibling parent reply "Era Scarecrow" <rtcvb32 yahoo.com> writes:
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
Aug 15 2012
next sibling parent reply "ixid" <nuaccount gmail.com> writes:
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?
Aug 15 2012
parent reply "Era Scarecrow" <rtcvb32 yahoo.com> writes:
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.
Aug 15 2012
parent reply "Era Scarecrow" <rtcvb32 yahoo.com> writes:
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.
Aug 15 2012
next sibling parent reply "ixid" <nuaccount gmail.com> writes:
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;
}
Aug 15 2012
parent "ixid" <nuaccount gmail.com> writes:
Hmm, sorry odd things have happened to the formatting. Visual D's 
spacing doesn't seem to work very well outside of itself.
Aug 15 2012
prev sibling parent reply maarten van damme <maartenvd1994 gmail.com> writes:
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.
Aug 15 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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')
Aug 15 2012
parent reply maarten van damme <maartenvd1994 gmail.com> writes:
I've now ran in something odd. Using a slight variant from my program on
dpaste (can't upload modified version atm but changes are minimal) it takes
0.6 seconds to solve the hard puzzle the python version took 180 seconds
for. Yet on the last puzzle, the impossible one, python takes 1800 seconds
to figure out it's impossible yet mine takes over 3885 seconds. Where is
this slowdown coming from?
Aug 16 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 08/16/2012 09:52 PM, maarten van damme wrote:

 I've now ran in something odd. Using a slight variant from my program on
 dpaste (can't upload modified version atm but changes are minimal) it
 takes 0.6 seconds to solve the hard puzzle the python version took 180
 seconds for.


This is because the python version happened to choose an unlucky search
order. Sudoku is NP-complete after all, so it is not surprising that
programs have a bad worst case run time.


 Yet on the last puzzle, the impossible one, python takes
 1800 seconds to figure out it's impossible yet mine takes over 3885
 seconds. Where is this slowdown coming from?


This is because your specific solution is slow.

Mine takes <20ms on the 'hard' puzzle and ~13s on the impossible one.
(~2.4 GHZ intel x86_64 machine, with gdmd -O -release -inline 
-noboundscheck.)
There is a constant factor between those two solutions.
Aug 16 2012
parent reply maarten van damme <maartenvd1994 gmail.com> writes:
 This is because your specific solution is slow.

 Mine takes <20ms on the 'hard' puzzle and ~13s on the impossible one.
 (~2.4 GHZ intel x86_64 machine, with gdmd -O -release -inline


-noboundscheck.)

 There is a constant factor between those two solutions.


I've compiled it using dmd on my latitude e5500 which is not that fast so I
don't think it's that slow...

Besides, lets say mine is five times slower, 3000 seconds is still waaay to
much. When I'm back able to get my laptop to use my crapy data connection
I'll compare.

Do you have some optimization ideas by the way?
Aug 16 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 08/16/2012 11:51 PM, maarten van damme wrote:

  > This is because your specific solution is slow.
  >
  > Mine takes <20ms on the 'hard' puzzle and ~13s on the impossible one.
  > (~2.4 GHZ intel x86_64 machine, with gdmd -O -release -inline
 -noboundscheck.)
  > There is a constant factor between those two solutions.

 I've compiled it using dmd on my latitude e5500 which is not that fast
 so I don't think it's that slow...


Compiled and run in the same environment, your solution takes 0.26s on
the 'hard' one, whereas mine takes 0.0013s. Your solution takes ~1600s
on the impossible one whereas mine takes ~13s.


 Besides, lets say mine is five times slower,


Hard facts say that it is at around 100x-200x slower.


 3000 seconds is still waaay  to much.


Sounds reasonable to me.


 When I'm back able to get my laptop to use my crapy data
 connection I'll compare.

 Do you have some optimization ideas by the way?


First of all, getting rid of the dynamic allocations is low hanging fruit.

Then you'll have to reduce the number of times you recompute the same
information. Update/restore the possibilities array as you
update/restore the solution attempts. Do this for the whole board at
once and use a compact representation of possibilities.
Aug 16 2012
parent reply maarten van damme <maartenvd1994 gmail.com> writes:
great, going to play around with it tomorrow.
Caching the possibilities is going to look really ugly but you're
right, it's going to give quiet a boost in performance.

I'm also going to format your source code a bit more and see if I can
follow it's logic as it seems to be way more efficient. (although
compilation is failing here, I'm running dmd 2.059 and it gives "can't
stride on chunks!(short))

would using short or bytes increase performance compared to integers?
if so, why did you use shorts instead of bytes?

2012/8/17, Timon Gehr <timon.gehr gmx.ch>:

 On 08/16/2012 11:51 PM, maarten van damme wrote:

  > This is because your specific solution is slow.
  >
  > Mine takes <20ms on the 'hard' puzzle and ~13s on the impossible one.
  > (~2.4 GHZ intel x86_64 machine, with gdmd -O -release -inline
 -noboundscheck.)
  > There is a constant factor between those two solutions.

 I've compiled it using dmd on my latitude e5500 which is not that fast
 so I don't think it's that slow...


 Compiled and run in the same environment, your solution takes 0.26s on
 the 'hard' one, whereas mine takes 0.0013s. Your solution takes ~1600s
 on the impossible one whereas mine takes ~13s.


 Besides, lets say mine is five times slower,


 Hard facts say that it is at around 100x-200x slower.


 3000 seconds is still waaay  to much.


 Sounds reasonable to me.


 When I'm back able to get my laptop to use my crapy data
 connection I'll compare.

 Do you have some optimization ideas by the way?


 First of all, getting rid of the dynamic allocations is low hanging fruit.

 Then you'll have to reduce the number of times you recompute the same
 information. Update/restore the possibilities array as you
 update/restore the solution attempts. Do this for the whole board at
 once and use a compact representation of possibilities.
Aug 16 2012
next sibling parent reply "Chris Cain" <clcain uncg.edu> writes:
On Thursday, 16 August 2012 at 23:13:56 UTC, maarten van damme 
wrote:

 great, going to play around with it tomorrow.
 Caching the possibilities is going to look really ugly but 
 you're
 right, it's going to give quiet a boost in performance.

 I'm also going to format your source code a bit more and see if 
 I can
 follow it's logic as it seems to be way more efficient. 
 (although
 compilation is failing here, I'm running dmd 2.059 and it gives 
 "can't
 stride on chunks!(short))

 would using short or bytes increase performance compared to 
 integers?
 if so, why did you use shorts instead of bytes?


Gonna chime in a bit here:

There's a lot of factors at play when deciding to use shorts vs 
bytes vs native-sized ints. The best way to decide is to time all 
of them and see which works best overall.

With caching on a larger problem, I'd guess that the smaller you 
go, the better. The reason is that you run the risk of your data 
getting large enough that it can't all fit in the L2 cache and 
waiting for information to come from memory takes forever 
(comparatively speaking).

Also, I just looked at your solution (not Mr. Gehr's solution), 
but it looks like you could approach this much more efficiently.

It seems like you're storing a lot of information in arrays of 
ints. At least some of that could be stored in a bitmap/bitset 
(http://en.wikipedia.org/wiki/Bit_array) and give you 
significantly better memory efficiency. Array!bool in 
std.container will actually do the correct thing and store things 
like a bitset, so you don't necessarily have to implement your 
own (however, I think that it stores it in an int when you could 
use a short to hold 1-9 ... but it's not enough to really worry 
about).
Aug 16 2012
parent reply maarten van damme <maartenvd1994 gmail.com> writes:
2012/8/17, Chris Cain <clcain uncg.edu>:

 Gonna chime in a bit here:

 There's a lot of factors at play when deciding to use shorts vs
 bytes vs native-sized ints. The best way to decide is to time all
 of them and see which works best overall.

 With caching on a larger problem, I'd guess that the smaller you
 go, the better. The reason is that you run the risk of your data
 getting large enough that it can't all fit in the L2 cache and
 waiting for information to come from memory takes forever
 (comparatively speaking).

 Also, I just looked at your solution (not Mr. Gehr's solution),
 but it looks like you could approach this much more efficiently.

 It seems like you're storing a lot of information in arrays of
 ints. At least some of that could be stored in a bitmap/bitset
 (http://en.wikipedia.org/wiki/Bit_array) and give you
 significantly better memory efficiency. Array!bool in
 std.container will actually do the correct thing and store things
 like a bitset, so you don't necessarily have to implement your
 own (however, I think that it stores it in an int when you could
 use a short to hold 1-9 ... but it's not enough to really worry
 about).


I've been using my phone the last few days to check my emails and
overlooked this message. I've never heard about std.container but this
could indeed be a more efficient solution. I'm now storing a lot in
bytes but that's still 8 times too much :)


 Try this:
 http://dpaste.dzfl.pl/23b1b6e2


Thank you very much, this makes everything more clearer. I'm not very
familiar with binary operators so the comments help out a lot.
Would you mind it if I shamelessly copy your solution of using shorts
to store possibilities in?

I'm also a bit confused. How come the int's you change from a square
passed from squ are stilled referenced to the original array? I
thought it lost that reference as soon as you did any operations (like
concenating) on it?


 Was that sarcasm? My own code only uses copying when it's working in the next
section of brute force, otherwise it's all referenced.


No, that wasn't sarastic. If you look at my last code you see that I
"compose" the squares using something like [....] ~ [.....] ~ [.....]
Using a foreach loop and copying the values was 10 times faster...


  I only use exceptions twice and both when it would be unable to find a
solution; I suppose I can try putting nothrow on everything and return a bool
if it had an error for solving, or when it had to, inside a structure. Mmmm...
I'll give it a try.


Yes but when your solver reaches a solution that is wrong, you get a
whole "branch" of numbers falling of, all throwing a "broken sudoku"
exception. It will rarely be called once.


 Not normal but it can be arranged. :p


But I used it in my getRegion code where I do simple calculations on
the contents of that array. It is slower there...
Aug 21 2012
next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Tuesday, 21 August 2012 at 15:55:08 UTC, maarten van damme 
wrote:

 Thank you very much, this makes everything more clearer. I'm 
 not very familiar with binary operators so the comments help 
 out a lot. Would you mind it if I shamelessly copy your 
 solution of using shorts to store possibilities in?


  Binary operators are fun :) Once you get the hang of it you know 
exactly what you're doing. Think of AND = Keep only, OR = Set, 
Xor = switch state. so.

  AND &
  source  0 0 1 1
  data    0 1 0 1
  result  0 0 0 1

  OR |
  source  0 0 1 1
  data    0 1 0 1
  result  0 1 1 1

  Xor ^
  source  0 0 1 1
  data    0 1 0 1
  result  0 1 1 0


 Was that sarcasm? My own code only uses copying when it's 
 working in the next section of brute force, otherwise it's all 
 referenced.





 No, that wasn't sarastic. If you look at my last code you see 
 that I "compose" the squares using something like [....] ~ 
 [.....] ~ [.....] Using a foreach loop and copying the values 
 was 10 times faster...


  Curious. With fixed array sizes it should do a bulk memory copy, 
unless you are going from static/fixed to dynamic. Also curious 
is in my code it allowed me to do a forced struct copy (move?) 
when I found a success and just copied the result to the current 
structure. I'll post my two revisions up later.


 I only use exceptions twice and both when it would be unable 
 to find a solution; I suppose I can try putting nothrow on 
 everything and return a bool if it had an error for solving, 
 or when it had to, inside a structure. Mmmm... I'll give it a 
 try.





 Yes but when your solver reaches a solution that is wrong, you 
 get a whole "branch" of numbers falling of, all throwing a 
 "broken sudoku" exception. It will rarely be called once.


  True. I already tried removing it, and curiously enough the code 
performs 10x-200x faster. Except all my debugging statements now 
fail since they aren't nothrow :P


 Not normal but it can be arranged. :p


 But I used it in my getRegion code where I do simple 
 calculations on the contents of that array. It is slower 
 there...
Aug 21 2012
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 08/21/2012 05:52 PM, maarten van damme wrote:

 On 08/20/2012 11:49 PM, Timon Gehr wrote:> On 08/20/2012 10:43 PM, 




maarten van damme wrote:

 Still it comes nowhere near beating timons solution. Is the logic of
 that documented somewhere because I don't understand it.


 Try this:
 http://dpaste.dzfl.pl/23b1b6e2


 Thank you very much, this makes everything more clearer. I'm not very
 familiar with binary operators so the comments help out a lot.
 Would you mind it if I shamelessly copy your solution of using shorts
 to store possibilities in?


Not at all.


 I'm also a bit confused. How come the int's you change from a square
 passed from squ are stilled referenced to the original array? I
 thought it lost that reference as soon as you did any operations (like
 concenating) on it?


The used ranges just express patterns of iteration. They replace manual
for-loops. The data source has assignable elements, and the relevant
range operations in Phobos all propagate this capability to their
result.
Aug 21 2012
parent reply maarten van damme <maartenvd1994 gmail.com> writes:
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.

I've probably violated every D guideline concerning the use of static,
pure, nothrow,... but it works perfectly :)
It does fail to compile on dpaste, I have no idea why. It does compile
on my machine though...

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

2012/8/21, Timon Gehr <timon.gehr gmx.ch>:

 On 08/21/2012 05:52 PM, maarten van damme wrote:

 On 08/20/2012 11:49 PM, Timon Gehr wrote:> On 08/20/2012 10:43 PM,




 maarten van damme wrote:

 Still it comes nowhere near beating timons solution. Is the logic of
 that documented somewhere because I don't understand it.


 Try this:
 http://dpaste.dzfl.pl/23b1b6e2


 Thank you very much, this makes everything more clearer. I'm not very
 familiar with binary operators so the comments help out a lot.
 Would you mind it if I shamelessly copy your solution of using shorts
 to store possibilities in?


 Not at all.


 I'm also a bit confused. How come the int's you change from a square
 passed from squ are stilled referenced to the original array? I
 thought it lost that reference as soon as you did any operations (like
 concenating) on it?


 The used ranges just express patterns of iteration. They replace manual
 for-loops. The data source has assignable elements, and the relevant
 range operations in Phobos all propagate this capability to their
 result.
Aug 24 2012
next sibling parent "Chris Cain" <clcain uncg.edu> writes:
On Friday, 24 August 2012 at 19:32:53 UTC, 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.

 I've probably violated every D guideline concerning the use of 
 static,
 pure, nothrow,... but it works perfectly :)


Nice job! I looked at it quickly, but it seems like a good 
solution.


 It does fail to compile on dpaste, I have no idea why. It does 
 compile
 on my machine though...

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


It's because dpaste is compiling for 64-bit and you're compiling 
it for 32-bit. length is a size_t which is uint in 32-bit 
environments and ulong in 64-bit. A long/ulong isn't implicitly 
convertable to int/uint in D. On line 119, either you need to use 
an explicit cast or you can change the type of curLength to long, 
ulong, or size_t.

In this case, since you expect curLength to be fairly small (much 
smaller than an int), I'd just stick a cast in there. Though, in 
general, changing the type to a size_t is better.
Aug 24 2012
prev sibling next sibling parent reply "nazriel" <spam dzfl.pl> writes:
On Friday, 24 August 2012 at 19:32:53 UTC, 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.

 I've probably violated every D guideline concerning the use of 
 static,
 pure, nothrow,... but it works perfectly :)
 It does fail to compile on dpaste, I have no idea why. It does 
 compile
 on my machine though...

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

 2012/8/21, Timon Gehr <timon.gehr gmx.ch>:

 On 08/21/2012 05:52 PM, maarten van damme wrote:

 On 08/20/2012 11:49 PM, Timon Gehr wrote:> On 08/20/2012 
 10:43 PM,




 maarten van damme wrote:

 Still it comes nowhere near beating timons solution. Is the 
 logic of
 that documented somewhere because I don't understand it.


 Try this:
 http://dpaste.dzfl.pl/23b1b6e2


 Thank you very much, this makes everything more clearer. I'm 
 not very
 familiar with binary operators so the comments help out a lot.
 Would you mind it if I shamelessly copy your solution of 
 using shorts
 to store possibilities in?


 Not at all.


 I'm also a bit confused. How come the int's you change from a 
 square
 passed from squ are stilled referenced to the original array? 
 I
 thought it lost that reference as soon as you did any 
 operations (like
 concenating) on it?


 The used ranges just express patterns of iteration. They 
 replace manual
 for-loops. The data source has assignable elements, and the 
 relevant
 range operations in Phobos all propagate this capability to 
 their
 result.




Your code is 32bitish, while you picked 64bit mode on dpaste.

Here's your code with m32: http://dpaste.dzfl.pl/b4a01f57
Working nice!
Aug 24 2012
next sibling parent maarten van damme <maartenvd1994 gmail.com> writes:
Thank you very much.
I changed line 119 to an explicit cast to int and removed an unneeded
cast at line 63.
It now happily compiles with 64bit mode : http://dpaste.dzfl.pl/63666f07.
It's kind off odd though that compiling with -inline seems to slow it
a bit down.

I'm unsure if searching for the field with the least possibilities was
a smart move because now I have to carry that "taken" array through
all my functions and optimize has to check the whole sudoku instead of
a slice. (come to think of it, taken should've been named occupied)

Still, I'm really pleased with the results. I should write a
prettyPrint method that prints sudoku's in a prettier format and
returns the solution instead of the shorts containing the solutions
hidden in bitfields :)
Aug 24 2012
prev sibling parent maarten van damme <maartenvd1994 gmail.com> writes:
 I'm unsure if searching for the field with the least possibilities was
 a smart move because now I have to carry that "taken" array through
 all my functions and optimize has to check the whole sudoku instead of
 a slice. (come to think of it, taken should've been named occupied)


I take that back, having tried it out, it is more then 3 times slower...
Aug 24 2012
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Aug 24 2012
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 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
Aug 24 2012
prev sibling next sibling parent reply maarten van damme <maartenvd1994 gmail.com> writes:
 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.
Aug 24 2012
parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Aug 24 2012
prev sibling parent maarten van damme <maartenvd1994 gmail.com> writes:
and everythingPossible should also be changed to something ala 2 ^(side) -1
Aug 24 2012
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
Aug 24 2012
next sibling parent reply maarten van damme <maartenvd1994 gmail.com> writes:
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
Aug 24 2012
parent reply "Chris Cain" <clcain uncg.edu> writes:
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. 
:)
Aug 24 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 08/25/2012 02:51 AM, Chris Cain wrote:

 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. :)


FWIW both mine and Maarten's solution require a trivial amount of time
to solve it.
Aug 24 2012
parent reply "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Saturday, 25 August 2012 at 00:51:23 UTC, Chris Cain wrote:

 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.


  Is most likely. What would you do, have multiple threads all 
solving it until one came with the fastest solution and then fix 
it back to how it should be? It would work...

  As a test I've taken the puzzle and converted it, normally I 
gave it up after some 30 seconds but flipped it was 2 seconds.

As the picture puzzle shows:
..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9

Flipped:
....4...9..2.1....5......73.9.........4...1.....5.7.....1.2.........3.85.........

  Strange, flipping it various ways and connecting them comes up 
with an interesting patterns.


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


  Adding another level of possibilities removal before going to 
brute force can definitely do a lot.


On Saturday, 25 August 2012 at 01:00:04 UTC, Timon Gehr wrote:

 FWIW both mine and Maarten's solution require a trivial amount 
 of time to solve it.


  Same for my C version of the solver. But that's not really the 
topic here :P
Aug 24 2012
next sibling parent maarten van damme <maartenvd1994 gmail.com> writes:
The puzzle unflipped is extra hard as the solution to the first row is
987 654 321. Come to think of it, one could add a new function "flip"
that mutates the sudoku according to well known rules and maybe
something like unflip for when the sudoku was finnished.

New techniques could certainly be added (like single candidate and
naked pairs) without too much overhead so they might just pay off,
certainly on the impossible puzzle.

Maybe I could also pre-calculate all rows, collumns and squares and
store them in int pointer arrays. This way things could become even
faster. Would it be possible to do something like that in ctfe?
Aug 25 2012
prev sibling parent reply maarten van damme <maartenvd1994 gmail.com> writes:
While trying to use Array!bool I noticed this:
import std.container;

void main(){
	Array!bool test;
	test[0]=false;
}
gives an assertion failure without any information.
Also, why on earth can't I instantiate array!bool with a given length?
Aug 25 2012
parent reply "Chris Cain" <clcain uncg.edu> writes:
On Saturday, 25 August 2012 at 13:33:27 UTC, maarten van damme 
wrote:

 While trying to use Array!bool I noticed this:
 import std.container;

 void main(){
 	Array!bool test;
 	test[0]=false;
 }
 gives an assertion failure without any information.
 Also, why on earth can't I instantiate array!bool with a given 
 length?


import std.container, std.stdio;

void main() {
     Array!bool myArr;
     myArr.length = 9; // set length before use
     myArr[0] = true;
     myArr[5] = true;
     writeln("myArr = ", myArr[]); // myArr = [true, false, false, 
false, false, true, false, false, false]
}
Aug 25 2012
parent reply maarten van damme <maartenvd1994 gmail.com> writes:
Ok, I'll try with Array!bool instead of bool.

I now renamed a few things, added a few extra checks and generalized
bearophiles modifications. Now the only thing keeping it from solving
25 x 25 size sudoku's is the way I input numbers :)

However, I now have a very strange issue. Compiling with dmd -O
-release -inline works but compiling with dmd -O -release -inline
-noboundscheck gives the following compile time error:

Assertion failure: 'semanticstarted == 2' on line 829 in file 'module.c'

abnormal program termination

Code is at http://dpaste.dzfl.pl/41a01039

I can't test on gdc because compilation of the aur sources failed on
my laptop and I'm to lazy to try and determine the source of the error
:p

Also, why do you use enum's and not consts ?
Aug 25 2012
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
maarten van damme:


 Ok, I'll try with Array!bool instead of bool.


There is also a BitVector, but it's heap-allocated, so probably
it's not a good idea. A ucent used as bit vector on a 64 bit
system is maybe the best way to implement that :-) But we don't
have ucents yet.

So maybe you have to implement your own bitvector with an uint[N]
where N is the minimal possible, it's 3 for the 9*9 Sudoku.



 I now renamed a few things, added a few extra checks and 
 generalized
 bearophiles modifications. Now the only thing keeping it from 
 solving
 25 x 25 size sudoku's is the way I input numbers :)

 However, I now have a very strange issue. Compiling with dmd -O
 -release -inline works but compiling with dmd -O -release 
 -inline
 -noboundscheck gives the following compile time error:

 Assertion failure: 'semanticstarted == 2' on line 829 in file 
 'module.c'

 abnormal program termination


Congratulations, you have found a compiler bug. I have found
maybe one hundred of those. Please minimize the code and submit
it to Bugzilla :-)



 Code is at http://dpaste.dzfl.pl/41a01039


Replacing side and size with boardSide and boardSize is a good
idea. But the two variables differ only by one char, so there's
space for further improvements.

The code contains:

// But, atention, an ushort is only 16 bits. Change this to uint
to be able to solve 25 x 25 sudoku's (http://dlang.org/type.html)
alias ushort SudokuCell; // contains only values in (0,
everythingPossible)

In D there are smarter ways to do that.
Generally in all your programs try to move as much semantics as
possible from comments to code.

In this case this means using static ifs to choose ushort or uint
(or give a compile-time error) to choose the best SudokuCell
type. There are fancier ways to do it, but this is simple and
seems OK, but I have not tested it:

// SudokuCell contains only values in (0, everythingPossible) (a
RangedValue when available)
static if (boardSide <= short.sizeof * 8) {
      alias ushort SudokuCell;
} else static if (boardSide <= uint.sizeof * 8) {
      alias uint SudokuCell;
} else static if (boardSide <= ulong.sizeof * 8) {
      alias ulong SudokuCell;
} else
      static assert(false, "");


Eventually a SudokuCell is meant to be replaced by a ranged
value, something like:

static if (boardSide <= short.sizeof * 8) {
      alias RangedValue!(ushort, 0, everythingPossible+1)
SudokuCell;
} else static if...

This moves another comment to code, and avoids some potential
run-time bugs in the code, because it forbids you to assign a
value outside that range (in non-release mode) to a Sudoku cell.



 Also, why do you use enum's and not consts ?


If you assign a global value like an int, using const or enum
produces the same binary. But generally enum conveys better that
meaning, because in D enum means that it's known at compile-time,
while const is for run-time constants too. Often while you code
it's better to use the tightest semantics available :-)
You just have to be careful with enum arrays, because they cause
extra allocations.

Bye,
bearophile
Aug 25 2012
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
struct MaxArray(T, size_t maxLen) {
...
     void opAssign(T[] a) {

I forgot ==>

struct MaxArray(T, size_t maxLen) {
...
     void opAssign(T[] a) pure nothrow {

Bye,
bearophile
Aug 25 2012
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
And now your backtrack() function too can be nothrow :-)

Bye,
bearophile
Aug 25 2012
parent maarten van damme <maartenvd1994 gmail.com> writes:
Ok, thank you very much with your help :)
Aug 25 2012
prev sibling parent maarten van damme <maartenvd1994 gmail.com> writes:
 Congratulations, you have found a compiler bug. I have found
 maybe one hundred of those. Please minimize the code and submit
 it to Bugzilla :-)


Oh, but try playing around with static and dynamic arrays. You'll be
able to find plenty more :p

By changing both squareWidth and squareHeight to 5, we get an optlink
crash (those are more rare, aren't they?)

I've made one of my last modifications allowing M x N sudoku's. I
think I'm going to place the result on github or something. It was a
great experience :)

One last thing would be to try and move generateBitsetCache to CTFE
(if that's even possible).

Anyway, code can be checked out at http://dpaste.dzfl.pl/879b0973
(along with the pretty compiler error at the end).

I'm going to try dustmite out (always wanted to do that) and see if it
can reduce my testcase (no previous experience).
Aug 25 2012
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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).
Aug 24 2012
parent Timon Gehr <timon.gehr gmx.ch> writes:
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
Aug 24 2012
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 08/17/2012 01:13 AM, maarten van damme wrote:

 great, going to play around with it tomorrow.
 Caching the possibilities is going to look really ugly but you're
 right, it's going to give quiet a boost in performance.

 I'm also going to format your source code a bit more and see if I can
 follow it's logic as it seems to be way more efficient. (although
 compilation is failing here, I'm running dmd 2.059 and it gives "can't
 stride on chunks!(short))


Works for me both with DMD 2.060 and GDC with the 2.059 front end.


 would using short or bytes increase performance compared to integers?


Using less memory sometimes increases performance, but here it is not 
significant.


 if so, why did you use shorts instead of bytes?


Because I need 9 bits per entry to keep track of all the combinations
of possibilities.
Aug 16 2012
next sibling parent reply maarten van damme <maartenvd1994 gmail.com> writes:
Great, i tried to get rid of the dynamic array "possibilities" by
representing it using a static array of bools. This approach made it 4
times faster :)

When i have a solid wifi connection I'm going to install dmd 2.60 to
compile timon's code. In the meantime I've started beautifying the source
so i can follow the logic.

I still have a few questions however:
- era claims his code takes 12 seconds on the hardest supplied puzzle yet
it enters an infinite loop when the puzzle isnt solvable. Is he talking
about a different puzzle?

-is it normal that const ref is slower then ref?

- in an effort of trying to make the program reuse the same memory I've
moved some temporary variables outside the function but the program became
slower, how can this be?

- in a few hours i'll upload my newest source. I cant find that much stupid
design decisions anymore that cause slowdowns yet it keeps lagging behind
by an enormous amount to timon's solver. What's that much more efficient in
his solution?
Aug 19 2012
next sibling parent reply "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Sunday, 19 August 2012 at 09:39:53 UTC, maarten van damme 
wrote:

 Great, I tried to get rid of the dynamic array "possibilities" 
 by representing it using a static array of bools. This approach 
 made it 4 times faster :)

 When I have a solid wifi connection I'm going to install dmd 
 2.60 to compile timon's code. In the meantime I've started 
 beautifying the source so I can follow the logic.

 I still have a few questions however:
 - era claims his code takes 12 seconds on the hardest supplied 
 puzzle yet it enters an infinite loop when the puzzle isn't 
 solvable. Is he talking about a different puzzle?


The one supplied: 
.....6....59.....82....8....45........3........6..3.54...325..6..................

  The infinite loop is likely the brute force actually brute 
forcing. I'm sure most other programs will lock up too until they 
can prove it won't work. I can re-check my code, but if it can't 
solve it it should tell you as it throws an exception. On ones 
filled with a lot more numbers it will take a lot less time.


 -is it normal that const ref is slower then ref?


  Ummm... No? I don't see why it would be.
Aug 19 2012
parent reply maarten van damme <maartenvd1994 gmail.com> writes:
The infinite loop was my mistake. I was looking at your outer while loop
but because you use exceptions instead of return values it indeed throws an
exception, my bad :)

By replacing ref by const ref my program slowed down (looked over a period
of 10_000 runs). Not considerably but noticeable. Compiled with -release
-noboundscheck -O -inline. Anyone else experiencing the same?

Is copying a static arrays cheaper then recalculating the lovation of
collumns and squares btw?
Aug 19 2012
parent reply "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Sunday, 19 August 2012 at 21:24:26 UTC, maarten van damme 
wrote:

 The infinite loop was my mistake. I was looking at your outer 
 while loop but because you use exceptions instead of return 
 values it indeed throws an exception, my bad :)


  I have a revised version that only does 2 calls for the main 
solve now, but that's not that important.


 By replacing ref by const ref my program slowed down (looked 
 over a period of 10_000 runs). Not considerably but noticeable. 
 Compiled with -release -noboundscheck -O -inline. Anyone else 
 experiencing the same?



 Is copying a static arrays cheaper then recalculating the 
 lovation of collumns and squares btw?


  Are you using ref with it like int[9][9]? Or int[][]? It may be 
making extra calculations but i couldn't be entirely sure.

  Something to try, perhaps wrap the array into a struct and ref 
the struct. I did that in my revision (which also keeps track of 
possible choices within the struct).
Aug 19 2012
parent reply maarten van damme <maartenvd1994 gmail.com> writes:
I'm using a static array.

I'm hesitating though if I should store possibilities in a precalculated
array or calculate them in-place. If i precalculate the possibilities i'd
have to copy them over and over so i don't know if it's smart.

Going even further I could even store a filled-in value as an array with
one possibilities...
Aug 19 2012
parent reply "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Monday, 20 August 2012 at 00:13:41 UTC, maarten van damme 
wrote:

 I'm using a static array.


  Good good..


 I'm hesitating though if I should store possibilities in a 
 precalculated array or calculate them in-place. If I 
 precalculate the possibilities I'd have to copy them over and 
 over so I don't know if it's smart.


  Depends. Do you plan on doing more than brute force? Having it 
bulk copy them may not be that bad if it's all in one place, and 
if you do it like that you have all the combinations that carry 
forward to the next level and if you back out it undoes them all 
automatically.

  In my updated code it gets it done in about 5 seconds compared 
to 12. To get it even faster I would have to implement a third 
algorithm to help reduce possibilities, the stored results then 
become a must compared to on-the-fly.


 Going even further I could even store a filled-in value as an 
 array with one possibilities...


  As long as you can tell it apart for it to work, that's up to 
you.
Aug 19 2012
parent reply maarten van damme <maartenvd1994 gmail.com> writes:
   Depends. Do you plan on doing more than brute force? Having it
 bulk copy them may not be that bad if it's all in one place, and
 if you do it like that you have all the combinations that carry
 forward to the next level and if you back out it undoes them all
 automatically.


No, I think doing something else then brute-force would simply be a
waste of time (except for finding singles in which case you don't need
to use a brute force solver right?)
These are of course speculations, I'm not sure.


 Going even further I could even store a filled-in value as an
 array with one possibilities...


   As long as you can tell it apart for it to work, that's up to
 you.


yes, that is indeed going to be the problem ...
Aug 19 2012
parent reply "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Monday, 20 August 2012 at 01:29:06 UTC, maarten van damme 
wrote:

 Depends. Do you plan on doing more than brute force? Having it 
 bulk copy them may not be that bad if it's all in one place, 
 and if you do it like that you have all the combinations that 
 carry forward to the next level and if you back out it undoes 
 them all automatically.


 No, I think doing something else then brute-force would simply 
 be a waste of time (except for finding singles in which case 
 you don't need to use a brute force solver right?) These are of 
 course speculations, I'm not sure.


  Not true. Brute force will get the job done, but it's slow and 
bulky. By using other techniques can eliminate thousands, 
millions, or billions of cycles through simply by removing a few 
possible numbers.

  I've seen on the hard level that the brute force recursive code 
went some 20 levels deep (at one point). If it did all 
combinations of 9^20 than you'd get potentially 
12,157,665,459,056,928,801 combinations it may have to brute 
force. That can take a very very very long time. With that in 
mind, brute force should likely be a last resort if you are doing 
other algorithms.

  I've mentioned before I have an old C version of a sudoku 
solver; It can solve any solvable puzzle very quickly, the hard 
one on the best run is 1/5th of a second.

  Here's a compiled binary of the C version.

  http://rtcvb32.herobo.com/SudokuSolver.zip



 Going even further I could even store a filled-in value as an 
 array with one possibilities...


 As long as you can tell it apart for it to work, that's up to 
 you.


 yes, that is indeed going to be the problem ...


Here's what I've done recently. I've made a grid something like 
ubyte[10][9][9]. This represents the grid and all combinations 
needed for it. This way if [0] is non-zero you know it has an 
answer, otherwise the rest are which are potentially possible.
Aug 19 2012
parent reply maarten van damme <maartenvd1994 gmail.com> writes:
  Not true. Brute force will get the job done, but it's slow and bulky. By


using other techniques can eliminate thousands, millions, or billions of
cycles through simply by removing a few possible numbers.


Yes, but these techniques have a drawback : they are not garantueed to find
solutions yet they are garantueed to increase the time a run takes.

I'm still unsure if it would be worth carrying over that possibilities
array. I'm going to implement auto-solving of single candidates and see how
big the performance hit/gain is.


  I've seen on the hard level that the brute force recursive code went


some 20 levels deep (at one point). If it did all combinations of 9^20 than
you'd get potentially 12,157,665,459,056,928,801 combinations it may have
to brute force. That can take a very very very long time. With that in
mind, brute force should likely be a last resort if you are doing other
algorithms.


Yes but I only test allowed numbers so if of those 20 combinations we need
5 fours, 3 nines, 4 twos and 8 ones, the possibilities to test are only
3491888400 which is reasonable for a pc :)


 Here's what I've done recently. I've made a grid something like


ubyte[10][9][9]. This represents the grid and all combinations needed for
it. This way if [0] is non-zero you know it has an answer, otherwise the
rest are which are potentially possible.

That is indeed a really smart approach, I'll try that.

By optimizing a bit more (who would've thought that a for loop copying
values one by one is way faster then some slice magic?) I was able to make
my program 3 times faster. Now it can solve an empty sudoku in 0.05 ms and
solve the hard sudoku in 0.06s. My sudoku generator for valid sudoku
solution now runs at 13000 sudokus a second.

Still it comes nowhere near beating timons solution. Is the logic of that
documented somewhere because I don't understand it.

And vera, why are you using exceptions instead of return values? I think
it's slowing your solver down considerably.



 Aug 20 2012



 next sibling parent  Timon Gehr <timon.gehr gmx.ch>  writes:


On 08/20/2012 10:43 PM, maarten van damme wrote:

 Still it comes nowhere near beating timons solution. Is the logic of
 that documented somewhere because I don't understand it.


Try this:
http://dpaste.dzfl.pl/23b1b6e2



 Aug 20 2012



prev sibling next sibling parent  "Era Scarecrow" <rtcvb32 yahoo.com>  writes:


On Monday, 20 August 2012 at 20:43:54 UTC, maarten van damme 
wrote:

 Yes, but these techniques have a drawback : they are not 
 guaranteed to find solutions yet they are guaranteed to 
 increase the time a run takes.


  The extra time it takes via a planned route rather than brute 
forcing is well worth the effort. Besides, they mostly make it 
more possible for the one-one-possible matches to be found much 
faster and safely.

  In my tests with the C version (that was written 6 years ago?) 
each time I added an extra algorithmn to remove dead 
possibilities, it sped the code up by a factor of 3 or more.


 I'm still unsure if it would be worth carrying over that 
 possibilities array. I'm going to implement auto-solving of 
 single candidates and see how big the performance hit/gain is.



 Yes but I only test allowed numbers so if of those 20 
 combinations we need 5 fours, 3 nines, 4 twos and 8 ones, the 
 possibilities to test are only 3491888400 which is reasonable 
 for a pc :)


  Indeed. My code only does that too, but it's still alot of 
possibilities.


 That is indeed a really smart approach, I'll try that.

 By optimizing a bit more (who would've thought that a for loop 
 copying values one by one is way faster then some slice magic?) 
 I was able to make my program 3 times faster. Now it can solve 
 an empty sudoku in 0.05 ms and solve the hard sudoku in 0.06s. 
 My sudoku generator for valid sudoku solution now runs at 13000 
 sudokus a second.


  Was that sarcasm? My own code only uses copying when it's 
working in the next section of brute force, otherwise it's all 
referenced.


 And vera, why are you using exceptions instead of return 
 values? I think it's slowing your solver down considerably.


  I only use exceptions twice and both when it would be unable to 
find a solution; I suppose I can try putting nothrow on 
everything and return a bool if it had an error for solving, or 
when it had to, inside a structure. Mmmm... I'll give it a try.

  This is actually one of the first time's I'm actually using 
exceptions.



 Aug 20 2012



prev sibling  parent reply "Era Scarecrow" <rtcvb32 yahoo.com>  writes:


On Monday, 20 August 2012 at 20:43:54 UTC, maarten van damme 
wrote:


 And Vera, why are you using exceptions instead of return 
 values? I think it's slowing your solver down considerably.


  Wow... Just Wow...

  Optimized I had the code at 5 seconds in my recently updated 
format, however now it increased to 31 seconds.  That makes it 
6-7 times slower by not using the two potential exceptions.



 Aug 20 2012



  parent  "Era Scarecrow" <rtcvb32 yahoo.com>  writes:


On Monday, 20 August 2012 at 23:59:44 UTC, Era Scarecrow wrote:

 Optimized I had the code at 5 seconds in my recently updated 
 format, however now it increased to 31 seconds.  That makes it 
 6-7 times slower by not using the two potential exceptions.


  Correction, bug in my code. That dropped it to 300ms. Once 
again, Pleasantly Wow... :P



 Aug 20 2012



prev sibling  parent  =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com>  writes:


On 08/19/2012 02:39 AM, maarten van damme wrote:


 -is it normal that const ref is slower then ref?


Not normal but it can be arranged. :p

import std.stdio;
import core.thread;

struct S
{
     void foo()
     {}

     void foo() const
     {
         Thread.sleep(dur!("seconds")(3));
     }
}

void takes_ref(ref S s)
{
     s.foo();
}

void takes_const_ref(const ref S s)
{
     s.foo();
}

void main()
{
     auto s = S();
     takes_ref(s);
     takes_const_ref(s);
}

Ali



 Aug 20 2012



prev sibling  parent  maarten van damme <maartenvd1994 gmail.com>  writes:


my code is located at http://dpaste.dzfl.pl/93cd5f45

2012/8/19, maarten van damme <maartenvd1994 gmail.com>:

 Great, i tried to get rid of the dynamic array "possibilities" by
 representing it using a static array of bools. This approach made it 4
 times faster :)

 When i have a solid wifi connection I'm going to install dmd 2.60 to
 compile timon's code. In the meantime I've started beautifying the source
 so i can follow the logic.

 I still have a few questions however:
 - era claims his code takes 12 seconds on the hardest supplied puzzle yet
 it enters an infinite loop when the puzzle isnt solvable. Is he talking
 about a different puzzle?

 -is it normal that const ref is slower then ref?

 - in an effort of trying to make the program reuse the same memory I've
 moved some temporary variables outside the function but the program became
 slower, how can this be?

 - in a few hours i'll upload my newest source. I cant find that much stupid
 design decisions anymore that cause slowdowns yet it keeps lagging behind
 by an enormous amount to timon's solver. What's that much more efficient in
 his solution?





 Aug 19 2012



prev sibling  parent  Era Scarecrow <rtcvb32 yahoo.com>  writes:


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


  While an old thread, I decided to try a different approach to 
sudoku solving. In no way is this better, just a different 
approach. At 200 lines (needs some heavy unittests added, but 
appears to work).

  Using a sorting method to solve the puzzle. The idea is to take 
your puzzle, sort it by weight (how many possible numbers) and 
only take guesses with the smallest number of combinations 
possible, meaning any puzzle with 1 solution won't take long. The 
idea behind this method is to ignore combinations that might 
never come up; Afterall if you have a block with 2 possibilities, 
why start brute forcing the one with 7? Fewer wasted cycles. Yes 
it still uses brute force and built-in backtracking (and also 
outputs all combinations of a solution).

  Trying the REALLY REALLY hard one from before? (17 numbers) 
Well... I had it run in the background for a few hours, and got 
69,555,823 answers before the output (610Mb compressed, 11,067Mb 
uncompressed) simply filled up the free space on my ramdrive thus 
crashing the program.



 May 25 2017



prev sibling next sibling parent  "Chris Nicholson-Sauls" <ibisbasenji gmail.com>  writes:


On Tuesday, 14 August 2012 at 22:31:16 UTC, 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


In an attempt to directly recreate the original Python code (in 
the spirit of the "challenge" :) I came up with this.  It is only 
complete up to the first test in the original article (the easy 
puzzle that is solved by the parser alone).


module sudoku;

import  std.algorithm   ,
         std.array       ,
         std.conv        ,
         std.exception   ,
         std.range       ,
         std.stdio       ,
         std.string      ,
         std.traits      ;


/***************************************************************************************************
  *
  */
alias string[ string ] Values;


/***************************************************************************************************
  *
  */
bool all ( R )( R input )
if ( isInputRange!R ) {
     foreach ( elem ; input ) {
         if ( !elem ) {
             return false;
         }
     }
     return true;
}


/***************************************************************************************************
  *
  */
string[] cross ( RA, RB ) ( RA a, RB b )
if (
     isInputRange!RA
     && isForwardRange!RB
     && isImplicitlyConvertible!( ElementType!RB, ElementType!RA )
     && isSomeChar!( ElementType!RA )
) {
     Appender!( dchar[][] ) output;
     foreach ( dchar _a ; a ) {
         foreach ( dchar _b ; b.save ) {
             output.put( [ _a, _b ] );
         }
     }
     return output.data.to!( string[] )();
}

unittest {
     auto x = "ab";
     auto y = "12";
     assert( cross( x, y ) == [ `a1`, `a2`, `b1`, `b2` ] );
}


/***************************************************************************************************
  *
  */
enum NUM_SQUARES      = 81;
enum NUM_UNITS        = 27;
enum UNITS_PER_SQUARE = 3;
enum PEERS_PER_SQUARE = 20;

enum DIGITS = `123456789`;
enum ROWS   = `ABCDEFGHI`;
enum COLS   = DIGITS;

enum SQUARES = cross( ROWS, COLS );

enum ROW_SEGS = [ ROWS[ 0 .. 3 ], ROWS[ 3 .. 6 ], ROWS[ 6 .. 9 ] 
];
enum COL_SEGS = [ COLS[ 0 .. 3 ], COLS[ 3 .. 6 ], COLS[ 6 .. 9 ] 
];

enum ROW_UNITS = COLS.map!( c => cross( ROWS, [ c ] ) )();
enum COL_UNITS = ROWS.map!( r => cross( [ r ], COLS ) )();


/***************************************************************************************************
  *
  */
string[][][ string ] units;
string[]  [ string ] peers;


/***************************************************************************************************
  *
  */
int main ( string[] args ) {
     if ( args.length != 2 ) {
         writefln( "USAGE: %s <grid-data>", args[ 0 ] );
         return 1;
     }

     auto unitlist = ROW_UNITS.array()
                   ~ COL_UNITS.array()
                   ~ (
                         ROW_SEGS.map!(
                             rs =>
                             COL_SEGS.map!( cs => cross( rs, cs ) 
)()
                         )()
                         .join()
                     );

     foreach ( s ; SQUARES ) {
         auto us = unitlist.filter!( u => u.canFind( s ) 
)().array();
         units[ s ] = us;
         peers[ s ] =
             us
             .joiner()
             .filter!( e => e != s )() .array()
             .sort()
             .uniq() .array()
         ;
     }

     debug {
         assert( SQUARES.length == NUM_SQUARES );
         assert( unitlist.length == NUM_UNITS );

         foreach ( s ; SQUARES ) {
             assert( units[ s ].length == UNITS_PER_SQUARE , 
`Wrong number of units for square ` ~ s );
             assert( peers[ s ].length == PEERS_PER_SQUARE , 
`Wrong number of peers for square ` ~ s );
         }

         assert( units[ `C2` ] == [[`A2`, `B2`, `C2`, `D2`, `E2`, 
`F2`, `G2`, `H2`, `I2`],
                                   [`C1`, `C2`, `C3`, `C4`, `C5`, 
`C6`, `C7`, `C8`, `C9`],
                                   [`A1`, `A2`, `A3`, `B1`, `B2`, 
`B3`, `C1`, `C2`, `C3`]] );

         assert( peers[ `C2` ] == [`A1`, `A2`, `A3`, `B1`, `B2`, 
`B3`, `C1`, `C3`, `C4`, `C5`,
                                   `C6`, `C7`, `C8`, `C9`, `D2`, 
`E2`, `F2`, `G2`, `H2`, `I2`] );

         writeln( `All tests pass.` );
     }

     auto values = parseGrid( args[ 1 ] );
     display( values );

     return 0;
}


/***************************************************************************************************
  *
  */
Values parseGrid ( string grid ) {
     Values result;

     foreach ( s ; SQUARES ) {
         result[ s ] = DIGITS;
     }
     foreach ( s, d ; gridValues( grid ) ) {
         if ( ( d >= '1' && d <= '9' ) && !assign( result, s, d ) 
) {
             throw new Exception( `Failed to assign given ` ~ d ~ 
` to square ` ~ s );
         }
     }
     return result;
}


/***************************************************************************************************
  *
  */
auto gridValues ( string grid ) {
     char[ string ] result;

     auto chars = grid.filter!( e => ( e >= '0' && e <= '9' ) || e 
== '.' )().to!string();
     enforce( chars.length == 81 );
     foreach ( i, s ; SQUARES ) {
         result[ s ] = chars[ i ];
     }
     return result;
}


/***************************************************************************************************
  *
  */
bool assign ( ref Values values, string square, dchar digit ) {
     bool result = true;

     auto other = values[ square ].remove( digit );
     if ( other.map!( d2 => eliminate( values, square, d2 ) 
)().all() ) {
         return true;
     }
     else {
         return false;
     }
}


/***************************************************************************************************
  *
  */
bool eliminate ( ref Values values, string square, dchar digit ) {
     if ( !values[ square ].canFind( digit ) ) {
         // Already eliminated.
         return true;
     }

     auto other = values[ square ].remove( digit );
     values[ square ] = other;

     // (1) If a square is reduced to one value d2, then eliminate 
d2 from the peers.
     if ( other.length == 0 ) {
         return false; // Contradiction: removed last value.
     }
     else if ( other.length == 1 ) {
         if ( ! peers[ square ].map!( s => eliminate( values, s, 
other[ 0 ] ) )().all() ) {
             return false;
         }
     }

     // (2) If a unit u is reduced to only one place for a digit, 
then put it there.
     foreach ( u ; units[ square ] ) {
         auto dplaces = u.filter!( s => values[ s ].canFind( digit 
) )().array();
         if ( dplaces.length == 0 ) {
             return false; // Contradiction: no place for this 
value.
         }
         else if ( dplaces.length == 1 ) {
             // digit can only be in one place in unit; assign it 
there
             if ( ! assign( values, dplaces[ 0 ], digit ) ) {
                 return false;
             }
         }
     }

     return true;
}


/***************************************************************************************************
  *
  */
string remove ( string s, dchar c ) {
     return s.removechars( [ c ].to!string() );
}


/***************************************************************************************************
  *
  */
void display ( Values values ) {
     auto width = 1 + SQUARES.map!( s => values[ s ].length 
)().array().minPos!`a > b`()[ 0 ];
     auto seg   = std.range.repeat( '-', width * 3 ).array();
     auto line  = format( "\n%s+%s+%s", seg, seg, seg );

     foreach ( r ; ROWS ) {
         foreach ( c ; COLS ) {
             write( values[ [ r, c ] ].center( width ) );
             write( c == '3' || c == '6' ? `|` : `` );
         }
         if ( r == 'C' || r == 'F' ) {
             write( line );
         }
         writeln();
     }
     writeln();
}


Sample of execution:
--------------------------------------------------
grant aesgard ~/Projects/D/Sudoku/translated $ dmd sudoku.d 
-debug -property -unittest -w -wi
grant aesgard ~/Projects/D/Sudoku/translated $ time ./sudoku 
"003020600900305001001806400008102900700000008006708200002609500800203009005010300"
All tests pass.
4 8 3 |9 2 1 |6 5 7
9 6 7 |3 4 5 |8 2 1
2 5 1 |8 7 6 |4 9 3
------+------+------
5 4 8 |1 3 2 |9 7 6
7 2 9 |5 6 4 |1 3 8
1 3 6 |7 9 8 |2 4 5
------+------+------
3 7 2 |6 8 9 |5 1 4
8 1 4 |2 5 3 |7 6 9
6 9 5 |4 1 7 |3 8 2


real    0m0.012s
user    0m0.010s
sys     0m0.001s
--------------------------------------------------



 Aug 15 2012



prev sibling  parent  Timon Gehr <timon.gehr gmx.ch>  writes:


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



 Aug 15 2012