Sudoku Py / C++11 / D?

ixid nuaccount at gmail.com
Wed Aug 15 18:41:00 PDT 2012


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




More information about the Digitalmars-d-learn mailing list