This isn't an answer, but it's too long for a comment...
Using that remaining-distance metric, you can certainly implement an A* search and it will give the correct result, but it will be extremely inefficient. The reason is that it's really a Dijkstra search disguised as A*. Worse than that, as Shawn notes, it's really a simple breadth-first search.
The reason it has decayed to Dijkstra is because your metric gives no clues as to which is the best direction to take through the state space. Each step from a particular intermediate state is just filling in one digit in one cell - precisely as cheap/costly as filling in any other possible digit/cell at that point and with no clue as to which successor states (with the same number of empty cells) are closer to a correct solution. All paths from that intermediate state to the solution are the same length, including the ones leading through illegal states to a broken solution.
This is legal in the sense that the distance metric is a lower bound to the remaining distance to a solution. But it's not just a lower bound, it's an exact distance. Your "perfect heuristic" isn't guiding the search towards the solution in any useful way beyond what Dijkstra could do.
The reason it has decayed to a breadth-first search is the same thing, but in terms of the weights of edges already traversed so far. Every path from the start to any intermediate state has the same number of edges and the same total cost (same number of cells filled in). Every edge effectively has weight one, and there are no short-cuts for Dijkstra to exploit.
In practice, Sodoku solvers usually use backtracking depth-first search with relatively cheap checks (if there are two of the same digit in any cell, row or block, this state is impossible as are all possible successor states) to avoid searching impossible parts of the search space. There's not much guidance you can get on which intermediate states are better without spending more on the heuristics and search algorithm than you gain by pruning the search tree further, and besides, backtracking search with that simple pruning is very fast.