If $\gcd(a,n)=g>1$ then if $g\nmid b$ there's clearly no solution. Otherwise write $a=g\alpha$, $b=g\beta$, $n=g\nu$, so
$$
a^x\equiv b\pmod{n} \iff g^{x-1}\alpha^x\equiv \beta \pmod{\nu}
$$
Since $\gcd(\alpha,\nu)=1$, $\alpha$ has an inverse mod $\nu$. Divide through by $\alpha$ to get
$$(g\alpha)^{x-1} = a^{x-1} \equiv \beta\alpha^{-1} \pmod{\nu}$$
If $\gcd(a,\nu)=1$ then you can use your preferred algorithm for the relatively prime case, otherwise repeat this reduction.
Example 1: $6^x \equiv 4 \pmod{44}$
Using $3\cdot 15 \equiv 1 \pmod{22}$ and $3\cdot 4 \equiv 1 \pmod{11}$:
$$
\begin{align}
2^{x-1}3^x & \equiv 2 \pmod{22} \\
6^{x-1} & \equiv 2\cdot 15 \equiv 8 \pmod{22} \\
2^{x-2}3^{x-1} & \equiv 4 \pmod{11} \\
6^{x-2} & \equiv 4\cdot4 \equiv 5 \pmod{11} \\
\end{align}
$$
Now $\gcd(6,11)=1$, so if you can solve this you might get $x-2=6$, $x=8$.
Example 2: $6^x \equiv 2 \pmod{44}$
Starting as in Example 1:
$$
\begin{align}
2^{x-1}3^x & \equiv 1 \pmod{22} \\
6^{x-1} & \equiv 2\cdot 15 \equiv 15 \pmod{22} \\
\end{align}
$$
and this has no solution since $\gcd(6,22) \nmid 15$.