in reply to Matrix Formation
Ok, I ran out of time working on the "brute force" checking, but here is the shell of a program which should reduce the number of numbers which need to be checked to a small enough set. Sorry I could not complete the program (as it was actually starting to be fun. *Smiles*)
#!/usr/bin/perl
use strict;
use warnings;
use constant MATRIX_DIM => 3; # Set your matrix size here
use constant MAX_NUM => (10 ** MATRIX_DIM)  1;
# Since you need to find 2 times the matrix width distinct numbers, yo
+u cannot
# have a divisor greater than the maximum number divided by that produ
+ct.
#
# For example, a 3 x 3 matrix has a maximum number of 999. You need 6
+distinct
# numbers to "solve" the matrix, so the maximum possible divisor would
+ be 166.
# 166 would result in 166, 332, 498, 664, 830, and 996.
#
my $Divisor = int(MAX_NUM / (MATRIX_DIM * 2));
my @Num;
my @Sol=();
sub CheckSolution
{
my $pNum=shift;
my @Sol=();
# INCOMPLETE CODE
#
# Place code here which checks every combination of MATRIX_DIM numbe
+rs as rows
# and sees if there are MATRIX_DIM other numbers which can act as co
+lumns.
#
# For example, for a 3 x 3 matrix, this code should go through each
+combination
# of three number (for rows) from the passed array and see if there
+are three
# other numbers which would work with the selected rows as columns.
+This should
# be a workable computation for all smaller matrix sizes.
#
return @Sol;
}
while ($Divisor >= 1)
{
@Num=();
foreach (1..int(MAX_NUM / $Divisor))
{
next if (($Divisor * $_) < (MAX_NUM / 10)); #Skip numbers which be
+gin with zero
push @Num, ($Divisor * $_);
}
print 'Checking solution for divisor ',$Divisor,': ',join('',@Num),
+"\n";
@Sol=CheckSolution(\@Num);
last if ($#Sol > 1);
$Divisor;
}
print "\n";
if ($#Sol > 1)
{
print 'Maximum divisor is ',$Divisor,', solution is ',join('',@Sol)
+,"\n";
}
else
{
print 'No solution found...',"\n";
}
Update: I finished code which will work on any size matrix and posted it Here. Please note: I use "work" in the loosest terms as solving the 4x4 took 1.5 hours on my notebook.
Re: Re: Matrix Formation by tall_man (Parson) on Jun 18, 2003 at 19:38 UTC 
Here is a possible implementation of CheckSolution (for 3x3 only  generalization is possible but it is left as an exercise for the reader):
sub CheckSolution
{
my $pNum = shift;
my @Sol=();
# Do some easy pair checks first.
my @digmap;
foreach my $n (@$pNum) {
my @digits = split //,$n;
foreach (0..$#digits) {
push @{$digmap[$_]>{$digits[$_]}},$n;
}
}
# Two or more with same first digit.
my $ref0 = $digmap[0];
my @lst0 = grep { scalar(@{$ref0>{$_}}) > 1 } keys %$ref0;
return @Sol if (! scalar(@lst0));
# Two or more with same middle digit.
my $ref1 = $digmap[1];
my @lst1 = grep { scalar(@{$ref1>{$_}}) > 1 } keys %$ref1;
return @Sol if (! scalar(@lst1));
# Two or more with same last digit
my $ref2 = $digmap[2];
my @lst2 = grep { scalar(@{$ref2>{$_}}) > 1 } keys %$ref2;
return @Sol if (! scalar(@lst2));
#print "Passed pair test\n";
# Use these lists for candidates for the three row positions.
my @uppers = map { @{$ref0>{$_}} } @lst0;
my @centers = map { @{$ref1>{$_}} } @lst1;
my @bottoms = map { @{$ref2>{$_}} } @lst2;
my ($upper, $center, $bottom);
my ($a, $b, $c, $d, $e, $f, $g, $h, $i);
my ($adg, $beh, $cfi);
# hash to simplify checking for duplicates.
my %wholeset = map { $_ => 1 } @$pNum;
my (%t1, %t2, %t3);
foreach $upper (@uppers) {
%t1 = %wholeset;
$t1{$upper} = 0;
foreach $center (@centers) {
next if (! $t1{$center});
%t2 = %t1;
$t2{$center} = 0;
foreach $bottom (@bottoms) {
next if (! $t2{$bottom});
%t3 = %t2;
$t3{$bottom} = 0;
($a, $b, $c) = split //,$upper;
($d, $e, $f) = split //,$center;
($g, $h, $i) = split //,$bottom;
$adg = $a . $d . $g;
next if (! $t3{$adg});
$t3{$adg} = 0;
$beh = $b . $e . $h;
next if (! $t3{$beh});
$t3{$beh} = 0;
$cfi = $c . $f . $i;
next if (! $t3{$cfi});
# Solution found  return it.
return ($upper, $center, $bottom);
} # bottom
} # center
} #upper
return @Sol;
}
I tried this and it found the 132792660 (divisor 44) case in about 4 seconds.  [reply] [d/l] 
