Fun problem!

I call this "Smart Brute Force".
It fills in one column at a time with each remaining number in turn, then checks to see if the leading parts of each row are possible from left over numbers.

#!/usr/bin/perl -l

# http://perlmonks.org/?node_id=1197354

use strict;
use warnings;

@ARGV or @ARGV = qw( 113443 143132 241131 321422 323132 331222
  341114 412433 414422 431331 443112 444313 );

my $half = @ARGV / 2;
my $steps = 0;

my @stack = [ "\n" x $half, join '', map "$_\n", @ARGV ];

NEXT:
while( @stack )
  {
  my ($have, $rest) = @{ pop @stack };
  $steps++;

  my %lefts;                            # validate legal so far
  $lefts{$_}++ for $have =~ /^(.+)\n/gm;
  for my $head (keys %lefts)
    {
    $lefts{$head} <= ( () = $rest =~ /^$head/gm ) or goto NEXT;
    }

  if( $rest =~ tr/\n// == $half )    # half left means completed
    {
    print "answer in $steps steps\n\n$have";
    print "diagonal  ", $have =~ /(\d)(?:..{$half})?/gs;
    exit;
    }

  while( $rest =~ /^(.+)\n/gm )      # try each number remaining
    {
    my ($before, $after, @digits) = ($`, $', split //, $1);
    push @stack,
      [ $have =~ s/(?=\n)/ shift @digits /ger, $before . $after ];
    }
  }

print "failed to find solution in $steps steps\n";
[download]

Output:

answer in 35 steps

412433
414422
431331
341114
143132
331222

diagonal  411132
[download]

Computes the answer in less than 0.1 seconds.

Thanks for posting this inspiring problem. Similar to what tybalt89 has posted, one can significantly reduce the search space by checking whether for a given number in a given position the remaining numbers would still fit. Below some code to do that based on positions counting from 0 to 5 and each can be vertical or horizontal. Given the output it is nearly trivial to solve the puzzle manually.

use strict;
use warnings;

my @numbers = qw( 113443 143132 241131 321422 323132 331222
                  341114 412433 414422 431331 443112 444313 );
                
# find possible positions
my %positions;
for my $n (@numbers) {
    $positions{$n} = [];
    # frequency of digits in current number
    my @nfreq = (0) x 5;
    $nfreq[$_]++ for split //, $n;
    # check which position is possible
    for my $p (0..5) {
        # frequency of digits in current position w/o current number
        my @freq = (0) x 5;
        $freq[substr( $_, $p, 1 )]++ for @numbers;
        $freq[substr( $n, $p, 1 )]--;
        # check if position is feasible
        # ie enough of each digit available
        my $possible = 1;
        $freq[$_]<$nfreq[$_] and $possible = 0 for 1..4;
        push @{$positions{$n}}, $p if $possible;
    }
}

for my $n (sort { scalar(@{$positions{$a}}) <=> scalar(@{$positions{$b
+}}) } @numbers) {
    print "Number $n can be at positions @{$positions{$n}}.\n";
}
[download]