Solve a Numbrix puzzle: Difference between revisions
(→{{header|Tcl}}: Added zkl) |
m (→{{header|zkl}}: typos) |
||
| Line 1,538: | Line 1,538: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|Python}} |
|||
This code solves Hidato, Hopido and Numbrix puzzles. |
This code solves Hidato, Hopido and Numbrix puzzles. |
||
<lang zkl> // Solve Hidato/Hopido/Numbrix puzzles |
<lang zkl> // Solve Hidato/Hopido/Numbrix puzzles |
||
| Line 1,574: | Line 1,575: | ||
if(not given.holds(cells)){ given.append(cells); terminated=False; } |
if(not given.holds(cells)){ given.append(cells); terminated=False; } |
||
given=given.filter().sort(); |
given=given.filter().sort(); |
||
self |
|||
} |
} |
||
fcn solve{ //-->Bool |
fcn solve{ //-->Bool |
||
Revision as of 03:28, 3 January 2016
You are encouraged to solve this task according to the task description, using any language you may know.
Numbrix puzzles are similar to Hidato. The most important difference is that it is only possible to move 1 node left, right, up, or down (sometimes referred to as the Von Neumann neighborhood). Published puzzles also tend not to have holes in the grid and may not always indicate the end node. Two examples follow:
- Example 1
Problem.
0 0 0 0 0 0 0 0 0 0 0 46 45 0 55 74 0 0 0 38 0 0 43 0 0 78 0 0 35 0 0 0 0 0 71 0 0 0 33 0 0 0 59 0 0 0 17 0 0 0 0 0 67 0 0 18 0 0 11 0 0 64 0 0 0 24 21 0 1 2 0 0 0 0 0 0 0 0 0 0 0
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
- Example 2
Problem.
0 0 0 0 0 0 0 0 0 0 11 12 15 18 21 62 61 0 0 6 0 0 0 0 0 60 0 0 33 0 0 0 0 0 57 0 0 32 0 0 0 0 0 56 0 0 37 0 1 0 0 0 73 0 0 38 0 0 0 0 0 72 0 0 43 44 47 48 51 76 77 0 0 0 0 0 0 0 0 0 0
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
- Task
Write a program to solve puzzles of this ilk, demonstrating your program by solving the above examples. Extra credit for other interesting examples.
Related Tasks:
AutoHotkey
<lang AutoHotkey>SolveNumbrix(Grid, Locked, Max, row, col, num:=1, R:="", C:=""){ if (R&&C) ; if neighbors (not first iteration) { Grid[R, C] := ">" num ; place num in current neighbor and mark it visited ">" row:=R, col:=C ; move to current neighbor }
num++ ; increment num if (num=max) ; if reached end return map(Grid) ; return solution
if locked[num] ; if current num is a locked value { row := StrSplit((StrSplit(locked[num], ",").1) , ":").1 ; find row of num col := StrSplit((StrSplit(locked[num], ",").1) , ":").2 ; find col of num if SolveNumbrix(Grid, Locked, Max, row, col, num) ; solve for current location and value return map(Grid) ; if solved, return solution } else { for each, value in StrSplit(Neighbor(row,col), ",") { R := StrSplit(value, ":").1 C := StrSplit(value, ":").2
if (Grid[R,C] = "") ; a hole or out of bounds || InStr(Grid[R, C], ">") ; visited || Locked[num+1] && !(Locked[num+1]~= "\b" R ":" C "\b") ; not neighbor of locked[num+1] || Locked[num-1] && !(Locked[num-1]~= "\b" R ":" C "\b") ; not neighbor of locked[num-1] || Locked[num] ; locked value || Locked[Grid[R, C]] ; locked cell continue
if SolveNumbrix(Grid, Locked, Max, row, col, num, R, C) ; solve for current location, neighbor and value return map(Grid) ; if solved, return solution } } num-- ; step back for i, line in Grid for j, element in line if InStr(element, ">") && (StrReplace(element, ">") >= num) Grid[i, j] := 0 }
- --------------------------------
- --------------------------------
- --------------------------------
Neighbor(row,col){ return row-1 ":" col . "," row+1 ":" col . "," row ":" col+1 . "," row ":" col-1 }
- --------------------------------
map(Grid){ for i, row in Grid { for j, element in row line .= (A_Index > 1 ? "`t" : "") . element map .= (map<>""?"`n":"") line line := "" } return StrReplace(map, ">") }</lang> Examples:<lang AutoHotkey>;-------------------------------- Grid := [[0, 0, 0, 0, 0, 0, 0, 0, 0] ,[0, 0, 46, 45, 0, 55, 74, 0, 0] ,[0, 38, 0, 0, 43, 0, 0, 78, 0] ,[0, 35, 0, 0, 0, 0, 0, 71, 0] ,[0, 0, 33, 0, 0, 0, 59, 0, 0] ,[0, 17, 0, 0, 0, 0, 0, 67, 0] ,[0, 18, 0, 0, 11, 0, 0, 64, 0] ,[0, 0, 24, 21, 0, 1, 2, 0, 0] ,[0, 0, 0, 0, 0, 0, 0, 0, 0]]
- --------------------------------
- find locked cells, find row and col of first value "1" and max value
Locked := [] max := 1 for i, line in Grid for j, element in line { max ++ if element = 1 row :=i , col := j if (element > 0) Locked[element] := i ":" j "," Neighbor(i, j) ; save locked elements position and neighbors
}
- --------------------------------
MsgBox, 262144, ,% SolveNumbrix(Grid, Locked, Max, row, col) return
</lang>
Outputs:
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
C++
<lang cpp>
- include <vector>
- include <sstream>
- include <iostream>
- include <iterator>
- include <cstdlib>
- include <string>
- include <bitset>
using namespace std; typedef bitset<4> hood_t;
struct node { int val; hood_t neighbors; };
class nSolver { public:
void solve(vector<string>& puzz, int max_wid) { if (puzz.size() < 1) return; wid = max_wid; hei = static_cast<int>(puzz.size()) / wid; max = wid * hei; int len = max, c = 0; arr = vector<node>(len, node({ 0, 0 })); weHave = vector<bool>(len + 1, false);
for (const auto& s : puzz) { if (s == "*") { max--; arr[c++].val = -1; continue; } arr[c].val = atoi(s.c_str()); if (arr[c].val > 0) weHave[arr[c].val] = true; c++; }
solveIt(); c = 0; for (auto&& s : puzz) { if (s == ".") s = std::to_string(arr[c].val); c++; } }
private: bool search(int x, int y, int w, int dr) { if ((w > max && dr > 0) || (w < 1 && dr < 0) || (w == max && weHave[w])) return true;
node& n = arr[x + y * wid]; n.neighbors = getNeighbors(x, y); if (weHave[w]) { for (int d = 0; d < 4; d++) { if (n.neighbors[d]) { int a = x + dx[d], b = y + dy[d]; if (arr[a + b * wid].val == w) if (search(a, b, w + dr, dr)) return true; } } return false; }
for (int d = 0; d < 4; d++) { if (n.neighbors[d]) { int a = x + dx[d], b = y + dy[d]; if (arr[a + b * wid].val == 0) { arr[a + b * wid].val = w; if (search(a, b, w + dr, dr)) return true; arr[a + b * wid].val = 0; } } } return false; }
hood_t getNeighbors(int x, int y) { hood_t retval; for (int xx = 0; xx < 4; xx++) { int a = x + dx[xx], b = y + dy[xx]; if (a < 0 || b < 0 || a >= wid || b >= hei) continue; if (arr[a + b * wid].val > -1) retval.set(xx); } return retval; }
void solveIt() { int x, y, z; findStart(x, y, z); if (z == 99999) { cout << "\nCan't find start point!\n"; return; } search(x, y, z + 1, 1); if (z > 1) search(x, y, z - 1, -1); }
void findStart(int& x, int& y, int& z) { z = 99999; for (int b = 0; b < hei; b++) for (int a = 0; a < wid; a++) if (arr[a + wid * b].val > 0 && arr[a + wid * b].val < z) { x = a; y = b; z = arr[a + wid * b].val; }
}
vector<int> dx = vector<int>({ -1, 1, 0, 0 }); vector<int> dy = vector<int>({ 0, 0, -1, 1 }); int wid, hei, max; vector<node> arr; vector<bool> weHave; };
//------------------------------------------------------------------------------ int main(int argc, char* argv[]) { int wid; string p; //p = ". . . . . . . . . . . 46 45 . 55 74 . . . 38 . . 43 . . 78 . . 35 . . . . . 71 . . . 33 . . . 59 . . . 17 . . . . . 67 . . 18 . . 11 . . 64 . . . 24 21 . 1 2 . . . . . . . . . . ."; wid = 9; //p = ". . . . . . . . . . 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 . . . . . . . . . ."; wid = 9; p = "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"; wid = 9;
istringstream iss(p); vector<string> puzz; copy(istream_iterator<string>(iss), istream_iterator<string>(), back_inserter<vector<string> >(puzz)); nSolver s; s.solve(puzz, wid);
int c = 0; for (const auto& s : puzz) { if (s != "*" && s != ".") { if (atoi(s.c_str()) < 10) cout << "0"; cout << s << " "; } else cout << " "; if (++c >= wid) { cout << endl; c = 0; } } cout << endl << endl; return system("pause"); } </lang>
- Output:
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 01 02 03 04 27 26 23 22 09 08 07 06 05 09 10 13 14 19 20 63 64 65 08 11 12 15 18 21 62 61 66 07 06 05 16 17 22 59 60 67 34 33 04 03 24 23 58 57 68 35 32 31 02 25 54 55 56 69 36 37 30 01 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 17 16 13 12 11 10 09 60 59 18 15 14 05 06 07 08 61 58 19 20 03 04 65 64 63 62 57 22 21 02 01 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
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.
<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>
- Output:
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
Icon and Unicon
This is a Unicon-specific solution, based on the Unicon Hidato problem solver: <lang unicon>global nCells, cMap, best record Pos(r,c)
procedure main(A)
puzzle := showPuzzle("Input",readPuzzle())
QMouse(puzzle,findStart(puzzle),&null,0)
showPuzzle("Output", solvePuzzle(puzzle)) | write("No solution!")
end
procedure readPuzzle()
# Start with a reduced puzzle space
p := []
nCells := maxCols := 0
every line := !&input do {
put(p,[: gencells(line) :])
maxCols <:= *p[-1]
}
# Now normalize all rows to the same length
every i := 1 to *p do p[i] := [: !p[i] | (|-1\(maxCols - *p[i])) :]
return p
end
procedure gencells(s)
static WS, NWS
initial {
NWS := ~(WS := " \t")
cMap := table() # Map to/from internal model
cMap["_"] := 0; cMap[0] := "_"
}
s ? while not pos(0) do {
w := (tab(many(WS))|"", tab(many(NWS))) | break
w := numeric(\cMap[w]|w)
if -1 ~= w then nCells +:= 1
suspend w
}
end
procedure showPuzzle(label, p)
write(label," with ",nCells," cells:")
every r := !p do {
every c := !r do writes(right((\cMap[c]|c),*nCells+1))
write()
}
return p
end
procedure findStart(p)
if \p[r := !*p][c := !*p[r]] = 1 then return Pos(r,c)
end
procedure solvePuzzle(puzzle)
if path := \best then {
repeat {
loc := path.getLoc()
puzzle[loc.r][loc.c] := path.getVal()
path := \path.getParent() | break
}
return puzzle
}
end
class QMouse(puzzle, loc, parent, val)
method getVal(); return val; end method getLoc(); return loc; end method getParent(); return parent; end method atEnd(); return (nCells = val, puzzle[loc.r,loc.c] = (val|0)); end method visit(r,c); return (/best, validPos(r,c), Pos(r,c)); end
method validPos(r,c)
v := val+1 # number we're looking for
xv := puzzle[r,c] | fail
if (xv ~= 0) & (xv != v) then fail
if xv = (0|v) then {
ancestor := self
while xl := (ancestor := \ancestor.getParent()).getLoc() do
if (xl.r = r) & (xl.c = c) then fail
return
}
end
initially
val := val+1 if atEnd() then return best := self QMouse(puzzle, visit(loc.r-1,loc.c) , self, val) # North QMouse(puzzle, visit(loc.r, loc.c+1), self, val) # East QMouse(puzzle, visit(loc.r+1,loc.c), self, val) # South QMouse(puzzle, visit(loc.r, loc.c-1), self, val) # West
end</lang>
- Output:
Sample runs
->numbrix <numbrix1.in
Input with 81 cells:
_ _ _ _ _ _ _ _ _
_ _ 46 45 _ 55 74 _ _
_ 38 _ _ 43 _ _ 78 _
_ 35 _ _ _ _ _ 71 _
_ _ 33 _ _ _ 59 _ _
_ 17 _ _ _ _ _ 67 _
_ 18 _ _ 11 _ _ 64 _
_ _ 24 21 _ 1 2 _ _
_ _ _ _ _ _ _ _ _
Output with 81 cells:
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
->numbrix <numbrix2.in
Input with 81 cells:
_ _ _ _ _ _ _ _ _
_ 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 _
_ _ _ _ _ _ _ _ _
Output with 81 cells:
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
->
Perl 6
Using the Warnsdorff solver from Solve_a_Hidato_puzzle: <lang perl6>my @adjacent = [-1, 0],
[ 0, -1], [ 0, 1],
[ 1, 0];
solveboard q:to/END/;
__ __ __ __ __ __ __ __ __
__ __ 46 45 __ 55 74 __ __
__ 38 __ __ 43 __ __ 78 __
__ 35 __ __ __ __ __ 71 __
__ __ 33 __ __ __ 59 __ __
__ 17 __ __ __ __ __ 67 __
__ 18 __ __ 11 __ __ 64 __
__ __ 24 21 __ 1 2 __ __
__ __ __ __ __ __ __ __ __
END</lang>
- Output:
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 1275 tries
And
<lang perl6>solveboard q:to/END/;
0 0 0 0 0 0 0 0 0 0 11 12 15 18 21 62 61 0 0 6 0 0 0 0 0 60 0 0 33 0 0 0 0 0 57 0 0 32 0 0 0 0 0 56 0 0 37 0 1 0 0 0 73 0 0 38 0 0 0 0 0 72 0 0 43 44 47 48 51 76 77 0 0 0 0 0 0 0 0 0 0
END</lang>
- Output:
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 4631 tries
Oddly, reversing the tiebreaker rule that makes hidato run twice as fast causes this last example to run four times slower. Go figure...
Phix
<lang Phix>sequence board, knownx, knowny
integer size, limit, nchars, tries string fmt, blank
constant ROW = 1, COL = 2 constant moves = {{-1,0},{0,-1},{0,1},{1,0}}
function onboard(integer row, integer col)
return row>=1 and row<=size and col>=nchars and col<=nchars*size
end function
function solve(integer row, integer col, integer n) integer nrow, ncol
tries+= 1
if n>limit then return 1 end if
if knownx[n] then
for move=1 to length(moves) do
nrow = row+moves[move][ROW]
ncol = col+moves[move][COL]*nchars
if nrow = knownx[n]
and ncol = knowny[n] then
if solve(nrow,ncol,n+1) then return 1 end if
exit
end if
end for
return 0
end if
sequence wmoves = {}
for move=1 to length(moves) do
nrow = row+moves[move][ROW]
ncol = col+moves[move][COL]*nchars
if onboard(nrow,ncol)
and board[nrow][ncol]='.' then
board[nrow][ncol-nchars+1..ncol] = sprintf(fmt,n)
if solve(nrow,ncol,n+1) then return 1 end if
board[nrow][ncol-nchars+1..ncol] = blank
end if
end for
return 0
end function
procedure Numbrix(sequence s) integer y, ch, ch2, k atom t0 = time()
s = split(s,'\n')
size = length(s)
limit = size*size
nchars = length(sprintf(" %d",limit))
fmt = sprintf(" %%%dd",nchars-1)
blank = repeat('.',nchars)
board = repeat(repeat(' ',size*nchars),size)
knownx = repeat(0,limit)
knowny = repeat(0,limit)
for x=1 to size do
for y=nchars to size*nchars by nchars do
ch = s[x][y]
if ch!='.' then
k = ch-'0'
ch2 = s[x][y-1]
if ch2!=' ' then
k += (ch2-'0')*10
board[x][y-1] = ch2
end if
knownx[k] = x
knowny[k] = y
end if
board[x][y] = ch
end for
end for
tries = 0
if solve(knownx[1],knowny[1],2) then
puts(1,join(board,"\n"))
printf(1,"\nsolution found in %d tries (%3.2fs)\n",{tries,time()-t0})
else
puts(1,"no solutions found\n")
end if
end procedure
constant board1 = """
. . . . . . . . . . . 46 45 . 55 74 . . . 38 . . 43 . . 78 . . 35 . . . . . 71 . . . 33 . . . 59 . . . 17 . . . . . 67 . . 18 . . 11 . . 64 . . . 24 21 . 1 2 . . . . . . . . . . ."""
Numbrix(board1)
constant board2 = """
. . . . . . . . . . 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 . . . . . . . . . ."""
Numbrix(board2)</lang>
- Output:
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 solution found in 580 tries (0.00s) 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 solution found in 334 tries (0.00s)
Racket
This is a general "Hidato" style solver (which is why there is a search for a 0 start point (which supports Hopido). There is already a Racket implementation of Hidato, so to allow a variety of approaches to be demonstrated, the main library for this set of problems is here.
hidato-family-solver.rkt
<lang racket>#lang racket
- Used in my solutions of
- "Solve a Hidato Puzzle"
- "Solve a Holy Knights Tour"
- "Solve a Numbrix Puzzle"
- "Solve a Hopido Puzzle"
- As well as the solver being common, the solution renderer and input formats are common
(provide
;; Input: list of neighbour offsets ;; Output: a solver function: ;; Input: a puzzle ;; Output: either the solved puzzle or #f if impossible solve-hidato-family ;; Input: puzzle ;; optional minimum cell width ;; Output: a pretty string that can be printed puzzle->string)
- Cell values are
- zero? - unvisited
- positive? - nth visitied
- else - unvisitable. In the puzzle layout, it's a _. In the hash it's a -1, so we can care less
- about number type checking.
- A puzzle is a sequence of sequences of cell values
- We work with a puzzle as a hash keyed on (cons row-num col-num)
- Take a puzzle and get a working hash of it
(define (puzzle->hash p)
(for*/hash
(((r row-num) (in-parallel p (in-naturals)))
((v col-num) (in-parallel r (in-naturals)))
#:when (integer? v))
(values (cons row-num col-num) v)))
- Takes a hash and recreates a vector of vectors puzzle
(define (hash->puzzle h# (blank '_))
(define keys (hash-keys h#))
(define n-rows (add1 (car (argmax car keys))))
(define n-cols (add1 (cdr (argmax cdr keys))))
(for/vector #:length n-rows ((r n-rows))
(for/vector #:length n-cols ((c n-cols))
(hash-ref h# (cons r c) blank))))
- See "provide" section for description
(define (puzzle->string p (w #f))
(match p
[#f "unsolved"]
[(? sequence? s)
(define (max-n-digits p)
(and p (add1 (order-of-magnitude (* (vector-length p) (vector-length (vector-ref p 0)))))))
(define min-width (or w (max-n-digits p)))
(string-join
(for/list ((r s))
(string-join
(for/list ((c r)) (~a c #:align 'right #:min-width min-width))
" "))
"\n")]))
(define ((solve-hidato-family neighbour-offsets) board)
(define board# (puzzle->hash board))
;; reverse mapping, will only take note of positive values
(define targets# (for/hash ([(k v) (in-hash board#)] #:when (positive? v)) (values v k)))
(define (neighbours r.c)
(for/list ((r+.c+ neighbour-offsets))
(match-define (list r+ c+) r+.c+)
(match-define (cons r c ) r.c)
(cons (+ r r+) (+ c c+))))
;; Count the moves, rather than check for "no more zeros" in puzzle
(define last-move (length (filter number? (hash-values board#))))
;; Depth first solution of the puzzle (we have to go deep, it's where the solutions are!
(define (inr-solve-pzl b# move r.c)
(cond
[(= move last-move) b#] ; no moves needed, so solved
[else
(define m++ (add1 move))
(for*/or ; check each neighbour as an option
((r.c+ (in-list (neighbours r.c)))
#:when (equal? (hash-ref targets# move r.c) r.c) ; we're where we should be!
#:when (match (hash-ref b# r.c+ -1) (0 #t) ((== m++) #t) (_ #f)))
(inr-solve-pzl (hash-set b# r.c+ m++) m++ r.c+))]))
(define (solution-starting-at n)
(define start-r.c (for/first (((k v) (in-hash board#)) #:when (= n v)) k))
(and start-r.c (inr-solve-pzl board# n start-r.c)))
(define sltn
(cond [(solution-starting-at 1) => values]
;; next clause starts from 0 for hopido
[(solution-starting-at 0) => values]))
(and sltn (hash->puzzle sltn)))</lang>
<lang racket>#lang racket (require "hidato-family-solver.rkt")
(define von-neumann-neighbour-offsets
'((+1 0) (-1 0) (0 +1) (0 -1)))
(define solve-numbrix (solve-hidato-family von-neumann-neighbour-offsets))
(displayln
(puzzle->string
(solve-numbrix
#(#(0 0 0 0 0 0 0 0 0)
#(0 0 46 45 0 55 74 0 0)
#(0 38 0 0 43 0 0 78 0)
#(0 35 0 0 0 0 0 71 0)
#(0 0 33 0 0 0 59 0 0)
#(0 17 0 0 0 0 0 67 0)
#(0 18 0 0 11 0 0 64 0)
#(0 0 24 21 0 1 2 0 0)
#(0 0 0 0 0 0 0 0 0)))))
(newline)
(displayln
(puzzle->string
(solve-numbrix
#(#(0 0 0 0 0 0 0 0 0)
#(0 11 12 15 18 21 62 61 0)
#(0 6 0 0 0 0 0 60 0)
#(0 33 0 0 0 0 0 57 0)
#(0 32 0 0 0 0 0 56 0)
#(0 37 0 1 0 0 0 73 0)
#(0 38 0 0 0 0 0 72 0)
#(0 43 44 47 48 51 76 77 0)
#(0 0 0 0 0 0 0 0 0)))))</lang>
- Output:
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 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
REXX
This solution is essentially same as the (REXX) Hidato puzzle solver.
Programming note: the coördinates for the cells used are the same as an X×Y grid, that is, the bottom left-most cell is (1,1) and the tenth cell on row 2 is (2,10). <lang rexx>/*REXX program solves a Numbrix (R) puzzle, displays puzzle & solution.*/ maxr=0; maxc=0; maxx=0; minr=9e9; minc=9e9; minx=9e9; cells=0; @.= parse arg xxx; PZ='Numbrix puzzle' /*get cell definitions from C.L. */ xxx=translate(xxx, , "/\;:_", ',') /*also allow other chars as comma*/
do while xxx\=; parse var xxx r c marks ',' xxx
do while marks\=; _=@.r.c
parse var marks x marks
if datatype(x,'N') then x=abs(x/1) /*normalize X*/
minr=min(minr,r); maxr=max(maxr,r)
minc=min(minc,c); maxc=max(maxc,c)
if x==1 then do; !r=r; !c=c; end /*start cell.*/
if _\== then call err "cell at" r c 'is already occupied with:' _
@.r.c=x; c=c+1; cells=cells+1 /*assign mark*/
if x==. then iterate /*hole? Skip.*/
if \datatype(x,'W') then call err 'illegal marker specified:' x
minx=min(minx,x); maxx=max(maxx,x) /*min & max X*/
end /*while marks¬= */
end /*while xxx ¬= */
call showGrid /* [↓] used for making fast moves*/ Nr = '0 1 0 -1 -1 1 1 -1' /*possible row for the next move.*/ Nc = '1 0 -1 0 1 -1 1 -1' /* " col " " " " */ pMoves=words(Nr) -4*(left(PZ,1)=='N') /*is this to be a Numbrix puzzle?*/
do i=1 for pMoves; Nr.i=word(Nr,i); Nc.i=word(Nc,i); end /*fast moves*/
if \next(2,!r,!c) then call err 'No solution possible for this' PZ"." say; say 'A solution for the' PZ "exists."; say; call showGrid exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────ERR subroutine──────────────────────*/ err: say; say '***error!*** (from' PZ"): " arg(1); say; exit 13 /*──────────────────────────────────NEXT subroutine─────────────────────*/ next: procedure expose @. Nr. Nc. cells pMoves; parse arg #,r,c; ##=#+1
do t=1 for pMoves /* [↓] try some moves.*/
parse value r+Nr.t c+Nc.t with nr nc /*next move coördinates*/
if @.nr.nc==. then do; @.nr.nc=# /*a move.*/
if #==cells then return 1 /*last 1?*/
if next(##,nr,nc) then return 1
@.nr.nc=. /*undo the above move. */
iterate /*go & try another move*/
end
if @.nr.nc==# then do /*is this a fill-in ? */
if #==cells then return 1 /*last 1.*/
if next(##,nr,nc) then return 1 /*fill-in*/
end
end /*t*/
return 0 /*This ain't working. */ /*──────────────────────────────────SHOWGRID subroutine─────────────────*/ showGrid: if maxr<1 | maxc<1 then call err 'no legal cell was specified.' if minx<1 then call err 'no 1 was specified for the puzzle start' w=length(cells); do r=maxr to minr by -1; _=
do c=minc to maxc; _=_ right(@.r.c,w); end /*c*/
say _
end /*r*/
say; return</lang>
- Output:
when using the input of
1 1 . . . . . . . . ./2 1 . . 24 21 . 1 2 . ./3 1 . 18 . . 11 . . 64 ./4 1 . 17 . . . . . 67 ./5 1 . . 33 . . . 59 . ./6 1 . 35 . . . . . 71 ./7 1 . 38 . . 43 . . 78 ./8 1 . . 46 45 . 55 74 . ./9 1 . . . . . . . . .
. . . . . . . . . . . 46 45 . 55 74 . . . 38 . . 43 . . 78 . . 35 . . . . . 71 . . . 33 . . . 59 . . . 17 . . . . . 67 . . 18 . . 11 . . 64 . . . 24 21 . 1 2 . . . . . . . . . . . A solution for the Numbrix puzzle exists. 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
- Output:
when using the input of
1 1 . . . . . . . . .\2 1 . 43 44 47 48 51 76 77 .\3 1 . 38 . . . . . 72 .\4 1 . 37 . 1 . . . 73 .\5 1 . 32 . . . . . 56 .\6 1 . 33 . . . . . 57 .\7 1 . 6 . . . . . 60 .\8 1 . 11 12 15 18 21 62 61 .\9 1 . . . . . . . . .
. . . . . . . . . . 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 . . . . . . . . . . A solution for the Numbrix puzzle exists. 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
Ruby
This solution uses HLPsolver from here <lang ruby>require 'HLPsolver'
ADJACENT = [[-1, 0], [0, -1], [0, 1], [1, 0]]
board1 = <<EOS
0 0 0 0 0 0 0 0 0 0 0 46 45 0 55 74 0 0 0 38 0 0 43 0 0 78 0 0 35 0 0 0 0 0 71 0 0 0 33 0 0 0 59 0 0 0 17 0 0 0 0 0 67 0 0 18 0 0 11 0 0 64 0 0 0 24 21 0 1 2 0 0 0 0 0 0 0 0 0 0 0
EOS HLPsolver.new(board1).solve
board2 = <<EOS
0 0 0 0 0 0 0 0 0 0 11 12 15 18 21 62 61 0 0 6 0 0 0 0 0 60 0 0 33 0 0 0 0 0 57 0 0 32 0 0 0 0 0 56 0 0 37 0 1 0 0 0 73 0 0 38 0 0 0 0 0 72 0 0 43 44 47 48 51 76 77 0 0 0 0 0 0 0 0 0 0
EOS HLPsolver.new(board2).solve</lang> Which produces:
Problem: 0 0 0 0 0 0 0 0 0 0 0 46 45 0 55 74 0 0 0 38 0 0 43 0 0 78 0 0 35 0 0 0 0 0 71 0 0 0 33 0 0 0 59 0 0 0 17 0 0 0 0 0 67 0 0 18 0 0 11 0 0 64 0 0 0 24 21 0 1 2 0 0 0 0 0 0 0 0 0 0 0 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 Problem: 0 0 0 0 0 0 0 0 0 0 11 12 15 18 21 62 61 0 0 6 0 0 0 0 0 60 0 0 33 0 0 0 0 0 57 0 0 32 0 0 0 0 0 56 0 0 37 0 1 0 0 0 73 0 0 38 0 0 0 0 0 72 0 0 43 44 47 48 51 76 77 0 0 0 0 0 0 0 0 0 0 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
Tcl
Following loosely the structure of Solve_a_Hidato_puzzle#Tcl.
<lang Tcl># Loop over adjacent pairs in a list.
- Example:
- % eachpair {a b} {1 2 3} {puts $a $b}
- 1 2
- 2 3
proc eachpair {varNames ls script} {
if {[lassign $varNames _i _j] ne ""} {
return -code error "Must supply exactly two arguments"
}
tailcall foreach $_i [lrange $ls 0 end-1] $_j [lrange $ls 1 end] $script
}
namespace eval numbrix {
namespace path {::tcl::mathop ::tcl::mathfunc}
proc parse {txt} {
set map [split [string trim $txt] \n]
}
proc print {map} {
join [lmap row $map {
join [lmap val $row {
format %2d $val
}] " "
}] \n
}
proc mark {map x y i} {
lset map $x $y $i
}
proc moves {x y} {
foreach {dx dy} {
0 1
-1 0 1 0
0 -1
} {
lappend r [+ $dx $x] [+ $dy $y]
}
return $r
}
proc rmap {map} { ;# generate a reverse map in a dict {val {x y} ..}
set rmap {}
set h [llength $map]
set w [llength [lindex $map 0]]
set x $w
while {[incr x -1]>=0} {
set y $h
while {[incr y -1]>=0} {
set i [lindex $map $x $y]
if {$i} {
dict set rmap [lindex $map $x $y] [list $x $y]
}
}
}
return $rmap
}
proc gaps {rmap} { ;# list all the gaps to be filled
set known [lsort -integer [dict keys $rmap]]
set gaps {}
eachpair {i j} $known {
if {$j > $i+1} {
lappend gaps $i $j
}
}
return $gaps
}
proc fixgaps {map rmap gaps} { ;# add a "tail" gap if needed
set w [llength $map]
set h [llength [lindex $map 0]]
set size [* $h $w]
set max [max {*}[dict keys $rmap]]
if {$max ne $size} {
lappend gaps $max Inf
}
return $gaps
}
proc paths {map x0 y0 n} { ;# generate all the maps with a single path filled legally
if {$n == 0} {return [list $map]}
set i [lindex $map $x0 $y0]
set paths {}
foreach {x y} [moves $x0 $y0] {
set j [lindex $map $x $y]
if {$j eq ""} {
continue
} elseif {$j == 0 && $n == $n+1} {
return [list [mark $map $x $y [+ $i 1]]]
} elseif {$j == $i+1} {
lappend paths $map
continue
} elseif {$j || ($n == 1)} {
continue
} else {
lappend paths {*}[
paths [
mark $map $x $y [+ $i 1]
] $x $y [- $n 1]
]
}
}
return $paths
}
proc solve {map} {
# fixpoint map
while 1 { ;# first we iteratively fill in paths with distinct solutions
set rmap [rmap $map]
set gaps [gaps $rmap]
set gaps [fixgaps $map $rmap $gaps]
if {$gaps eq ""} {
return $map
}
set oldmap $map
foreach {i j} $gaps {
lassign [dict get $rmap $i] x0 y0
set n [- $j $i]
set paths [paths $map $x0 $y0 $n]
if {$paths eq ""} {
return ""
} elseif {[llength $paths] == 1} {
#puts "solved $i..$j"
#puts [print $map]
set map [lindex $paths 0]
}
;# we could intersect the paths to maybe get some tiles
}
if {$map eq $oldmap} {
break
}
}
#puts "unique paths exhausted - going DFS"
try { ;# for any left over paths, go DFS
;# we might want to sort the gaps first
foreach {i j} $gaps {
lassign [dict get $rmap $i] x0 y0
set n [- $j $i]
set paths [paths $map $x0 $y0 $n]
foreach path $paths {
#puts "recursing on $i..$j"
set sol [solve $path]
if {$sol ne ""} {
return $sol
}
}
}
}
}
namespace export {[a-z]*}
namespace ensemble create
}
set puzzles {
{
0 0 0 0 0 0 0 0 0
0 0 46 45 0 55 74 0 0
0 38 0 0 43 0 0 78 0
0 35 0 0 0 0 0 71 0
0 0 33 0 0 0 59 0 0
0 17 0 0 0 0 0 67 0
0 18 0 0 11 0 0 64 0
0 0 24 21 0 1 2 0 0
0 0 0 0 0 0 0 0 0
}
{
0 0 0 0 0 0 0 0 0
0 11 12 15 18 21 62 61 0
0 6 0 0 0 0 0 60 0
0 33 0 0 0 0 0 57 0
0 32 0 0 0 0 0 56 0
0 37 0 1 0 0 0 73 0
0 38 0 0 0 0 0 72 0
0 43 44 47 48 51 76 77 0
0 0 0 0 0 0 0 0 0
}
}
foreach puzzle $puzzles {
set map [numbrix parse $puzzle]
puts "\n== Puzzle [incr i] =="
puts [numbrix print $map]
set sol [numbrix solve $map]
if {$sol ne ""} {
puts "\n== Solution $i =="
puts [numbrix print $sol]
} else {
puts "\n== No Solution for Puzzle $i =="
}
}</lang>
- Output:
== Puzzle 1 == 0 0 0 0 0 0 0 0 0 0 0 46 45 0 55 74 0 0 0 38 0 0 43 0 0 78 0 0 35 0 0 0 0 0 71 0 0 0 33 0 0 0 59 0 0 0 17 0 0 0 0 0 67 0 0 18 0 0 11 0 0 64 0 0 0 24 21 0 1 2 0 0 0 0 0 0 0 0 0 0 0 == Solution 1 == 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 == Puzzle 2 == 0 0 0 0 0 0 0 0 0 0 11 12 15 18 21 62 61 0 0 6 0 0 0 0 0 60 0 0 33 0 0 0 0 0 57 0 0 32 0 0 0 0 0 56 0 0 37 0 1 0 0 0 73 0 0 38 0 0 0 0 0 72 0 0 43 44 47 48 51 76 77 0 0 0 0 0 0 0 0 0 0 == Solution 2 == 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
zkl
This code solves Hidato, Hopido and Numbrix puzzles. <lang zkl> // Solve Hidato/Hopido/Numbrix puzzles class Puzzle{ // hold info concerning this puzzle
var board, nrows,ncols, cells,
start, // (r,c) where 1 is located, Void if no 1
terminated, // if board holds highest numbered cell
given, // all the pre-loaded cells
adj, // a list of (r,c) that are valid next cells
;
fcn print_board{
d:=D(-1," ", 0,"__");
foreach r in (board){
r.pump(String,'wrap(c){ "%2s ".fmt(d.find(c,c)) }).println();
}
}
fcn init(s,adjacent){
adj=adjacent;
lines:=s.split("\n");
ncols,nrows=lines[0].split().len(),lines.len();
board=nrows.pump(List(), ncols.pump(List(),-1).copy);
given,start=List(),Void;
cells,terminated=0,True;
foreach r,row in (lines.enumerate()){
foreach c,cell in (row.split().enumerate()){ if(cell=="X") continue; // X == not in play, leave at -1 cells+=1; val:=cell.toInt(); board[r][c]=val; given.append(val); if(val==1) start=T(r,c); }
}
println("Number of cells = ",cells);
if(not given.holds(cells)){ given.append(cells); terminated=False; }
given=given.filter().sort();
}
fcn solve{ //-->Bool
if(start) return(_solve(start.xplode()));
foreach r,c in (nrows,ncols){
if(board[r][c]==0 and _solve(r,c)) return(True);
}
False
}
fcn [private] _solve(r,c,n=1, next=0){
if(n>given[-1]) return(True);
if(not ( (0<=r<nrows) and (0<=c<ncols) )) return(False);
if(board[r][c] and board[r][c]!=n) return(False);
if(terminated and board[r][c]==0 and given[next]==n) return(False);
back:=0;
if(board[r][c]==n){ next+=1; back=n; }
board[r][c]=n;
foreach i,j in (adj){ if(self.fcn(r+i,c+j,n+1, next)) return(True) }
board[r][c]=back;
False
}
} // Puzzle</lang> <lang zkl>hi1:= // 0==empty cell, X==not a cell
- <<<
"0 0 0 0 0 0 0 0 0
0 0 46 45 0 55 74 0 0 0 38 0 0 43 0 0 78 0 0 35 0 0 0 0 0 71 0 0 0 33 0 0 0 59 0 0 0 17 0 0 0 0 0 67 0 0 18 0 0 11 0 0 64 0 0 0 24 21 0 1 2 0 0 0 0 0 0 0 0 0 0 0";
- <<<
hi2:= // 0==empty cell, X==not a cell
- <<<
"0 0 0 0 0 0 0 0 0
0 11 12 15 18 21 62 61 0 0 6 0 0 0 0 0 60 0 0 33 0 0 0 0 0 57 0 0 32 0 0 0 0 0 56 0 0 37 0 1 0 0 0 73 0 0 38 0 0 0 0 0 72 0 0 43 44 47 48 51 76 77 0 0 0 0 0 0 0 0 0 0";
- <<<
adjacent:=T( T(-1,0),
T( 0,-1), T( 0,1),
T( 1,0) );
foreach hi in (T(hi1,hi2)){
puzzle:=Puzzle(hi); puzzle.adjacent=adjacent; puzzle.print_board(); puzzle.solve(); println(); puzzle.print_board(); println();
}</lang>
- Output:
Number of cells = 81 __ __ __ __ __ __ __ __ __ __ __ 46 45 __ 55 74 __ __ __ 38 __ __ 43 __ __ 78 __ __ 35 __ __ __ __ __ 71 __ __ __ 33 __ __ __ 59 __ __ __ 17 __ __ __ __ __ 67 __ __ 18 __ __ 11 __ __ 64 __ __ __ 24 21 __ 1 2 __ __ __ __ __ __ __ __ __ __ __ 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 Number of cells = 81 __ __ __ __ __ __ __ __ __ __ 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 __ __ __ __ __ __ __ __ __ __ 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