What type of reinforcement learning can I do restricted to ~200MB on an average smartphone?
I skimmed through your question and understood that the state/action space is finite, so in this case, RL would be a good option for storage.

The most basic RL technique will keep track of a matrix Q &in; &#8477;s&times;a, where s is number of possible states, and a is number of possible actions. 

In addition to a small overhead of agent's parameters:  


&alpha; &in; [0,1] learning parameter
&gamma; &in; [0,1] discount rate, 
&epsilon; &in; [0,1]  exploration rate


If you have a total of 81 states and 10 actions, then your storage would be in the neighborhood of 850 double words.

If your AI will track different states per location, e.g. possible values 0 to 9 + a null, then your state space will grow to 11 * 81 = 968 and the final value matrix will be Q &in; &#8477;968&times;10 &asymp; 20Kb.

Update

I am terrible sorry, I made a terrible mistake in my calculations.
if you are to keep track of 11 possible values in 81 locations, then the correct number should be 1181&times; double word size, that is a big number. 

Of course, if this is Sudoku and you  and you are not considering illegal moves as possible states, then definitely this will be a way smaller number, but you will still keep track of an action space that is as big as the state space.

You might need to use function approximation instead, or some sort of action state space compression.

sorry