Does this mean that the implementation must actually choose C before displaying it digit by digit? Or would it (theoretically) be okay if the digits were chosen as they are being displayed (i.e. the second digit is not known to the program before the first has been shown)?

As my own attempt uses on the latter approach, I have to say it is acceptable. Others are free to disagree and discount my attempt. Here is how I justify it. Istarted out with this to fulfill the 'spec':

#! perl -slw
use strict;

$|++;

sub r{int rand pop}

my $n = pop;
my @c = map int rand 10,1..$n; 
my @x = (0) x $n;

for my $d ( 0 .. $n -1 ){ 
    map{ 
        $x[ $d + r( $n - $d ) ] = r( 10 );
        printf "\r@x";
        $x[ $d ] = $c[ $d ]
    }1..1e5
}
[download]

I then started golfing and here are the steps I went through:

-e"sub r{int rand(pop||10)};@c=map{r}1..($n=pop);for$d(0..$n-1){map{$x
+[$d+r($n-$d)]=r,print qq[@x\r]}1..1e5;$x[$d]=$c[$d]}"

-e"sub r{int rand(pop||10)};$n=pop;@c=map{r}1..$n;for$d(0..$n-1){map{$
+x[$d+r($n-$d)]=r,print qq[@x\r]}1..1e5;$x[$d]=$c[$d]}"

-e"$n=pop;for$d(0..$n-1){map{$x[$d+rand($n-$d)]=int(rand 10),print qq[
+@x\r]}1..1e5;}"

-e"for$d(0..($n=pop)-1){map{$x[$d+rand($n-$d)]=int(rand 10),print qq[@
+x\r]}1..1e5}"

-l15e"for$d(0..($n=pop)-1){map{$x[$d+rand($n-$d)]=int(rand 10),print @
+x}1..1e5}"

-l15e"for$d(0..($n=pop)-1){$x[$d+rand($n-$d)]=int(rand 10),print@x,for
++1..1e5}"

-l15e"for$d(0..($n=pop)-1){$x[$d+rand($n-$d)]=rand(10)&15,print@x,for+
+1..1e5}"

-l15e"for$d(0..($n=pop)-1){$x[$d+rand$n-$d]=rand(10)&15,print@x,for+1.
+.1e5}"
[download]

At the transition from step 2 to step 3, I notice that I had these 3 pieces of code:

1. @c=map{r}1..$n;

   Put random digits into @c.

2. $x[$d+r($n-$d)]=r

   put a random digits into $x[...].

3. $x[$d]=$c[$d]

   replace the random digit in @x with corresponding (random digit) from @c.

Which is equivalent to $tmp = val; $target = other value; $target = $tmp.

Eliminating the temporary value and intermediate steps is the essence of golf, so I conclude that step 3 above is logically equivalent to step 2. Others may wish they had thought of it...or condemn it as a step too far?