Layout my tiles for me

Question

I'm retiling my kitchen with different coloured tiles. In fact, it's going to have at least 2 colours - and 26 colours as a maximum.

But, I'm fussy. I want this wall to look random, but sometimes random isn't random enough.

So, when I lay out my tiles, I don't want to have any the same colour next to each other in the 4 Cartesian directions. Diagonally adjacent is (of course) fine.

Acceptable:

┌───┐
│ A │
└───┘

┌───┬───┬───┐
│ A │ B │ A │
├───┼───┼───┤
│ B │ A │ B │
└───┴───┴───┘

┌───┬───┬───┐
│ A │ B │ C │
├───┼───┼───┤
│ C │ A │ B │
└───┴───┴───┘

Unacceptable:

┌───┬───┬───┐
│ A │ B │ A │
├───┼───┼───┤
│ A │ A │ B │
└───┴───┴───┘

┌───┬───┬───┐
│ A │ C │ C │
├───┼───┼───┤
│ C │ A │ B │
└───┴───┴───┘

Given input in the form A B N where A is the width, B is the height and N is the number of colours - an integer from 2 to 26 - you need to output a grid like so:

Input:

5 6 4

Example output:

A B C D A
B A D A C
A D C D A
B C B A B
D A D C A
B C A D C

The input will be given as a) 3 arguments to a function or b) as 3 separate input statements or b) as A B N. Input will always be valid.

All colours have to be used and all valid tilings have to have a non-zero probability of being generated.

This is code-golf so the shortest code wins.

Answer 1

Python 2, 151 149 bytes

from random import*
W,H,N=input()
L='x'*W
exec"M='';exec'M+=sample(set(map(chr,range(65,65+N)))-{L[len(M)],M[-1:]},1)[0];'*W;L=M;print' '.join(L);"*H

Takes input comma-separated via STDIN, e.g. 10, 10, 2.

Answer 2

CJam, 53 52 51 bytes

q~:L,'Af+a*a*{_::mR_:|,L<\_z:O|N*2ew::=|:|}g;OSf*N*

This will take a long time if AB is too large or N is too small.

Try it online in the CJam interpreter.

Answer 3

Python2, 177 bytes

from random import *
W,H,N=input()
A,l={chr(c)for c in range(65,65+N)},[" "*W]
for h in range(H):
 s=""
 for c in l[h]:s+=sample(A-{s[-1:],c},1)[0]
 l+=[s]
print"\n".join(l[1:])