127 lines
3.8 KiB
D
127 lines
3.8 KiB
D
import std.stdio, std.range, std.string, std.algorithm, std.array,
|
|
std.ascii, std.typecons;
|
|
|
|
struct Digit {
|
|
immutable char d;
|
|
|
|
this(in char d_) pure nothrow @safe @nogc
|
|
in { assert(d_ >= '0' && d_ <= '9'); }
|
|
body { this.d = d_; }
|
|
|
|
this(in int d_) pure nothrow @safe @nogc
|
|
in { assert(d_ >= '0' && d_ <= '9'); }
|
|
body { this.d = cast(char)d_; } // Required cast.
|
|
|
|
alias d this;
|
|
}
|
|
|
|
enum size_t sudokuUnitSide = 3;
|
|
enum size_t sudokuSide = sudokuUnitSide ^^ 2; // Sudoku grid side.
|
|
alias SudokuTable = Digit[sudokuSide ^^ 2];
|
|
|
|
|
|
Nullable!SudokuTable sudokuSolver(in ref SudokuTable problem)
|
|
pure nothrow {
|
|
alias Tgrid = uint;
|
|
Tgrid[SudokuTable.length] grid = void;
|
|
problem[].map!(c => c - '0').copy(grid[]);
|
|
|
|
// DMD doesn't inline this function. Performance loss.
|
|
Tgrid access(in size_t x, in size_t y) nothrow @safe @nogc {
|
|
return grid[y * sudokuSide + x];
|
|
}
|
|
|
|
// DMD doesn't inline this function. If you want to retain
|
|
// the same performance as the C++ entry and you use the DMD
|
|
// compiler then this function must be manually inlined.
|
|
bool checkValidity(in Tgrid val, in size_t x, in size_t y)
|
|
pure nothrow @safe @nogc {
|
|
/*static*/ foreach (immutable i; staticIota!(0, sudokuSide))
|
|
if (access(i, y) == val || access(x, i) == val)
|
|
return false;
|
|
|
|
immutable startX = (x / sudokuUnitSide) * sudokuUnitSide;
|
|
immutable startY = (y / sudokuUnitSide) * sudokuUnitSide;
|
|
|
|
/*static*/ foreach (immutable i; staticIota!(0, sudokuUnitSide))
|
|
/*static*/ foreach (immutable j; staticIota!(0, sudokuUnitSide))
|
|
if (access(startX + j, startY + i) == val)
|
|
return false;
|
|
|
|
return true;
|
|
}
|
|
|
|
bool canPlaceNumbers(in size_t pos=0) nothrow @safe @nogc {
|
|
if (pos == SudokuTable.length)
|
|
return true;
|
|
if (grid[pos] > 0)
|
|
return canPlaceNumbers(pos + 1);
|
|
|
|
foreach (immutable n; 1 .. sudokuSide + 1)
|
|
if (checkValidity(n, pos % sudokuSide, pos / sudokuSide)) {
|
|
grid[pos] = n;
|
|
if (canPlaceNumbers(pos + 1))
|
|
return true;
|
|
grid[pos] = 0;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
if (canPlaceNumbers) {
|
|
//return typeof(return)(grid[]
|
|
// .map!(c => Digit(c + '0'))
|
|
// .array);
|
|
immutable SudokuTable result = grid[]
|
|
.map!(c => Digit(c + '0'))
|
|
.array;
|
|
return typeof(return)(result);
|
|
} else
|
|
return typeof(return)();
|
|
}
|
|
|
|
string representSudoku(in ref SudokuTable sudo)
|
|
pure nothrow @safe out(result) {
|
|
assert(result.countchars("1-9") == sudo[].count!q{a != '0'});
|
|
assert(result.countchars(".") == sudo[].count!q{a == '0'});
|
|
} body {
|
|
static assert(sudo.length == 81,
|
|
"representSudoku works only with a 9x9 Sudoku.");
|
|
string result;
|
|
|
|
foreach (immutable i; 0 .. sudokuSide) {
|
|
foreach (immutable j; 0 .. sudokuSide) {
|
|
result ~= sudo[i * sudokuSide + j];
|
|
result ~= ' ';
|
|
if (j == 2 || j == 5)
|
|
result ~= "| ";
|
|
}
|
|
result ~= "\n";
|
|
if (i == 2 || i == 5)
|
|
result ~= "------+-------+------\n";
|
|
}
|
|
|
|
return result.replace("0", ".");
|
|
}
|
|
|
|
void main() {
|
|
enum ValidateCells(string s) = s.map!Digit.array;
|
|
|
|
immutable SudokuTable problem = ValidateCells!("
|
|
850002400
|
|
720000009
|
|
004000000
|
|
000107002
|
|
305000900
|
|
040000000
|
|
000080070
|
|
017000000
|
|
000036040".removechars(whitespace));
|
|
problem.representSudoku.writeln;
|
|
|
|
immutable solution = problem.sudokuSolver;
|
|
if (solution.isNull)
|
|
writeln("Unsolvable!");
|
|
else
|
|
solution.get.representSudoku.writeln;
|
|
}
|