I have solved it by reduction to a graph exploration task.
Each vertex consists of three parameters (i, j, pr).
Where i, j denote number of card at the top of each pile and pr denotes previous state.  pr is also a "used"  array.  So,  if pr[N] [N] =none,  then impossible.  Otherwise  just recover answer using pr.  You can also have in your state additional parameter diff denotes difference between red and black cards.  I have used instead additional two arrays diff11 and diff2 denote difference between first i cards in first pile and in the second pile respectively.  There is an edge iff difference at the next step would be not greater than one (abs) ,  obviously.