An HMM with N observations can also be modeled as a bayesian network with 2N nodes (N nodes for the hidden states, and N nodes for the observation.

Once modeled as a Bayesian Network, it is possible to answer any query (question about unobserved nodes) using any available/desired combination of evidence (observed nodes).

I’m attaching a photo of using Samiam, a bayesian network solver, to get the MAP solution for the biased-coin flipping problem. It is also possible to use EM or other (even approximated) solutions as explained in the tutorial.