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. :)

In reply to a couple of rounds of golf for the weekend by hv

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.