Sudoku: Difference between revisions

Content added Content deleted
(New D entry that solves far more Sudokus)
(Stronger types for D entry)
Line 1,499: Line 1,499:
<lang d>import std.stdio, std.range, std.string, std.algorithm, std.array;
<lang d>import std.stdio, std.range, std.string, std.algorithm, std.array;


⚫
enum int side = 9; // Sudoku grid side
⚫
string sudokuSolver(in string problem)
alias immutable(char) TableItem; // Statically in '0'...'9'
alias TableItem[side ^^ 2] SudokuTable;


⚫
SudokuTable sudokuSolver(const ref SudokuTable problem)
in {
in {
⚫
assert(problem == removechars(problem[], "^0-9"));
⚫
enum int side = 9; // dupe
assert(problem.walkLength == side ^^ 2);
⚫
assert(problem == problem.removechars("^0-9"));
} body {
} body {
⚫
uint[side ^^ 2] grid = array(map!q{ a - '0' }(problem[]));
enum int side = 9;
⚫
uint[side ^^ 2] grid = array(map!q{ a - '0' }(problem));


bool checkValidity(in int val, in int x, in int y) nothrow {
bool checkValidity(in int val, in int x, in int y) nothrow {
Line 1,520: Line 1,522:
return false;
return false;
return true;
return true;
}

static class FinishedSudokuException: Exception {
this(string msg) {
super(msg);
}
}
}


void placeNumber(in int pos) {
void placeNumber(in int pos) {
if (pos == side ^^ 2)
if (pos == side ^^ 2)
throw new Exception("Finished!");
throw new FinishedSudokuException("Finished!");
if (grid[pos] > 0) {
if (grid[pos] > 0) {
placeNumber(pos + 1);
placeNumber(pos + 1);
Line 1,540: Line 1,548:
try {
try {
placeNumber(0);
placeNumber(0);
return ""; // Unsolvable
return typeof(return).init;
} catch (Exception ex)
} catch (FinishedSudokuException ex) {
return array(map!q{ cast(char)(a + '0') }(grid[])).idup;
//auto r = map!q{ cast(TableItem)(a + '0') }(grid[]);
auto r = map!q{ cast(char)(a + '0') }(grid[]);
SudokuTable result = array(r).idup;
return result;
}
}
}




string formatSudoku(in string sudo)
string formatSudoku(const ref SudokuTable sudo)
in {
in {
⚫
assert(sudo == removechars(sudo[], "^0-9"));
enum int side = 9; // dupe
assert(sudo.walkLength == side ^^ 2);
⚫
assert(sudo == sudo.removechars("^0-9"));
} body {
} body {
enum int side = 9;
string result;
string result;


Line 1,572: Line 1,581:


void main() {
void main() {
const problem = "850002400" ~
const SudokuTable problem =
"720000009" ~
"850002400" ~
"004000000" ~
"720000009" ~
"000107002" ~
"004000000" ~
"305000900" ~
"000107002" ~
"040000000" ~
"305000900" ~
"000080070" ~
"040000000" ~
"017000000" ~
"000080070" ~
"000036040";
"017000000" ~
"000036040";
writeln(formatSudoku(problem));
writeln(formatSudoku(problem));


const solution = sudokuSolver(problem);
const solution = sudokuSolver(problem);
if (solution.empty)
if (solution[0] == TableItem.init)
writeln("Unsolvable!");
writeln("Unsolvable!");
else
else
Retrieved from "https://rosettacode.org/wiki/Sudoku"