Case 1:

 1  2  3  4
 5  6  7  0
 9 10 11  8
13 14 15 12

Case 2:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13  0 14 15

Case 3: I can't march up and down the square!

Case 4:

15 14 13 12
 0 11 10  9
 8  7  6  5
 4  3  2  1

Case 5:

15 14 13 12
11 10  0  9
 8  7  6  5
 4  3  2  1

Case 6:

15 14 13 12
11 10  9  0
 8  7  6  5
 4  3  2  1

Case 7:

15  0 13 12
11 14 10  9
 8  7  6  5
 4  3  2  1

Case 8:

15 14 13 12
11  7 10  9
 8  0  6  5
 4  3  2  1

Case 9:

15 14 13 12
11  7 10  9
 8  3  6  5
 4  0  2  1

Case 10: I can't march up and down the square!

Case 11:

 1  2  3  0
 4  5  6  7
 8  9 10 11
12 13 14 15

Case 12:

 4  1  2  3
 8  5  6  7
12  9 10 11
 0 13 14 15

Case 13: I can't march up and down the square!

Case 14:

 5  0  3  8
 2  9  1  6
13 10  7 15
 4 12 11 14