#1: Jan Wolter (jan) on Jun 29, 2007

I've been scribbling some PBN math that I need for an upgrade on the back of an envelope. I thought I'd write it up a bit nicer and post it here for the amusement of folks who like such things.

A key notion in PBN puzzles is the amount of slack in a row or column. The clue in any line accounts for a certain number of squares, all the squares counted in the numbers, plus one white space whenever two consecutive clue numbers are of the same color. If you subtract the number of squares accounted for in the clue, from the length of the row or column, then that's the slack. Basically, if you jammed everything as far to the left as it would go, the number of blanks left over at the right would be the slack.

  slack = (length of row) -
          (sum of all clue values) -
          (number of same-color consecutive clue pairs)

Slack is a handy value, so handy that I've been tempted to put some tool into the solver that will compute and display it for you. If slack is zero, then there is only one possible solution for the row/column. If there is any clue number that is larger than the slack, then you can fill in some cells in the row.

It's possible that some analog to the notion of slack could be found for partly solved rows. Might even be useful, but for now I'm only talking about blank rows.

So what I want to know is how many possible solution there are to a row/column. Let's let C be the number of different clue numbers. So if the clue is "4 9 13" then C is three. Let S be the amount of slack.

Solving the row basically consists of distributing the S slack spaces into the C+1 gaps between the clue numbers. You could stick in a slack space before the 4, between the 4 and the 9, between the 9 and the 13, or after the 13. So there are 4 places you can insert slack spaces into a line with 3 clues. So pretty clearly, the number of possible different solutions is going to depend entirely on the number of clues (or gaps between clues) and the amount of slack, not on the length of the line, the values of the clues, or anything else. So we'll write the number of solutions to a row with C clues and S slack as N(C,S).

So what is the formula for N(C,S)? Well, let's start with some boundary conditions:

   N(0,S) = 1
   N(C,0) = 1

If there are no clues, then there is only one solution (this is the case of an all blank row/column). If there is no slack, then there is only one solution.

But suppose S>0 and C>0. Well, let's focus on the first gap. We can put 0 spaces in it, 1 space in it, 2 spaces in it, and so on, up to a maximum of S spaces. For each of these cases, we can figure out how many solutions there are to the rest of the line. The rest of the line contains C-1 clues, and, if we put I spaces into the first gap, there is S-I slack. So the total number of solutions is:

 N(C,S) = N(C-1,S) + N(C-1,S-1) + N(C-1,S-2) + ..+ N(C-1,0)

If I had any half-way decent tools for displaying mathematical formula here, I'd rewrite that as the summation for I=0 to S of N(C-1,I).

Now, the above rather ugly expression can be rewritten as

  N(C,S) = N(C-1,S) + N(C,S-1)

Note that the first term is the same as it was in the previous equation, and N(C,S-1) is, by definition, equal to the rest of the terms in that equation.

We can write down a few values of this:

Slack (S)	Clues (C)
	0	1	2	3	4
0	1	1	1	1	1
1	1	2	3	4	5
2	1	3	6	10	15
3	1	4	10	20	35
4	1	5	15	35	70

OK, we're well past flash of recognition time for anyone who ever studied any combinatorics. That's Pascal's Triangle, turn on it's side a bit. Pascal's Triangle is a table of binomial coefficients, those things called "N choose K" which are usually written with the N over the K in a pair of parenthesis, but that's too hard to do in HTML, so I'll just write C(N,K) for "N choose K".

So, we can write:

   N(C,S) = C(C+S,S)

or equivalently

   N(C,S) = C(C+S,C)

I admit, I got that by inspection, not derivation. Hey, I'm rusty.

Or we can write in factorial notation,

   N(C,S) = (C+S)! / ( C! S!)

Interestingly, this means that the rows/columns that are the worst to solve, that have the most possible solutions, are the ones where the amount of slack is equal to the number of clues. If the slack is significantly more or less than the number of clues, then the number of possible solutions drops dramatically.

The specific reason that I worked all this out is that I want to implement a partial work-around for the problem with the error checking hanging on large puzzles sometimes. This happens when you do something impossible on the right side of a row. The error checker, being a bit stupid, starts trying out all possible rearrangements of things on the left side of the row in the vain hope that doing something different there will magically make the right side work out.
<p>
So the number of possible solutions to a row is likely to be a good predictor how likely the error checker is to flail for a long time in such circumstances.

If I know the row is a risky one for the error checker, I can do some tricks to reduce the risk of long hangs. For example, if the row was previously OK, and the last change was nearer the right side than the left, then I could do the error checking from right to left instead of from left to right. I expect that would make a huge difference, much more than you'd normally expect, because of the exponential nature of the expression developed above. It wouldn't entirely solve the problem, but might make it much less common.

But reversing the error check takes some extra computation to do and extra download time to set up, so I wouldn't want to do it for all rows/columns. I'd only want to do it for rows/columns where N(C,S) exceeds some threshold.

Generalizing this analysis to allow us to compute the number of solutions in partially solved rows would be useful. Not only would it be helpful for knowing when to take steps to avoid the error checking from hanging, but it would be useful in a solver, since the rational thing to do would be to attach the rows/columns where N is low first (maybe - I'd have to think about that). But that's more complex.

Of course, if I want to compute N(C,S) for all the rows of a puzzle, and use it to decide if I should take evasive action to avoid hangups, then I need a way to compute it efficiently. The obvious way to compute N(C,S) involves a loop doing min(C,S) multiplications and a division, but that is (1) slow, and (2) prone to overflows.

The better idea is to compute the natural log of N(C,S) instead. We'll compare that to the natural log of the threshold. This turns all our multiplications into additons, and pretty much completely avoids any risk of overflows.

The next better idea is use Lanczos's approximation to the gamma function to compute the factorials. A gamma function is basically just a factorial for real numbers, and Lanczos's approximation allows us to compute the logarithm of the gamma function without doing a loop at all. What this means is that I can compute ln(N(C,S)) in a snap even for large values. It takes me no more time to discover that ln(C(100,000,50,000)) = 69308.7357994092 than it does to discover that ln(C(9,0)) = 0.

It might actually be overkill for this application, since C and S are really usually quite small, but it's so much more cool than doing it the obvious way.

Hmmm...unfortunately, this doesn't seem to be that good a predictor of the performance of the regular expression matcher that does the error check. I created some test puzzles with various numbers of clues and various amounts of slack. The run time of the error checker (at least in Firefox) seems to be much more sensitive to the number of clues than the amount of slack, though it is definitely sensitive to both. Furthermore, it is sensitive to the sizes of the clue numbers. A row with a bunch of one-clues and a single larger clue is much slower to check than a row with uniform sized clues, even if the number of clues and amount of slack is the same.

If I have a line with 30 clues and just one space of slack, it takes almost forever for the regular expression to work, even though there are only 31 possible solutions to consider.

Hmmm...this implies that something entirely different is going on with the error checker than I thought, which I might be able to fix in a different way.... But that's not a topic for a PBN math item.

Here's a simple proof of the theorem in #1:

The number of possible solutions is the number of ways of putting S identical balls into C+1 distinct boxes. Say the number of clues is 4 and the slack is 7; then you can represent any such arrangement as a string of 7 x's and 4 |'s. For instance, x|xx|xxxx|x| means put 1 ball in the first box, 2 in the second, 4 in the third, one in the fourth, and none in the fifth.

The number of such strings is 7+4 choose 4, and in general it's clearly C+S choose C. This is called a "stars and bars" argument.

When I compute binomial coefficients I usually need a lot of them, so it makes sense to compute all of Pascal's triangle down to some depth, using the recurrence (n choose k) = (n-1 choose k-1) + (n-1 choose k). Then any particular one is just a lookup. Dunno if that makes sense here.

Hm, I've been using this "slack" math for ages as a sort of shortcut to counting out every square during line solving. I also use it for self-checking (extra important on paper, since after you erase it enough times the paper tears!) I just never called it that! I do it in my head.

First I sum up the clues for the blank section in question (whether it's a whole line or just a portion). Then I count up by one for each of the spaces between them. It's easier for me to do it in my head this way, even though it's less efficient. I've had to modify this for multi-color puzzles by counting up by one <i>only</i> when the two adjacent numbers are the same color.

Once I have this sum, I add the largest clue number to it. If the result is greater than the length of the line (or the blank part of it), I know I can take the difference and fill in exactly that many squares for that block.

So if I have a row of 15, and clue numbers 1 2 3 4 (all one color), I add up the clue numbers (10). I physically or mentally put my "pencil" on the space between 1 and 2 and count up by one (11). Same for the space between 2 and 3 (12) and 3 and 4 (13). Now I add the largest clue number, 4, to get 17. The difference between this number and the line length is 2, so I automatically fill in 2 squares for the block of 4. (It's always the ones furthest from the edge if you count the blocks and spaces as tightly as possible from the edge.) If I add the 13 to the next clue number (3), I get 16, one more than 15, so I can mark one square of the block of 3. For the clue of 2, my sum is only 15, equal to the blank line length, so I can't yet mark any squares of the block of 2.

It sounds complicated but I just do it automatically in my head now. I don't think I'm using anything like binomial coefficients, Pascal's triangle, etc. (if I am, I'm not aware of it), just simple addition and subtraction—like I said, it's less efficient but easier for my brain to grasp.
Does anybody else do this?

I do almost what you do. The only difference is I add up the number of clues (in your example 4) and subtract 1 and add that the to sum. Other than that, you describe exactly how I tackle the math.

I also have a special case that I apply. I always look for clues that when doubled are more than the length of the row. For instance, if I am working on a 20x20 grid and I have clues 11,2 on a row, then I will fill in the 10 and 11 column cell and 3 more cells to the left since I know the 2 clue and a space will take up 3 spots on the right.

Yes, the clue that's more than half the row is a pretty standard thing I look for, too. Say in a 20x20 puzzle I have a line with a single block of 11. I automatically blacken the two center squares without thinking. Now say that line has clues "1 11." I automatically blacken the two center, then two more to the right (or bottom) because of the offset of the 1 and the space between them. I hardly even think about this—like all experienced solvers, I'm sure.

My approach is to double the longest clue and add up all the other fillers and spaces. This is obviously the same thing as what Robyn does. Also the other fills will be the same difference, i.e. if the longest is 10 and there is an overlap of 8 having doubled 10, every other number will be filled -2 (a 6 would be 4 filled) and there are clear symmetries as well.

Goto next topic

You must register and log in to be able to participate in this discussion.