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

 A* search algorithm
 Solve a Holy Knight's tour
 Knight's tour
 N-queens problem
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Solve a Hopido puzzle
 Solve the no connection puzzle


 
#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");
}
 