laziness, impatience, and hubris PerlMonks

Number Grid Fillin

by QM (Parson)
 on Aug 14, 2017 at 08:41 UTC ( #1197354=CUFP: print w/replies, xml ) Need Help??

Saw this idea recently. Wondered how susceptible it would be to a brute force approach.

Given a square grid size N, and a list of numbers 2*N**2 2*N, find a fillin (like a crossword), and report the digits in the major diagonal (as an easy proof of solution).

The reference in the spoiler took an hour or two to find the solution. I won't post the solution here, you'll have to do the work yourself.

-QM
--
Quantum Mechanics: The dreams stuff is made of

Replies are listed 'Best First'.
Re: Number Grid Fillin
by tybalt89 (Priest) on Aug 14, 2017 at 12:05 UTC

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;
{
\$lefts{\$head} <= ( () = \$rest =~ /^\$head/gm ) or goto NEXT;
}

if( \$rest =~ tr/\n// == \$half )    # half left means completed
{
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.

Re: Number Grid Fillin
by hdb (Monsignor) on Aug 15, 2017 at 12:40 UTC

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";
}

Re: Number Grid Fillin
by LanX (Bishop) on Aug 14, 2017 at 15:56 UTC

Create A New User
Node Status?
node history
Node Type: CUFP [id://1197354]
Approved by davies
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (4)
As of 2018-04-23 18:33 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My travels bear the most uncanny semblance to ...

Results (85 votes). Check out past polls.

Notices?