Make a picture into a sliding puzzle
Mathematica, 246 bytes
ImageAssemble@(n=Nest)[k=RandomInteger;q=Reverse;({t,r}=1~k~2;q[o=n[q/@#&amp;,#,r]&amp;@*(n[#&amp;,#,t]&amp;)])[o@#/.{a___,b:_~RepeatedNull~k[Position[o@#,i][[1,2]]-1],i,c___}:&gt;{a,i,b,c}]&amp;,MapAt[(i=#~ImageAdd~1)&amp;,#~ImagePartition~Scaled[1/#2],{1,#2}~k~2],#3]&amp;

Anonymous function. Contains U+F3C7, corresponding to Mathematica's Transpose operator. This function takes an Image object and returns an Image object.
Sample Animation, with n=16 and r=100
After 5000 iterations:
(click image for larger version)
Explanation
Initialization
n=Nest

Store the Nest function (repeating operation) in n.
k=RandomInteger;q=Reverse;

Store the RandomInteger function in k, and Reverse function in q.
Splitting the image
#~ImagePartition~Scaled[1/#2]

Partition the input image into (second input)^2 tiles.
{1,#2}~k~2

Generate two RandomIntegers between 1 and the second input. This selects a random tile.
MapAt[(i=#~ImageAdd~1)&amp;, ..., {1,#2}~k~2]

Make that tile white. Store it in i.
Moving Tiles
{t,r}=1~k~2

Generate two random integers from 0 to 1, and store them in t and r, respectively. This randomly selects direction.
o=n[q/@#&amp;,#,r]&amp;@*(n[#&amp;,#,t]&amp;)

Define function o: the composition of

a function transposing the input t times.
a function reversing each row r times.

o@#
Apply o to the input.
Position[o@#,i][[1,2]]

Find the column of i (white image).
k[ ... -1]

Subtract one and find a random integer between 0 and that number. This randomly chooses how many tiles to move.
o@#/.{a___,b:_~RepeatedNull~ ... ,i,c___}:&gt;{a,i,b,c}

When the said number of tiles occur before an i (white image), switch their places.
(... q[o= ... ])[ ... ]

Reverse the o function and apply that to the result of above operation. This un-reverses and un-transposes the image.
Looping and Image Assembly
(n=Nest)[ ... ,#3]

Repeat the above process (third input) times.
ImageAssemble@

Put the images together.