Easy As ABC, también conocido como "End View", es un rompecabezas en el que se le da una cuadrícula vacía con letras a su alrededor; debe completar parcialmente la cuadrícula para que exactamente una de cada letra esté en cada fila y columna; Además, las letras al final de una fila (o columna) deben ser la primera letra visible en esa fila (o columna) desde esa dirección. Su objetivo en este código de golf será resolver un rompecabezas Easy As ABC.

Por ejemplo, aquí hay un rompecabezas Easy As ABC del MIT Mystery Hunt de este año usando las letras MIC:

La solucion es:

(Perdón por los artefactos en las Cs; intenté editar la información irrelevante del resto del rompecabezas).

I / O

La entrada será una matriz de cadenas o una cadena posiblemente con delimitadores. Comenzará en la esquina superior izquierda e irá en sentido horario. Por ejemplo, el acertijo anterior podría introducirse así:

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

La salida debe ser la cuadrícula resuelta, con o sin borde. Puede ser un conjunto de caracteres, un conjunto de cadenas o cualquier otro formato conveniente. El mismo carácter "en blanco" debe aceptarse como entrada y mostrarse como salida, pero ese carácter en blanco puede ser cualquier cosa. Si son cadenas simples, tanto la entrada como la salida deben tener el mismo separador (entre los lados para la entrada y las filas para la salida) o ningún separador.

Para acertijos insolubles, debe generar algo que no se pueda confundir con una solución. Puede suponer que ningún rompecabezas tiene más de una solución.

Debe permitir cualquier cantidad de letras y cuadrículas de cualquier tamaño; todas las letras usadas aparecerán en el borde de la cuadrícula.

Este es el código de golf : como siempre, ¡el código más corto gana!

Casos de prueba

"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"

PHP, 1111 bytes

menos los bytes que eliminan nuevas líneas

La versión en línea solo funciona con los Casos de prueba con una longitud de 6

breve solución

hacer todas las permutaciones

llenar 2 matrices con las permutaciones $ x $ y

cambiar entre dos funciones durante tanto tiempo hasta que solo exista una solución en la línea x de cada línea

función i: encontrar intersecciones en la cuadrícula y soltar permutaciones

función c: verifique las columnas en cada conjunto de caracteres únicos y elimine las permutaciones en las otras líneas para el conjunto $ x y $ 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;}