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 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 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 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
next 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 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 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 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, 


 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 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 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 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
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 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 next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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- 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
Aug 15 2012
prev sibling 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:

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.
Aug 15 2012
prev sibling next sibling parent "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
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 next 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 next 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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling 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 next sibling parent 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
prev sibling next sibling parent maarten van damme <maartenvd1994 gmail.com> writes:
--e89a8f646605ec401d04c767627b
Content-Type: text/plain; charset=ISO-8859-1

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?

--e89a8f646605ec401d04c767627b
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<p>I&#39;ve now ran in something odd. Using a slight variant from my progra=
m on dpaste (can&#39;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&#39;s impossible yet mine takes over 3885 seconds.=
 Where is this slowdown coming from?</p>


--e89a8f646605ec401d04c767627b--
Aug 16 2012
prev sibling next sibling parent maarten van damme <maartenvd1994 gmail.com> writes:
--e89a8f3b9c0190d20e04c7690c37
Content-Type: text/plain; charset=ISO-8859-1

 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

 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? --e89a8f3b9c0190d20e04c7690c37 Content-Type: text/html; charset=ISO-8859-1 <p><br> &gt; This is because your specific solution is slow.<br> &gt;<br> &gt; Mine takes &lt;20ms on the &#39;hard&#39; puzzle and ~13s on the impossible one.<br> &gt; (~2.4 GHZ intel x86_64 machine, with gdmd -O -release -inline -noboundscheck.)<br> &gt; There is a constant factor between those two solutions.</p> <p>I&#39;ve compiled it using dmd on my latitude e5500 which is not that fast so I don&#39;t think it&#39;s that slow...</p> <p>Besides, lets say mine is five times slower, 3000 seconds is still waaay to much. When I&#39;m back able to get my laptop to use my crapy data connection I&#39;ll compare.</p> <p>Do you have some optimization ideas by the way?</p> --e89a8f3b9c0190d20e04c7690c37--
Aug 16 2012
prev sibling next sibling parent 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
prev sibling next sibling parent "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
prev sibling next sibling parent maarten van damme <maartenvd1994 gmail.com> writes:
--e89a8f3b9c11db4c2e04c79b2b2f
Content-Type: text/plain; charset=ISO-8859-1

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?

--e89a8f3b9c11db4c2e04c79b2b2f
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<p>Great, i tried to get rid of the dynamic array &quot;possibilities&quot;=
 by representing it using a static array of bools. This approach made it 4 =
times faster :)</p>
<p>When i have a solid wifi connection I&#39;m going to install dmd 2.60 to=
 compile timon&#39;s code. In the meantime I&#39;ve started beautifying the=
 source so i can follow the logic.</p>
<p>I still have a few questions however:<br>
- era claims his code takes 12 seconds on the hardest supplied puzzle yet i=
t enters an infinite loop when the puzzle isnt solvable. Is he talking abou=
t a different puzzle?</p>
<p>-is it normal that const ref is slower then ref?</p>
<p>- in an effort of trying to make the program reuse the same memory I&#39=
;ve moved some temporary variables outside the function but the program bec=
ame slower, how can this be?</p>
<p>- in a few hours i&#39;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&#39;s solver. What&#39;s that much mo=
re efficient in his solution?</p>


--e89a8f3b9c11db4c2e04c79b2b2f--
Aug 19 2012
prev sibling next 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 next sibling parent "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
prev sibling next sibling parent maarten van damme <maartenvd1994 gmail.com> writes:
--e89a8f3b9c11006df604c7a504fe
Content-Type: text/plain; charset=ISO-8859-1

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?

--e89a8f3b9c11006df604c7a504fe
Content-Type: text/html; charset=ISO-8859-1

<p>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 :)</p>
<p>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?</p>
<p>Is copying a static arrays cheaper then recalculating the lovation of
collumns and squares btw?</p>

--e89a8f3b9c11006df604c7a504fe--
Aug 19 2012
prev sibling next sibling parent "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
prev sibling next sibling parent maarten van damme <maartenvd1994 gmail.com> writes:
--14dae934053921654d04c7a76168
Content-Type: text/plain; charset=ISO-8859-1

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

--14dae934053921654d04c7a76168
Content-Type: text/html; charset=ISO-8859-1

<p>I&#39;m using a static array.</p>
<p>I&#39;m hesitating though if I should store possibilities in a precalculated
array or calculate them in-place. If i precalculate the possibilities i&#39;d
have to copy them over and over so i don&#39;t know if it&#39;s smart.</p>

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

--14dae934053921654d04c7a76168--
Aug 19 2012
prev sibling next sibling parent "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
prev sibling next sibling parent 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.

Aug 19 2012
prev sibling next sibling parent "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.

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.


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
prev sibling next sibling parent maarten van damme <maartenvd1994 gmail.com> writes:
--e89a8f3b9c0162b51d04c7b8903e
Content-Type: text/plain; charset=ISO-8859-1

  Not true. Brute force will get the job done, but it's slow and bulky. By

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

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

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. --e89a8f3b9c0162b51d04c7b8903e Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <p><br> &gt; =A0Not true. Brute force will get the job done, but it&#39;s slow and = bulky. By using other techniques can eliminate thousands, millions, or bill= ions of cycles through simply by removing a few possible numbers.<br> &gt;</p> <p>Yes, but these techniques have a drawback : they are not garantueed to f= ind solutions yet they are garantueed to increase the time a run takes.</p> <p>I&#39;m still unsure if it would be worth carrying over that possibiliti= es array. I&#39;m going to implement auto-solving of single candidates and = see how big the performance hit/gain is.</p> <p>&gt; =A0I&#39;ve seen on the hard level that the brute force recursive c= ode went some 20 levels deep (at one point). If it did all combinations of = 9^20 than you&#39;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.<br> &gt;</p> <p>Yes but I only test allowed numbers so if of those 20 combinations we ne= ed 5 fours, 3 nines, 4 twos and 8 ones, the possibilities to test are only = <br> 3491888400 which is reasonable for a pc :)</p> <p>&gt; Here&#39;s what I&#39;ve done recently. I&#39;ve made a grid someth= ing like ubyte[10][9][9]. This represents the grid and all combinations nee= ded for it. This way if [0] is non-zero you know it has an answer, otherwis= e the rest are which are potentially possible.</p> <p>That is indeed a really smart approach, I&#39;ll try that.</p> <p>By optimizing a bit more (who would&#39;ve thought that a for loop copyi= ng values one by one is way faster then some slice magic?) I was able to ma= ke my program 3 times faster. Now it can solve an empty sudoku in 0.05 ms a= nd solve the hard sudoku in 0.06s. My sudoku generator for valid sudoku sol= ution now runs at 13000 sudokus a second.</p> <p>Still it comes nowhere near beating timons solution. Is the logic of tha= t documented somewhere because I don&#39;t understand it.</p> <p>And vera, why are you using exceptions instead of return values? I think= it&#39;s slowing your solver down considerably.</p> --e89a8f3b9c0162b51d04c7b8903e--
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 next sibling parent "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
prev sibling next sibling 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 next sibling parent 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
prev sibling 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 next sibling parent 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,


 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
prev sibling 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 "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,


 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
prev sibling 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 next 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 "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
prev sibling 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 maarten van damme <maartenvd1994 gmail.com> writes:
 Some suggestions about the code:

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
prev sibling next 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 next sibling parent 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
prev sibling next sibling 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 next sibling parent "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
prev sibling next sibling parent "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
prev sibling 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 next sibling parent 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
prev sibling next sibling parent "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
prev sibling next sibling parent 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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
And now your backtrack() function too can be nothrow :-)

Bye,
bearophile
Aug 25 2012
prev sibling next sibling 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