I'm programming an AI for solving picross puzzles, to optimize it, it would be very helpful to know which row has the least possible valid combinations.
What I've figured out is that given the constraints of a row i can calculate the number of valid combinations with generating functions in the following manner.
A valid row might be visualized as:
|2 3|□ □ ■ ■ □ □ □ ■ ■ ■ □|
m is the size of the row in question.
Given the constraints of a row as: $c = (c_1, c_2, ..., c_n)$
s = $\sum^{n}_{i=1}c_i$
$x_i$ is the size of the gap between $c_{i-1}$ and $c_i$
We find the number of combinations of $x_i$ that satisfy the following equation:
$m = \sum^{n}_{i=1}c_i + \sum^{n+1}_{i=1}x_i$
$m - \sum^{n}_{i=1}c_i = \sum^{n+1}_{i=1}x_i$
$m-s = x_1 + x_2 + ... + x_{n+1}$
Notice that the gaps can't be 0 with the exception of the first and last ones.
From this we define the polynomial $P(x)$:
$P(x)=(x+x^2+x^3+...)^{n-1} \cdot (1+x+x^2+...)^2$
The solution to our problem will then be the coefficient of order $m-s$ of $P(x)$, that would be enough for me, since i can easily calculate that coefficient in my code.
Now the problem is that i might have an incomplete row where i know that some of the cells should be colored in, and others that shouldn't, but there are some cells for which i have not enough information.
An example of an incomplete row might be visualized as:
|2 3|□ ? ■ ? □ ? ? ■ ? ? □|
How could I solve this problem?
By the way, the AI which I'm talking about is open source and can be found here.
It might be hard to understand since there's almost no comments yet, also, it has no GUI for the moment, but I'm still working on it.