Sudoku Py / C++11 / D?
Chris Nicholson-Sauls
ibisbasenji at gmail.com
Wed Aug 15 02:59:30 PDT 2012
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 at aesgard ~/Projects/D/Sudoku/translated $ dmd sudoku.d
-debug -property -unittest -w -wi
grant at 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
--------------------------------------------------
More information about the Digitalmars-d-learn
mailing list