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

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.

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

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

Era Scarecrow:

> I don't see the python source off hand,

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

Bye,
bearophile

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.

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.

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

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

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.