Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
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
Re: Sudoku Py / C++11 / D?
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 ", 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;
}
Re: Sudoku Py / C++11 / D?
Era Scarecrow: I don't see the python source off hand, The original Python code: http://norvig.com/sudopy.shtml Bye, bearophile
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
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 .659.8284536..3.54...325..6.. .6... .59.8 28... .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) real0m9.565s user0m0.015s sys 0m0.046s
Re: Sudoku Py / C++11 / D?
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- sudoku-solver/402#402 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
Re: Sudoku Py / C++11 / D?
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: http://codegolf.stackexchange.com/questions/378/implement-a-brute-force-sudoku-solver/402#402 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.
Re: Sudoku Py / C++11 / D?
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 .659.8284536..3.54...325..6.. .6... .59.8 28... .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) real0m9.565s user0m0.015s sys 0m0.046s How many solutions do you find for that one?
Re: Sudoku Py / C++11 / D?
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
Re: Sudoku Py / C++11 / D?
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
Re: Sudoku Py / C++11 / D?
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
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
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;
}
Re: Sudoku Py / C++11 / D?
Hmm, sorry odd things have happened to the formatting. Visual D's spacing doesn't seem to work very well outside of itself.
Re: Sudoku Py / C++11 / D?
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 : > 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. >
Re: Sudoku Py / C++11 / D?
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')
Re: Sudoku Py / C++11 / D?
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?
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
> 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?
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
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 : > 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. >
Re: Sudoku Py / C++11 / D?
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).
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
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?
Re: Sudoku Py / C++11 / D?
my code is located at http://dpaste.dzfl.pl/93cd5f45 2012/8/19, maarten van damme : > 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? >
Re: Sudoku Py / C++11 / D?
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: .659.8284536..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.
Re: Sudoku Py / C++11 / D?
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?
Re: Sudoku Py / C++11 / D?
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).
Re: Sudoku Py / C++11 / D?
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...
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
> 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 ...
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
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
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
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
Re: Sudoku Py / C++11 / D?
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
Re: Sudoku Py / C++11 / D?
2012/8/17, Chris Cain : > > 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...
Re: Sudoku Py / C++11 / D?
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 data0 1 0 1 result 0 0 0 1 OR | source 0 0 1 1 data0 1 0 1 result 0 1 1 1 Xor ^ source 0 0 1 1 data0 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...
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
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 : > 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. > >
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
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 : 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!
Re: Sudoku Py / C++11 / D?
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 :)
Re: Sudoku Py / C++11 / D?
> 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...
Re: Sudoku Py / C++11 / D?
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__, 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
Re: Sudoku Py / C++11 / D?
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
Re: Sudoku Py / C++11 / D?
> 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__, 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.
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
and everythingPossible should also be changed to something ala 2 ^(side) -1
Re: Sudoku Py / C++11 / D?
2012/8/25 Timon Gehr : > 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
Re: Sudoku Py / C++11 / D?
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
Re: Sudoku Py / C++11 / D?
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).
Re: Sudoku Py / C++11 / D?
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
Re: Sudoku Py / C++11 / D?
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. :)
Re: Sudoku Py / C++11 / D?
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.
Re: Sudoku Py / C++11 / D?
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.14...9 Flipped: 4...9..2.15..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
Re: Sudoku Py / C++11 / D?
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?
Re: Sudoku Py / C++11 / D?
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?
Re: Sudoku Py / C++11 / D?
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]
}
Re: Sudoku Py / C++11 / D?
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 ?
Re: Sudoku Py / C++11 / D?
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
Re: Sudoku Py / C++11 / D?
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
Re: Sudoku Py / C++11 / D?
And now your backtrack() function too can be nothrow :-) Bye, bearophile
Re: Sudoku Py / C++11 / D?
Ok, thank you very much with your help :)
Re: Sudoku Py / C++11 / D?
> > 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).
Re: Sudoku Py / C++11 / D?
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.
