Solution for $Xa + X^Tb = c$ where $X^TX = I$? There are three known $n\times1$ vectors: $a, b, c$, along with one unknown $n\times n$ matrix: $X$. I am only interested in the $n={2,3}$ cases. 
$X$ is $2\times 2$ or $3\times 3$ rotation matrix with an unusual domain specific constriant:


*

*$X^TX = XX^T = I$

*$Xa + X^Tb = c$
Is there a solution for $X$ in terms of $a,b,c$? Based on where the problem came from, I know there isn't always a solution, but I have stumped myself trying to figure out how to solve it when there is one.
I have tried working out the $2\times 2$ case element-wise, and arrived at the following, equally(?) difficult problem:
$X = \begin{bmatrix}x_{11} & x_{12} \\ -x_{12} & x_{11}\end{bmatrix}$
$\begin{bmatrix}a_1+b_1 & b_2-a_2 \\ a_2+b_2 & a_1-b_1\end{bmatrix}\begin{bmatrix}x_{11}\\x_{12}\end{bmatrix}=c$
$Ax = c$ where $x^Tx=1$
 A: As a beginning of a search for solutions, we can take norms of each side.  We then get
$$\|a\|^2 + \|b\|^2 + 2 b\cdot (X^2 a)=\|c\|^2,$$
which is enough to fix the angle between $b$ and $X^2 a$.
Similarly, multiplying through by $X$ and then dotting with $b$, we can conclude that
$$b\cdot (Xc)=\|b\|^2+b\cdot (X^2 a)=\|b\|^2+\frac{\|c\|^2-\|a\|^2-\|b\|^2}{2}=\frac{\|b\|^2+\|c\|^2-\|a\|^2}{2}.$$
Therefore, we know the angle that $b$ makes with $Xc$.  Similar calculations show us the angle that $a$ makes with $X^T c$.  In two dimensions, this is enough to find $X$ geometrically if it exists in most cases, and otherwise to say that there is no such solution.    The geometry is slightly more involved in 3 dimensions, and I'm not immediately sure if there is more useful information to be extracted through dot products to help.

Here is an approach for $\mathbb R^3$, inspired by Michael Renardy's answer.
Let us temporarily expand the problem to $Aa+Bb=c$, where $A,B\in O_n(\mathbb R)$.  Assuming that $|a|,|b|$, and $|c|$ satisfy the triangle inequality, we can find a solution, $(A_0,B_0)$.  However, the space of all solutions is $(MA_0,MB_0)$ where $Mc=c$ and $M\in O_n(\mathbb R)$.  Thus, we've reduced the problem to:
Given $A,B\in O_n(\mathbb R)$ and $c\in \mathbb R^n$, does there exist $X\in O_n(\mathbb R)$ such that $$Xc=c \quad \text{and} \quad I=AXBX.$$
Since $AX$ and $BX$ are inverses, they commute, and so $BXAX=I$ too.  Evaluating at $c$, we get 3 equations,
$$ Xc=c, \quad X(Bc)=A^Tc, \quad X(Ac)=B^Tc.$$
Assuming that $c, Ac, Bc$ span your space (which happens in $\mathbb R^3$ for most $(A,B,c)$-triples), this specifies a unique candidate $X$ to test to see if it actually satisfies the problem.
Explicitly, if $P$ is the matrix whose columns are $c,Ac, Bc$ respectively, and $Q$ is the matrix whose columns are $c, B^Tc, A^Tc$ respectively, then $X=QP^{-1}$.  We just need to check that $XX^T=I$ and $AXBX=I$. or see that these equations are violated.
A: \begin{equation}
Xa = \begin{bmatrix} a_1x_{1,1} + a_2x_{1,2}\\ a_1x_{2,1} + a_2x_{2,2}\\ 
 \end{bmatrix}
\end{equation}
and 
\begin{equation}
X^Tb = \begin{bmatrix} b_1x_{1,1} + b_2x_{2,1}\\ b_1x_{1,2} + b_2x_{1,2}\\ 
 \end{bmatrix}
\end{equation}
and 
\begin{equation}
Xa+X^Tb = \begin{bmatrix}a_1x_{1,1} + a_2x_{1,2} + b_1x_{1,1} + b_2x_{2,1}\\ a_1x_{2,1} + a_2x_{2,2}+ b_1x_{1,2} + b_2x_{2,2}\\ 
 \end{bmatrix} = \begin{bmatrix}(a_1+b_1)x_{1,1} + a_2x_{1,2} + b_2x_{2,1}\\ (a_2+b_2)x_{2,2} + a_1x_{2,1} + b_1x_{1,2}\\ 
 \end{bmatrix} = \begin{bmatrix}c_1 \\ c_2\\ 
 \end{bmatrix} 
\end{equation}
but $X$ is a rotation matrix gives us that 
\begin{equation}
Xa+X^Tb = \begin{bmatrix}(a_1+b_1)\cos\theta - a_2\sin\theta  + b_2\sin \theta \\ (a_2+b_2)\cos\theta  + a_1\sin\theta  - b_1\sin\theta\\ 
 \end{bmatrix} =  \begin{bmatrix}(a_1+b_1)\cos\theta +(b_2- a_2)\sin\theta  \\ (a_2+b_2)\cos\theta  + (a_1  - b_1)\sin\theta\\ 
 \end{bmatrix} 
\end{equation}
(if you only have $X^TX= I$ then you have to consider the extra case there $\sin \theta  \to -\sin \theta $; i.e. rotation composed with reflection. Notice that $X$ is a rotation implies $X^TX= I$!) and therefore that 
\begin{equation}
Xa+X^Tb =    \begin{bmatrix}(a_1+b_1)\cos\theta +(b_2- a_2)\sin\theta  \\ (a_2+b_2)\cos\theta  + (a_1  - b_1)\sin\theta\\ 
 \end{bmatrix} = \begin{bmatrix}c_1 \\ c_2\\ 
 \end{bmatrix} 
\end{equation}
and therefore (by using the triangle inequality) you don't have a solution if for example 
\begin{equation}
\frac{|(a_1+b_1)|}{\sqrt{2}}  +\frac{|(b_2- a_2)|}{\sqrt{2}} < |c_1|
\end{equation}
 and like wise for the second condition 
\begin{equation}
\frac{|(a_2+b_2)|}{\sqrt{2}}  +\frac{|(a_1- b_1)|}{\sqrt{2}} < |c_2|
\end{equation}
and you can probably come up with all kinds of other tests for failure, but here is the most general one:
An alternative/equivalent way to look at it is that you have an overdetermined system of 3 equations and 2 unknowns of the form 
\begin{equation}
\begin{array}
& ax & + & by & =& c_1\\
 cx & + & dy & =& c_2 \\
 x^2 & + & y^2 & =& 1 \\
\end{array}
\end{equation}
where $a = a_1+b_1$ , $b=a_2- b_2$, $c = a_2+b_2$, and $d = a_1- b_1$; which is highly unlikely to have solutions. 

Therefore you have solutions iff the solution to the system of
   equations \begin{equation} \begin{array} & ax & + & by & =& c_1 \\  cx
 & + & dy & =& c_2 \\ \end{array} \end{equation} also satisfies the
  condition $ x^2  +  y^2  = 1 $.

If you want to work out the $n=3$ case you can do the same exact thing but use the Euler angles; it will be long and tedious but you can probably get some kind of condition on the solutions. 
A: You can possibly try this as well. Note that the orthogonality requirement can be relaxed using Schur complement as $\begin{bmatrix}I&X\\X^\top & I \end{bmatrix} \succeq 0$. So, we have the following:
$$
\max_{X\in R^{n\times n}} ~~ \|c-Xa-X^\top b\|_2\\
\hspace{-3cm}\mbox{subject to}\\
~~~~~~~~~~~~\begin{bmatrix}I&X\\X^\top & I \end{bmatrix} \succeq 0.
$$
Note that if the solution to this convex problem $X^*$ does not satisfy $\|c-Xa-X^\top b\|^2_2=0$, there does not exist a solution to the original problem.
Hope this partial treatment helps. And, thanks to Aaron for pointing out an error earlier.
A: An obvious necessary condition is that |a|, |b| and |c| can be sides of a triangle. The two-dimensional case can be analyzed further geometrically. If the triangle inequalities are satisfied, there are vectors congruent to a and b which form a triangle with c. The condition you require is that these vectors can be obtained either by rotating a and b in opposite directions (if X is proper orthogonal, and in this case the bisector of the angle between a and b stays the same), or by reflection across some axis (if X is improper orthogonal).
A: You can solve the $n=2$ case relatively easily with complex numbers:
$a$, $b$ and $c$ can be represented by complex numbers and the rotation matrix by a complex number z with modulus 1.
So the equations are:
$$za+z^{-1}b=c$$ with $|z|=1$.
The equation is equivalent to $$az^2-cz+b=0$$
which you can solve immediately using the quadratic formula:
$$z=\frac{c\pm\sqrt{c^2-4ab}}{2a}.$$
Clearly we only have solution to the problem if $$|\frac{c+\sqrt{c^2-4ab}}{2a}|=1$$ or $$|\frac{c-\sqrt{c^2-4ab}}{2a}|=1.$$
We can analyse further to obtain simpler conditions for a solution to exist by taking the modulus which gives $(za+b/z)(\bar{a}/z+\bar{b}z)=|c|^2$ or $2\Re(\bar{a}b/z^2)=|c|^2-|a|^2-|b|^2$. The inequality $|\Re(z)|\leq|z|$ implies $||c|^2-|a|^2-|b|^2|\leq 2|a||b|$ which is equivalent to the triangle inequality holding for $|a|$, $|b|$ and $|c|$ which as Michael Renardy noted is obvious geometrically and is clearly a necessary condition for a solution to exist. However it is also a sufficient condition.
In fact if $\bar{a}b=re^{\mu}$ and we set $z=e^{i\theta}$ the equation reduces to $2\Re(re^{\mu-2\theta})=|c|^2-|a|^2-|b|^2$ or $2r\cos(\mu-2\theta)=|c|^2-|a|^2-|b|^2.$ or $\cos(\mu-2\theta)=(|c|^2-|a|^2-|b|^2)/(2|a||b|).$ and hence if the triangle inequality condition is satisfied we have $|\cos(\mu-2\theta)|\leq 1$ which gives us a solution for $\theta \in \mathbb{R}$ and hence the rotation $z=e^{i\theta}$.
