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