Solve a Numbrix puzzle: Difference between revisions

=={{header|D}}==

From the refactored C++ version with more precise typing. The NumbrixPuzzle struct is created at compile-time, so its asserts and exceptions can catch most malformed puzzles at compile-time.

{{trans|C++}}

<lang d>import std.stdio, std.conv, std.string, std.range, std.array, std.typecons, std.algorithm;

struct {

alias BitSet8 = ubyte; // A set of 8 bits.

alias Cell = uint;

enum : string { unavailableInCell = "#", availableInCell = "." }

enum : Cell { unavailableCell = Cell.max, availableCell = 0 }

this(in string inPuzzle) pure @safe {

const rawPuzzle = inPuzzle.splitLines.map!(row => row.split).array;

assert(!rawPuzzle.empty);

assert(!rawPuzzle[0].empty);

assert(rawPuzzle.all!(row => row.length == rawPuzzle[0].length)); // Is rectangular.

gridWidth = rawPuzzle[0].length;

gridHeight = rawPuzzle.length;

immutable nMaxCells = gridWidth * gridHeight;

grid = new Cell[nMaxCells];

auto knownMutable = new bool[nMaxCells + 1];

uint nAvailableMutable = nMaxCells;

bool[Cell] seenCells; // To avoid duplicate input numbers.

uint i = 0;

foreach (const piece; rawPuzzle.join) {

if (piece == unavailableInCell) {

nAvailableMutable--;

grid[i++] = unavailableCell;

continue;

} else if (piece == availableInCell) {

grid[i] = availableCell;

} else {

immutable cell = piece.to!Cell;

assert(cell > 0 && cell <= nMaxCells);

assert(cell !in seenCells);

seenCells[cell] = true;

knownMutable[cell] = true;

grid[i] = cell;

}

i++;

}

known = knownMutable.idup;

nAvailable = nAvailableMutable;

}

@disable this();

auto solve() pure nothrow @safe @nogc

out(result) {

if (!result.isNull) {

// Can't verify 'result' here because it's const.

// assert(!result.get.join.canFind(availableCell.text));

assert(!grid.canFind(availableCell));

auto values = grid.filter!(c => c != unavailableCell);

auto interval = iota(reduce!min(values.front, values.dropOne),

reduce!max(values.front, values.dropOne) + 1);

assert(values.walkLength == interval.length);

assert(interval.all!(c => values.count(c) == 1)); // Quadratic.

}

} body {

auto result = grid

.map!(c => (c == unavailableCell) ? unavailableInCell : c.text)

.chunks(gridWidth);

alias OutRange = Nullable!(typeof(result));

const start = findStart;

if (start.isNull)

return OutRange();

search(start.r, start.c, start.cell + 1, 1);

if (start.cell > 1) {

immutable direction = -1;

search(start.r, start.c, start.cell + direction, direction);

}

if (grid.any!(c => c == availableCell))

return OutRange();

else

return OutRange(result);

}

private:

bool search(in uint r, in uint c, in Cell cell, in int direction)

pure nothrow @safe @nogc {

if ((cell > nAvailable && direction > 0) || (cell == 0 && direction < 0) ||

(cell == nAvailable && known[cell]))

return true; // One solution found.

immutable neighbors = getNeighbors(r, c);

if (known[cell]) {

foreach (immutable i, immutable rc; shifts) {

if (neighbors & (1u << i)) {

immutable c2 = c + rc[0],

r2 = r + rc[1];

if (grid[r2 * gridWidth + c2] == cell)

if (search(r2, c2, cell + direction, direction))

return true;

}

}

return false;

}

foreach (immutable i, immutable rc; shifts) {

if (neighbors & (1u << i)) {

immutable c2 = c + rc[0],

r2 = r + rc[1],

pos = r2 * gridWidth + c2;

if (grid[pos] == availableCell) {

grid[pos] = cell; // Try.

if (search(r2, c2, cell + direction, direction))

return true;

grid[pos] = availableCell; // Restore.

}

}

}

return false;

}

BitSet8 getNeighbors(in uint r, in uint c) const pure nothrow @safe @nogc {

typeof(return) usable = 0;

foreach (immutable i, immutable rc; shifts) {

immutable c2 = c + rc[0],

r2 = r + rc[1];

if (c2 >= gridWidth || r2 >= gridHeight)

continue;

if (grid[r2 * gridWidth + c2] != unavailableCell)

usable |= (1u << i);

}

return usable;

}

auto findStart() const pure nothrow @safe @nogc {

alias Triple = Tuple!(uint,"r", uint,"c", Cell,"cell");

Nullable!Triple result;

auto cell = Cell.max;

foreach (immutable r; 0 .. gridHeight) {

foreach (immutable c; 0 .. gridWidth) {

immutable pos = gridWidth * r + c;

if (grid[pos] != availableCell &&

grid[pos] != unavailableCell && grid[pos] < cell) {

cell = grid[pos];

result = Triple(r, c, cell);

}

}

}

return result;

}

static immutable int[2][4] shifts = [[0, -1], [0, 1], [-1, 0], [1, 0]];

immutable uint gridWidth, gridHeight;

immutable int nAvailable;

immutable bool[] known; // Given known cells of the puzzle.

Cell[] grid; // Flattened mutable game grid.

}

void main() {

// enum NumbrixPuzzle to catch malformed puzzles at compile-time.

enum puzzle1 = ". . . . . . . . .

. . 46 45 . 55 74 . .

. 38 . . 43 . . 78 .

. 35 . . . . . 71 .

. . 33 . . . 59 . .

. 17 . . . . . 67 .

. 18 . . 11 . . 64 .

. . 24 21 . 1 2 . .

. . . . . . . . .".NumbrixPuzzle;

enum puzzle2 = ". . . . . . . . .

. 11 12 15 18 21 62 61 .

. 6 . . . . . 60 .

. 33 . . . . . 57 .

. 32 . . . . . 56 .

. 37 . 1 . . . 73 .

. 38 . . . . . 72 .

. 43 44 47 48 51 76 77 .

. . . . . . . . .".NumbrixPuzzle;

enum puzzle3 = "17 . . . 11 . . . 59

. 15 . . 6 . . 61 .

. . 3 . . . 63 . .

. . . . 66 . . . .

23 24 . 68 67 78 . 54 55

. . . . 72 . . . .

. . 35 . . . 49 . .

. 29 . . 40 . . 47 .

31 . . . 39 . . . 45".NumbrixPuzzle;

foreach (puzzle; [puzzle1, puzzle2, puzzle3]) {

auto solution = puzzle.solve; // Solved at run-time.

if (solution.isNull)

writeln("No solution found for puzzle.\n");

else

writefln("One solution:\n%(%-(%2s %)\n%)\n", solution);

}

}</lang>

{{out}}

<pre>One solution:

49 50 51 52 53 54 75 76 81

48 47 46 45 44 55 74 77 80

37 38 39 40 43 56 73 78 79

36 35 34 41 42 57 72 71 70

31 32 33 14 13 58 59 68 69

30 17 16 15 12 61 60 67 66

29 18 19 20 11 62 63 64 65

28 25 24 21 10 1 2 3 4

27 26 23 22 9 8 7 6 5

One solution:

9 10 13 14 19 20 63 64 65

8 11 12 15 18 21 62 61 66

7 6 5 16 17 22 59 60 67

34 33 4 3 24 23 58 57 68

35 32 31 2 25 54 55 56 69

36 37 30 1 26 53 74 73 70

39 38 29 28 27 52 75 72 71

40 43 44 47 48 51 76 77 78

41 42 45 46 49 50 81 80 79

One solution:

17 16 13 12 11 10 9 60 59

18 15 14 5 6 7 8 61 58

19 20 3 4 65 64 63 62 57

22 21 2 1 66 79 80 81 56

23 24 69 68 67 78 77 54 55

26 25 70 71 72 75 76 53 52

27 28 35 36 73 74 49 50 51

30 29 34 37 40 41 48 47 46

31 32 33 38 39 42 43 44 45</pre>