CJam, 33 32 20 19 17 bytes

Revised version, with massive support from @Sp3000 and @MartinBüttner:

qN/_z]{:e`z,3<}/| 

Try it online

Contributions

• @Sp3000 suggested a critical simplification to my original algorithm.
• @MartinBüttner applied his mad golfing skills to the revised approach, which almost certainly resulted in shorter code than I would have come up with even after considering the simplification.

Algorithm and Proof

The following explains the criteria for the puzzle sliding apart horizontally. The vertical case can be determined by looking at columns instead of rows, or transposing the character matrix and looking at the rows again.

I'll use the term "stretch" for a maximum sequence of the same letters. For example, the following rows have 1, 2, and 3 stretches respectively:

AAAAAAAA BBBAAAAA AABBBAAA 

I'll also use the term "interlocked" for a row/puzzle that cannot slide apart.

The key observation is that the puzzle can slide apart if and only if all rows have at most 2 stretches. Or reversed, it is interlocked if and only if there is any row with more than 2 stretches.

The following might not qualify as a strict mathematical proof, but I believe that it makes for a convincing explanation why this has to be the case.

It is easy to see that the puzzle is interlocked if it has rows of more than 2 stretches. Looking at a row with 3 stretches:

BBBAAB 

it is clear that it prevents the puzzle from sliding apart because the A stretch is locked between the B stretches. This means that the row is interlocked, which in turn makes the whole puzzle interlocked.

The opposite direction of the proof is not quite as obvious. We need to show that there are no interlocked puzzles where all rows have only 1 or 2 stretches. Starting with a couple of observations:

• Rows with only 1 stretch do not contribute to a puzzle being interlocked, since they can slide in either direction without any collisions.
• If all rows with 2 stretches have the same order of A and B, the puzzle is clearly not interlocked. In this case, all A cells are left of all B cells, or vice versa, and there are no collisions when sliding the two pieces apart.

The only tricky case would be puzzles where we have rows with 2 stretches of different order. I'm going to show that such puzzles do not exist under the given specifications. To show this, let's look at a partial puzzle that does have this configuration, where . are wildcards:

....... AAABBBB ....... BBAAAAA ....... 

Now, the specification says that both the A and B cells are simply connected in all valid puzzles. To make the A cells connected in the partial puzzle above, we have two options:

1. We loop around one of the stretches of B, for example:

   ..AAAAAA AAABBBBA .......A BBAAAAAA ........ 

   To do this, we unavoidably extend one of the rows to have 3 stretches, so this will never give us a valid puzzle where all rows have at most 2 stretches.

2. We connect them on a direct path:

   ....... AAABBBB ..A.... BBAAAAA ....... 

   The A cells are now simply connected, and there are still no rows with more than 2 stretches. However, the B cells also need to be simply connected. The direct path is now blocked by the connected A cells, and the only way to connect the B cells is to loop around one of the stretches of A cells. This leads back to case 1, where we can't do that without creating rows of 3 stretches.

To count the stretches, the implementation uses the CJam RLE operator.

Explanation of Code

qN/ Get input and split at newlines. _z Make a transposed copy. ] Wrap the original and transposed puzzle in an array so that we can loop over the two. { Start of loop over original and transposed puzzle. :e` Apply RLE to all rows. z, Transpose the matrix with the RLE rows, and take the element count of the result. Or in other words, take the column count. This will be the length of the longest row after RLE. 3< Check the length for less than 3. }/ End of loop over original and transposed puzzle. | Or the results of the two. 

JavaScript (ES6), 108 107 98 91 82 bytes

a=>!(T=[],R=/AB+A|BA+B/).test([...a].map((c,i)=>T[i%-~a.search` `]+=c))|!R.test(a) 

Live demo. Tested in Firefox. Takes input as a newline-delimited string.

Edits:

• Saved 1 byte by changing \n to a literal newline.
• Saved 9 bytes by doing the RegExp test directly on the multi-line string instead of converting to an array.
• Eliminated another 9 bytes by using array comprehensions to split string, moving ! into g function and calling RegExp directly on array instead of using find.
• Continued the arthmetic sequence by saving another 9 bytes. Did a modulus on the index instead of splitting the array by newlines before taking the transpose.

How it works

Previous version:

a=>(T=[],a.split` `.map(s=>s.split``.map((c,i)=>T[i]+=c)),!T.find(g=s=>/AB+A|BA+B/.test(s)))|!g(a) 

1. Take the input a and split it by newlines into an array of strings.
2. Transpose a and store it in T. Use map to iterate over each element of a, split the string into a character array, and use map again to append the ith character in the line to the ith line of T. Since each element of T is uninitialized, it will end up looking something like "undefinedAAABBA", but this won't matter.
3. Create a RegExp based testing function g that matches the pattern /AB+A|BA+B/. If it matches, the pieces are locked in the given direction because then there are a set of Bs sandwiched between two or more As or vice-versa.
4. Use the testing function g to test all elements of the block a and its transpose T for a match using find. If both match, then the pieces are locked in both directions, so output a falsy value, otherwise a truthy one.

Javascript (ES6), 118

slidey= // code a=>!a.match(R=/AB+A|BA+B/)||!(a=a.split` `.map(b=>b.split``))[0].map((_,c)=>a.map(d=>d[c])).some(e=>e.join``.match(R)) // IO var S =document.getElementById('S'); S.onkeyup = _=> document.getElementById('P').innerText = slidey(S.value); document.getElementById('P').innerText = slidey(S.value);

<textarea id='S'>BAAAAABB BBAAABBB BBBABBBB BBBABBBB BBBABBBB BBBBBBBB BBBBBBBB</textarea> <p id='P'></p>

Explanation:

a=> !/* check string horizontally */ || !/* check string vertically by transposing it and running the same horizontal check */ a=> !a.match(R=/AB+A|BA+B/) || !/* ... */ // check for lines containing something like BAAAAAB or ABBBBBBBA // this is the only way something can get blocked horizontally // eg AAAAAAA // AAABAAA <<< note the B in the middle of As here // AAABBBB <<< blocked from being pulled out horizontally // AAAAAAA a=> /* ... */ ||!( a = a.split('\n').map(b=> b.split('')) ) // split a into 2D array [0].map((_,c)=>a.map(d=>d[c])) // transpose it .some(e=>e.join``.match(R)) // run the check again using `some` to go line by line // which is shorter than .join().match() outside a=> !/* returns null if no horizontal obstacles and an array if there are */ || !/* same thing */ // negate both to cast to a boolean (false if obstacles, true if not) // an input can only be unslidable if both directions are blocked // so (no obstacles vertically? || no obstacles horizontally?) gives the answer 

JavaScript (ES6) 72 74

Edit 2 bytes saved thx @NotthatCharles

I have the intuitive understanding that if one piece can slide just a fraction of step, then it's free. The current test cases confirm this.

So I check just one step in each direction.

Characters used: 1 and 0
2 bytes more to use any 2 printable characters like A and B

Test running the snippet below in an EcmaScript 6 compliant browser (supporting the spread operator - IE Firefox)

f=s=>[w=~s.search` `,-w,-1,1].some(o=>![...s].some((x,p)=>x+s[p+o]==10)) // 4 bytes more- for any symbol, not just 1 and 0 (for instance A and B): g=s=>[w=~s.search` `,-w,-1,1].some(o=>![...s].some((x,p)=>x+s[p+o]=='AB')) //TEST console.log=x=>O.innerHTML+=x+'\n' testOk = [ '111\n100\n111', '10', '0\n1', '01\n01', '000\n111', '00001\n01111', '0110\n0110\n0000', '000000111111111\n001111111111111\n000000000011111\n001111111111111\n000000000000001', '000000000000\n010101010101\n111111111111', '10000011\n11000111\n11101111\n11101111\n11101111\n11111111\n11111111', '000\n100\n000' ] testKo = [ '1111\n1001\n1011', '1111\n1001\n0011', '1111111\n1111101\n0000001\n1111111', '1000\n1010\n1110\n0010\n0000', '0000000\n0111110\n0000010\n1111110', '10000011\n11000111\n11101111\n11101111\n11100111\n11111111\n11111111', '000\n010\n110\n010\n000' ] console.log('Expecting true') testOk.forEach(t=>console.log(t+'\n'+f(t)+'\n')) console.log('Expecting false') testKo.forEach(t=>console.log(t+'\n'+f(t)+'\n'))

<pre id=O></pre>

Mathematica 100 69 bytes

With a massive 31 bytes saved, thanks to @Martin Buttner,

g=Max[Length/@Split/@#]<3&;g[c=Characters@StringSplit@#]||g@Thread@c& 

Formats the input as a matrix of characters; it also makes a transpose of the matrix. If either the matrix or its transpose has no more than 2 runs per row then the puzzle is can slide.

{a,a,b,b,b} has 2 runs of letters.

{a,a,b,a,a} has 3 runs of letters.

{a,a,b,a,a,a,b,b,b,b,b,b,b,b} has 4 runs of letters.

Dyalog APL, 22 bytes

(∨/{∧/2>+/2≠/⍵}¨)⊂∘⍉,⊂ 

Try it here. This is a function that takes in a 2D array of characters, and returns 1 for sliding instances and 0 for non-sliding ones. The algorithm is similar to most other answers: check for the matrix and its transpose that no row contains more than one adjacent pair of different letters. For the 4x3 input matrix

AAAA ABBB AAAB 

the function can be invoked as

f ← (∨/{∧/2>+/2≠/⍵}¨)⊂∘⍉,⊂ f 4 3 ⍴ 'AAAAABBBAAAB' 

which results in 1.

Explanation

⊂∘⍉,⊂ The matrix and its transpose. {...}¨ For each of them: 2≠/⍵ On each row, replace each adjacent pair with 1 if they differ, with 0 otherwise 2>+/ Take the sum on each row and check that it's less than 2 ∧/ AND over all rows ∨/ OR over the resulting two values 

JavaScript (ES6), 94 bytes

x=>!(y=/AB+A|BA+B/).test(x)|(z=[],x.split` `.map(b=>b.split``.map((c,i)=>z[i]+=c)),!y.test(z)) 

Same-size alternate method:

x=>(t=s=>!/AB+A|BA+B/.test(s),z=[],x.split` `.map(b=>b.split``.map((c,i)=>z[i]+=c)),t(x)|t(z)) 

This returns 1 for a truthy input and 0 for falsy. I started work on this before any other answers had been posted. I also originally tried using ES7's array comprehensions, but that ended up about 10 chars longer than this method.

Try it out:

a=x=>!(y=/AB+A|BA+B/).test(x)|(z=[],x.split` `.map(b=>b.split``.map((c,i)=>z[i]+=c)),!y.test(z)) P.onclick=_=>Q.innerHTML='Result: '+a(O.value)

<textarea id=O cols="20" rows="8">AAAAAABBBBBBBBB AABBBBBBBBBBBBB AAAAAAAAAABBBBB AABBBBBBBBBBBBB AAAAAAAAAAAAAAB</textarea> <button id=P>Test</button> <p id=Q>Result: </p>

Suggestions welcome!

Python3, 426 bytes

M=[(1,0),(-1,0),(0,-1),(0,1)] E=enumerate def G(d): q=[*d] while q: Q=[q.pop(0)] s=[*Q] for x,y in Q: for X,Y in M: if(T:=(x+X,y+Y))in q and d[T]==d[(x,y)]:s+=[T];Q+=[T];q=[*{*q}-{T}] yield s def f(b): a,u=G({(x,y):v for x,r in E(b)for y,v in E(r)}) q=[(u,*i)for i in M] for b,x,y in q: if[]==b:return 1 B,F=[],1 for X,Y in b: if(T:=(x+X,y+Y))in a:F=0;break if T in u:B+=[T] if F:q+=[(B,x,y)] 

Try it online!