There are 288 different 4 x 4 grids that represent a valid Sudoko solution. But how many partial grids are there that represent a fair Sudoku problem? (By "fair" I mean "give enough information to resolve to a unique solution".)

Here's an example of a fair problem with 4 digits given, and the unique solution it leads to:


+--+--+       +--+--+
| 4| 2|       |14|32|
|  | 1|       |32|41|
+--+--+ gives +--+--+
|  |  |       |41|23|
| 3|  |       |23|14|
+--+--+       +--+--+

[download]

The challenge (part 1): code to construct a list or array of the 288 solutions as 16-byte strings of the digits 1234. (E.g. the solution above would be "1432324141232314".)

The challenge (part 2): a program that takes a single integer argument from 0 to 16, and outputs to stdout the number of fair partial grids there are with that many digits given. You may optionally output a newline as well.

Now this represents a fixed 17-term sequence, and the intention is that entries should calculate the terms rather than simply embed them, but I don't know how to specify my intention as an unambiguous rule. So I'll specify this instead: if you don't construct the array from part 1 as part of your solution to part 2, you must specify what knowledge about the problem you took as given, and you'll be competing against people that used the same knowledge.

I wrote some code to help you verify that your program is producing the right* answers, but it's been raining here which unfortunately smudged some of the digits:

perl -MDigest::MD5=md5_hex -wle 'print $s=join",",map`my_entry $_`,0..
+16; print md5_hex($s)'
0,0,0,################################################################
+######################8,288
59344163bcacc12056163949869a84b0

[download]

Update 1: lines should not exceed 80 characters.

Update 2: strike update 1; add ref to definition of Sudoku.

Hugo

*"The same answers as I get." Bonus marks for proving me wrong. :)

Replies are listed 'Best First'.
Re: a couple of rounds of golf for the weekend
by hv (Prior) on Aug 19, 2005 at 19:27 UTC
[reply]
[d/l]
[select]
Re: a couple of rounds of golf for the weekend
by Anonymous Monk on Aug 21, 2005 at 10:24 UTC
    Let me try to explain to you why no one has responded to this.

    Firstly, to golf one needs to know what algorithm one has to implement, in this case it involves knowing what a sudoku is. Do not assume everyone does, explain what it is and post a link or something.

    Secondly, never restrict the type of algorithm that can be chosen as you have done in part II. Golfing well is all about choosing the right algo. Part II would certinally be smaller if in the form: 
    print ((ans_0,ans_1,...,ans_16)[$ARGV[0]]);

    [download]
    although there may be some shorter underlying mathematical expression. You seem to want that we implement some difficult method. Why? Some strange notion of program purity? Golf is not about creating something that is easily extendable to other cases. If that is what you want, specify a second argument to give the dimension of the sudoku. If you do not bound this then no list based solution will work. There may however still be a mathematical expression for this which is easier than what you want.

    Thirdly, what with the "I wrote some code to help you verify that your program is producing the right* answers, but it's been raining here which unfortunately smudged some of the digits"? Are you saying that this code thus doesn't work? What is the point then?. This is a golf, providing test code is not abnormal. Providing test code that is broken simply to annoy the participant is a sure-fire way of having no participants.

    Fourthly, "Update 1: lines should not exceed 80 characters."? WHY NOT? If there is no good reason do not impose stupid restrictions, certainaly not as an after thought.

    Now, go have a tasty cup of longjin tea and then try again.
[reply]
[d/l]

      (Quotes are paraphrased.)

      Firstly, define Sudoku

      Apologies: I foolishly assumed that anybody likely to be interested in this sort of problem would have heard of them. See the Wikipedia entry for lots of information about them.

      Secondly, don't restrict the algorithm

      I specifically did not restrict the algorithm that could be chosen. What I am personally interested in is golf approaches to "discovering the numbers when you don't already know them", but last time someone tried to express that as an imposition it led to a lot of discussion and some bad feeling. So I tried to find a different approach.

      I'm hoping people will try different algorithms, but while I will applaud the artistry of any good solution I will look with more interest at the science of those that do not encode the answers as a priori knowledge.

      What's with the silly verification stuff?

      I provided the md5 checksum so that someone who didn't want to spoil themselves by looking at my implementation could verify that they were producing the right set of numbers. I provided some digits at either end to remove any doubt about the format of the string. If you want the full list, you'll find it as A109252 in the OEIS.

      Why the arbitrary line length restriction?

      I was expecting long lines, and was worried that it would be rude to impose such on the Monastery. Maybe that was foolish, since any entries will likely be in code tags and spoiler tags. I'll take the restriction out.

      Thanks for the comments,

      Hugo

[reply]
Re: a couple of rounds of golf for the weekend
by barrachois (Pilgrim) on Aug 26, 2005 at 23:02 UTC
    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

    [download]
[reply]
[d/l]
[select]

Back to Obfuscated Code