XP is just a number PerlMonks

### Re: a couple of rounds of golf for the weekend

by barrachois (Pilgrim)
 on Aug 26, 2005 at 23:02 UTC ( #487058=note: print w/replies, xml ) Need Help??

in reply to a couple of rounds of golf for the weekend

I played around with part 1. An interesting problem, but it didn't feel like a a good one for golf.

"the intention is that entries should calculate the terms rather than simply embed them", you say, but when I looked at your part 1 code, I found plenty of embedded data. Disappointing.

Below is 14 lines of code that generates the desired 288 lines, starting only with the constraint definitions and "my \$N=4;". It would, I believe, work as well for N=9 - if you were willing to wait. :)

The algorithm uses regular expressions and recursion both to generate the permutations and recognize the sudoku solutions. I put together a different, iterative version as well; that one didn't squash quite as small. If there's any interest I could post more readable versions of each.

```#!/usr/bin/perl
use warnings; use strict;
my \$N=4;my \$sqN=sqrt(\$N);my @d=1..\$N;my @nsq=0..\$N**2-1;my \$o2n=join('
+',@d);
my (@perm,@sud,\$p_regex,\$s_regex,%cnstrnts,@extra,\$i,\$j,\$p);
sub ro {int(shift()/\$N)} sub col {shift()%\$N}
sub yy {int(int(shift()/\$N)/\$sqN)} sub xx {int((shift()%\$N)/\$sqN)}
for \$i (0..\$N-1){\$p_regex.='(?!'.join('|',map {'\\'.\$_} 1..\$i).')' if
+\$i>0;
\$p_regex.='(\\d)'} \$p_regex = qr(\$p_regex)o; for \$i (@nsq){ my @cnflct
+s;
for \$j (@nsq){next unless \$i!=\$j && (ro(\$i)==ro(\$j)||col(\$i)==col(\$j)|
+|
xx(\$i)==xx(\$j)&&yy(\$i)==yy(\$j)); push(@cnflcts, 1+\$j)} \$cnstrnts{\$i}=\
+@cnflcts}
for \$i (@nsq){\$s_regex.='(?!'.join('|',map{'\\'.\$_}@{\$cnstrnts{\$i}}).'
+)(\\d)'}
\$s_regex=qr(\$s_regex)x; our (\$br,\$max,\$regex,@ans)=(\@d,\$N,\$p_regex);
sub recur {my \$st = shift; if (length(\$st)>=\$max) {push(@ans,\$st)
if \$st=~\$regex} else {recur(\$st.\$_) for @\$br}} recur(''); @perm=@ans;
(\$br,\$max,\$regex,@ans)=(\@perm,\$N**2,\$s_regex); recur(\$o2n); @sud=@ans
+; my @as;
for \$p (@perm){eval("tr/\$o2n/\$p/"),push(@as,\$_) for @sud} print "\$_\n"
+ for @as;

# Generate strings representing sudoku puzzle solutions.
# This could certainly be made shorter, but at about 1000 characters
# it's already illegible enough for me.
#  N=4 : iterations = (N!)**(N-1) = 24**3 = 13824 ; runs in < 1 second
+.
#  N=9 : (9!)**8 = 362880**8 = 3e44, so a million/sec would take 1e31
+years...

print "\n Number of sudokus found is " . scalar(@as) . ".\n\n"; # N=4
+gives 288

Create A New User
Node Status?
node history
Node Type: note [id://487058]
help
Chatterbox?
 [Discipulus]: it seems a legitimate one.. grin ..

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (7)
As of 2018-05-22 12:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (163 votes). Check out past polls.

Notices?