Here's solutions for 2,4,6,8,10 and proves? none for 3,5,7

#!/usr/bin/perl

use strict; # https://perlmonks.org/?node_id=11141490
use warnings;
use ntheory qw( forperm );
use List::AllUtils qw( none );

for my $n ( 2 .. 8, 10 )
  {
  my @cols;
  forperm { my $c = join '', map +('-', 'a'..'z', 'A' .. 'Z')[$_], @_;
    push @{ $cols[ index $c, '-' ] }, $c } $n;
  my $start = $cols[0][0];
  eval { find( "$start\n", @cols[1 .. $#cols ] ) };
  }

sub transpose
  {
  (local $_, my $new) = (shift, '');
  $new .= "\n" while s/^./ $new .= $&; ''/gem;
  return $new;
  }

sub find
  {
  my ($have, @next) = @_;
  my $flip = transpose($have);
  @next or $have eq $flip and warn( "$have\n"), die;
  my $pat = (split /\n/, $flip)[index $flip, "\n"];
  my @haves = split /\n/, $have;
  my $trys = shift @next;
  for my $try ( grep /^$pat/, @$trys )
    {
    none { ("$try" ^ "$_") =~ tr/\0// } @haves, and
      find( "$have$try\n", @next );
    }
  }
[download]

Outputs:

-a
a-

-abc
a-cb
bc-a
cba-

-abcde
a-cdeb
bc-ead
cde-ba
deab-c
ebdac-

-abcdefg
a-cbedgf
bc-afgde
cba-gfed
defg-abc
edgfa-cb
fgdebc-a
gfedcba-

-abcdefghi
a-cbedgfih
bc-afghide
cba-ghidef
defg-iahbc
edghi-bcfa
fghiab-ecd
gfidhce-ab
hidebfca-g
ihefcadbg-


real    0m8.080s
user    0m7.986s
sys     0m0.090s
[download]

I think you are dealing with factorials, so good luck with 50 factorial!!

On the other hand, I could be wrong...