There are different ways of defining "legal".
In a comment, the OP posits that legal could mean
by legal I mean that for a 3x3x3 cube there are exactly 9 tiles with the same color, and there are 6 different colors.
In which case the existence of "legal" colorings not reachable by standard Rubik's cube moves is trivial: observe that a Rubik's cube move only sends
- Corner pieces to corner pieces
- Center pieces to center pieces
- Edge pieces to edge pieces
So if you peel of the Red center piece sticker and swap it with the sticker of a blue edge piece, you will still have 9 "red tiles", but no "red center tile", so it cannot be arrived at by a standard permutation.
Okay so perhaps you want to strengthen the condition on the tiles. May be we amend the definition of legal to be
A color configuration is legal if there are 6 total colors, each color has 9 tiles, and of the 9 tiles you have 1 center piece, 4 corner pieces, and 4 edge pieces.
This is still not sufficient to guarantee that the cube is solvable. One property of the standard Rubik's cube moves is that opposite centers can never be made adjacent. So take a solved standard cube, with (assuming) white being the top face, blue being the bottom face, and red being a side face. If you take an arbitrary edge sticker off the blue side, and swap it with the red edge sticker that is adjacent to the white face you've created an impossible cube, because the cube now has an edge face with white/blue, but white and blue centers can never be adjacent.
So okay, that is still a trivial impossibility. Perhaps we need to strengthen our definitions even more. The next natural assumption is then
In a solved cube there are 12 edges and 8 corners. Each edge has two colors. Each corner has 3. We say a color configuration is "legal" if it has 6 total colors, 9 tiles of each color, with 1 in the center, 4 on the edge, and 4 on the corner. Furthermore, we require that the color combinations for the edges and corners are in one-to-one correspondence with those available on a solved cube.
In fact, this turns out to be what I call the "take the cube apart and reassemble" definition. (You'll know what I mean if you've ever tried taking apart a Rubik's cube.)
In this situation there are still impossible configurations: for example, if you pry off one single edge piece and re-insert it "upside down". The proof that such configurations are impossible is more difficult, and requires learning some group theory. (See chapter 11 of this exposition.) But the fundamental idea behind the argument is same as the previous cases: one needs to find "algebraic invariants" which describe the configuration of the cube, and which values are left unchanged by the Rubik's cube moves. By constructing a configuration with a different value for the invariants compared to the solved cube, you obtain an example that can be demonstrated to not be solvable.
In the first example, the algebraic invariants are the "number of edge/center/corner tiles per color". In the second example, the algebraic invariants are "the number of edges shared by two given colors". For the third example, I invite you to read the linked PDF file.
Disclaimer: This is an old incomplete answer, now aged multiple years. I started this before I had any formal math education and I never came back to finish this.
To make our lives easier, we can separate the pieces by 3 types:
Edges (3 stickers)
Sides (2 stickers)
Centers (1 sticker)
Also note that im observing a cube with Yellow and Black( I call it White later on) colors for the top and bottom sides as my default color scheme.
(Other pieces follow Red, Blue, Orange, Green)
For the $3\times3\times3$ Rubik's cube, first we can solve for the middle parts.
We can conclude that if the color scheme is known, that all obscured centers can be determined if we have at least 2 neighbour ones.
This means we can peel off 4 centers if we keep 2 neighbour ones. This can be checked by playing with its own cube or simply by following the laws of legal positions and using something like a solver help you out. (This is because centers can't be really switched, but the pieces around them can so that it looks that way)
Then lets see how many stickers from the edge pieces can be obscured or peeled off, since any configuration of $n\times n\times n$ always has exactly 8 edges.
We can list them by the colors they contain:
(Red, Blue, Green, Orange, Yellow, White)
$$ R,G,Y $$
$$ R,G,W $$
$$ R,B,Y $$
$$ R,B,W $$
$$ O,G,Y $$
$$ O,G,W $$
$$ O,B,Y $$
$$ O,B,W $$
If you want to know how many stickers can be peeled off and still be able to identify each corner, you can ask yourself; How many stickers you can take so that when putting them back, you have only one possible way to do so?
I have found out the maximum number of 12 out of 24 stickers; by taking all R or O, then all B or G and finally all Y or W.
Here is an example:
$$ -,-,- $$
$$ -,-,W $$
$$ -,B,- $$
$$ -,B,W $$
$$ O,-,- $$
$$ O,-,W $$
$$ O,B,- $$
$$ O,B,W $$
Now by shuflling the order and rotation of all 8 edges in every way possible, there will be only one way to stick the removed stickers, thus you still can identify the pieces.
Now the Side pieces, which might be a bit tricky.
On the $3\times3\times3$ Rubik's cube, there are 12 Edge pieces:
$$ G,R $$
$$ R,B $$
$$ B,O $$
$$ O,G $$
$$ Y,G $$
$$ G,W $$
$$ W,B $$
$$ B,Y $$
$$ R,W $$
$$ W,O $$
$$ O,Y $$
$$ Y,R $$
Now you can try to do the same thing.
Firstly I tried to remove all White stickers, then it allows me to take one color from $Y,?$ pieces other than yellow, and after that nothing more can be taken without providing multiple solutions for the edges; so that was 5 stickers.
Then after other failed attempts, I found you can remove 6 stickers; one of each color so that there aren't multiple stickers of the same color standing without their second color, and I'm kinda sure it can't be done with more than 6 here.
If someone can do better here, please let me know.
So if I haven't made a mistake, for the $3\times3\times3$ Rubik's cube you can remove total of $12+6+4 = 22$ out of 54 stickers top (following the things I pointed out) without losing any information about the cube's states.
The $2\times2\times2$ Rubik's cube is made of only 8 edge pieces, so 12 out of 24 stickers can be removed here.
We can now try to generalize this to other $n\times n\times n$ cubes.
We now know that we can for;
$n=2$ take 12 out of 24
$n=3$ take 22 out of 54
For any $n\times n\times n$ cube, we always have 8 edges, so thats $+12$ obscured stickers.
For the side pieces, we have $n$ of each piece (sorted set of pieces):
$$ W,R $$
$$ W,B $$
$$ W,G $$
$$ W,O $$
$$ Y,R $$
$$ Y,B $$
$$ Y,G $$
$$ Y,O $$
$$ R,B $$
$$ R,G $$
$$ O,B $$
$$ O,G $$
There is nothing more to do here than apply the same thing I did in $3\times 3\times 3$ cube;
Remove 6 stickers, one of each color so that there aren't multiple stickers of the same color standing without their second color and do that for each new set of the side pieces.
This provides us with $6\times(n-2)$ pieces more to obscure.
Again, if you can do better with the sorted set I provided, please let me know.
So far then, the number of stickers we can obscure is: $$12+6\times(n-2)+C$$
Where $C$ is the number of "mobile" and "immobile" centers we can obscure, that appear after $n>3$ and have yet to be figured out.
(when $n=3$ then $c=4$ )
So now, the center pieces at $4\times 4\times 4$ cube and every other with $2k$ sides ($k>1$) are different than every $2k+1$ sided cubes;
The $2k+1$ like our standart $3\times3\times3$ cube have 6 "real centers" which are immobile and $4$ out of $6$ can be obscured, the rest one-sticker centers here are "mobile" and behave differently when being rotated.
Same goes for all of centers which are all "mobile" in $2k$ cubes.
How many of these mobile centers can be obscured? I would say for a starting bound, all of one color which is then:
$C = (n-2)^2$ for $n>3$
And gives us finally:
$$12+6\times(n-2)+(n-2)^2$$
Pieces we can surely obscure.
I haven't yet started checked if more can be obscured on these centers, but thats because its now end of the day and I don't have any more time, and now decided to post my progress so far.
I think you could take it from here to finish up the generalization and try to see if it is possible to obscure more than $(n-2)^2$ stickers using the color scheme and legal permutations, so maybe separate formulas for $2k$ and $2k+1$ can be found.
Update
Actually I don't think the mobile centers should provide us with any additional problems, thus we can take for $C$ that it is: $ = (n-2)^2 \times 4$ Since we need only 2 full center colors that will tell us the rest, most easily after solving the cube to its solved state.
Then we have: $$12+6\times(n-2)+4\times(n-2)^2$$
I have classes to be on early tomorrow morning now, so good night.
Edit: This should be computed and checked to make sure I haven't made
a mistake somewhere.
Best Answer
Imagine repainting the cube in state $B$ to make it look like $S$, and keep track of how you paint each piece. Now apply these repaintings of the individual pieces to the cube in state $A$. This gives you a new cube state $C$. Apply the cube-solving algorithm to $C$; the steps that turn $C$ into $S$ will also turn $A$ into $B$.