Wireless Keyboard Inteference
Julia, 97 chars

s(k)=while any([k[j]&gt;k[j-1]||j&gt;6&amp;&amp;k[j]&gt;k[j-6] for j=2:36]);i,j=rand(1:36,2);k[[i,j]]=k[[j,i]];end


Checks if the array is in an acceptable final state state, if not, randomly flips two entries. It's super slow, which I find highly amusing. Does an in place alteration on the input array k. InterferesWith is implemented as &gt;.

As I said, it's really slow.  I tested it with more frequencies and smaller boards with 3 frequencies, but it hasn't returned in over 30 mins on the actual problem. I suspect that it won't return overnight, but I'll update if it does. Update: Yes it did finish in less than 12 hours, and yielded an answer that I added to the gist.

Gist with commented code, and includes 3x3 test case that finishes fast: https://gist.github.com/ggggggggg/8679916