Easy As ABC, também conhecido como "End View", é um quebra-cabeça em que você recebe uma grade vazia com letras ao seu redor; você deve preencher parcialmente a grade para que exatamente uma de cada letra esteja em cada linha e coluna; além disso, as letras no final de uma linha (ou coluna) devem ser a primeira letra visível nessa linha (ou coluna) dessa direção. Seu objetivo neste código de golfe será resolver um quebra-cabeça Easy As ABC.

Por exemplo, aqui está um quebra - cabeça Easy As ABC da MIT Mystery Hunt deste ano usando as letras MIC:

A solução é:

(Desculpe pelos artefatos no Cs; tentei editar as informações irrelevantes do resto do quebra-cabeça.)

I / O

A entrada será uma matriz de seqüências de caracteres ou possivelmente com delimitadores. Ele começará no canto superior esquerdo e vai no sentido horário. Por exemplo, o quebra-cabeça acima pode ser inserido assim:

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

A saída deve ser a grade resolvida, com ou sem a borda. Pode ser como uma matriz de caracteres, matriz de seqüências de caracteres ou qualquer outro formato conveniente. O mesmo caractere "em branco" deve ser aceito como entrada e exibido como saída, mas esse caractere em branco pode ser qualquer coisa. Se forem cadeias simples, entrada e saída devem ter o mesmo separador (entre os lados para entrada e linhas para saída) ou nenhum separador.

Para quebra-cabeças insolúveis, você deve produzir algo que não seja confundível com uma solução. Você pode assumir que nenhum quebra-cabeça tem mais de uma solução.

Você deve permitir qualquer número de letras e qualquer grade de tamanho; todas as letras usadas aparecerão na borda da grade.

Este é o código-golfe : como sempre, o código mais curto vence!

Casos de teste

"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 os bytes removendo novas linhas

A versão online funciona apenas com os casos de teste com um comprimento de 6

solução curta

faça todas as permutações

preencha 2 matrizes com as permutações $ x $ y

mude entre duas funções até que exista apenas 1 solução na matriz x para cada linha

função i: encontre interseções na grade e solte permutações

função c: verifique as colunas em cada matriz de caracteres exclusivos e remova permutações nas outras linhas das matrizes $ xe $ 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;}