Make a picture into a sliding puzzle

Question

Summary

The goal of this challenge is to create an undone image-version of a 15-puzzle / sliding puzzle also called taquin in french.

Details:

Given an input composed of:

• an image,
• an integer n,
• an other integer r,

your program, or function, or anything else that fits, must output the same image (i.e. same size and format) as the input, but that underwent the following process:

1. divide the image into n² rectangles,
2. remove one of those rectangles, randomly,
3. move a random number of contiguous rectangles from the line/column affected by point (2.) so the hole created is filled and another one is generated in this line/column. This number can be 0 if the blank is in a corner or an edge.

Repeat (3.) r times.

Clarifications:

• If you moved rectangles from the line in step (3.), you must move rectangles from the column the in the next repetition,
• if you moved rectangles left-to-right in a line-step, they must be moved right-to-left in the next line-step, same for top-to-bottom and bottom-to-top concerning columns,
• you may assume that n will be chosen so it divides the lengths of the sides of the picture.

A last point:

An animated .gif showing the whole process are very welcomed.

I propose to use the following picture (which is 1024x768), with n=16 and r=100 as a model, you can use any other picture (as long as it's relevant and complies with SE's rules, of course).

Note that standards loopholes policies apply.

This is code-golf, so the shorter submission wins !

Since an example was requested, here is one, made "by hand", with n=4 and r=1

Steps 1 and 2

Step 3 : line-wise, 2 rectangles to the left

Answer 1

Mathematica, 246 bytes

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

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)&, ..., {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/@#&,#,r]&@*(n[#&,#,t]&)

Define function o: the composition of

1. a function transposing the input t times.
2. 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___}:>{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.