Easy as ABC Solver

Question

Easy As ABC, also known as "End View", is a puzzle where you are given an empty grid with letters around it; you must partially fill in the grid so that exactly one of each letter is in every row and column; in addition, letters at the end of a row (or column) must be the first letter visible in that row (or column) from that direction. Your goal in this code golf will be to solve an Easy As ABC puzzle.

For example, here is an Easy As ABC puzzle from this year's MIT Mystery Hunt using the letters MIC:

The solution is:

(Sorry about the artifacts on the Cs; I tried to edit out the irrelevant information from the rest of the puzzle.)

I/O

Input will be an array of strings or a string possibly with delimiters. It will start in the top left corner and go clockwise. For instance, the above puzzle could be input like this:

".CMM.M|....IM|.....I|C.ICI."

Output should be the solved grid, with or without the border. It can be as an array of chars, array of strings, or any other convenient format. The same "blank" character must be accepted as input and displayed as output, but that blank character may be anything. If they are single strings, both input and output must have the same separator (between sides for input and rows for output) or no separator at all.

For unsolvable puzzles, you must output something that is not mistakable for a solution. You may assume that no puzzle has more than one solution.

You must allow any number of letters and any size grid; all used letters will appear in the border of the grid.

This is code-golf: as usual, shortest code wins!

Test Cases

"T.AA..|.T.TSS|..TST.|A...SS"
"R.RU..|B.B..B|.UR.UB|UR..B."
"N...NK|E.NK.K|..KK..|....EK"
"CA..DBD|.B..CC.|.D.DEB.|DB.A..A"
"...DDEBE|DC..EBBD|BA..ABF.|E..FECDE"

Answer 1

PHP, 1111 Bytes

minus the Bytes removing newlines

The Online version works only with the Testcases with a length of 6

short workaround

make all permutations

fill 2 arrays with the permutations $x $y

change between two functions so long till only 1 solution in the x array foreach line exists

function i:find intersections in the grid and drop permutations

function c:check the colums in each array of unique charcters and remove permutations in the other lines for array $x and $y

$p=[];p(array_pad(($s="str_split")(substr(count_chars($a=$argn,3),1,-1)),$l=(strlen($a)-3)/4," "));
$e=explode("|",$a);$e[3]=strrev($e[3]);$e[2]=strrev($e[2]);
$x=$y=array_fill(0,$l,$p);$g="preg_grep";$c="array_column";$o="join";
foreach($q=range(0,$l-1)as$i){
$e[0][$i]=="."?:$y[$i]=$g("#^\s*{$e[0][$i]}#",$y[$i]);
$e[2][$i]=="."?:$y[$i]=$g("#{$e[2][$i]}\s*$#",$y[$i]);
$e[3][$i]=="."?:$x[$i]=$g("#^\s*{$e[3][$i]}#",$x[$i]);
$e[1][$i]=="."?:$x[$i]=$g("#{$e[1][$i]}\s*$#",$x[$i]);}
for(;array_sum(($m="array_map")("count",$x))>$l;){
foreach($q as$i)foreach($q as$j){
$k=array_intersect($c($m($s,$x[$i]),$j),$c($m($s,$y[$j]),$i));
$y[$j]=$g("#^.{{$i}}(".$o("|",$k).")#",$y[$j]);
$x[$i]=$g("#^.{{$j}}(".$o("|",$k).")#",$x[$i]);
foreach(["x","y"]as$z){
$u=array_unique($c($m($s,${"$z"}[$i]),$j));
if(count($u)==1&&end($u)!=" "){$w=end($u);
foreach($q as$h){
if($i!=$h)${"$z"}[$h]=$g("#^.{{$j}}{$w}#",${"$z"}[$h],1);}}
}}}
echo$o("\n",$m($o,$x));
function p($c,$b=[]){global$p;
if(($c)){$n=[];while($c){
$e=array_pop($c);
p(($m="array_merge")($c,$n),$m($b,[$e]));
$n[]=$e;
}}else in_array($b=join($b),$p)?:$p[]=$b;}