Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
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 (Prior) 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; 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.

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 (Cardinal) on Aug 14, 2017 at 15:56 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: CUFP [id://1197354]
Approved by davies
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (8)
As of 2021-04-22 16:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?