Red Ed wrote:Let's try to answer those questions for the Naked Single resolution rule with condition:

candidate(n1,r,c) AND NOT(candidate(n2,r,c)) AND ... NOT(candidate(n9,r,c)), and I'm taking n1,n2,...,n9 to be distinct. Then, with respect to the two questions above:

- There are 81 choices for (r,c) and 9 for n1, so 729 places to look in total.
- This is tricky! We could say that there are 9 terms to check, or just 1 minterm (multi-input AND) to evaluate, or 16 logical operations to perform, or ... what? How about (for a strawman) we just count the minimal number of appearances of a candidate() predicate that can be achieved by any logical rewriting of the condition. So, in this case, it's 9.

My intuition, flawed as it may be, is that the product of these numbers could be a good overall complexity figure. Or maybe, for aesthetics, the log (base 9) of that, giving

complexity(naked single) = 4.

tricky indeed, but its about time for some fun

right off there will be a tug of war between complexity of an empty grid (no clues, all candidates possible in all cells) vs. a grid with some clues

e.g., the average number of candidates/cell for |sudogen0.txt|=10,000, not counting clue cells, is 2.7

but say we ignore that

then there's the issue of bitmask representations that can lead to parallel operations (which may lead to operation weights)

e.g., with candidates represented as 9 bits, one wouldn't scan the grid 9 times, once for each candidate

one would scan once and check each cell for one candidate, and then determine the candidate value

so naked singles could take 81 candidate mask(r,c) ops, and then a check for 1 bit set

(the scan would have to differentiate between solved and unsolved cells too)

for r,c if unsolved(r,c) and !(mask(r,c)&(mask(r,c)-1)) then value(mask(r,c)) is a naked single

this looks like O(9^2) or strawman 2

so I guess I'm saying that a complexity measure should take into account that not all operations are equal

or maybe that the predicates chosen may have a non-trivial effect on how complexity is measured

e.g., measures limited to candidate(n,r,c) might end up doing loops inside out in a less efficient manner