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";
Output:
answer in 35 steps
412433
414422
431331
341114
143132
331222
diagonal 411132
Computes the answer in less than 0.1 seconds.