<p>This is not an answer, just a long comment.</p>

<p>First, you say that you are unsure if this problem in in #P.  It depends on how you define your input, which can either be the $n$-by-$n$ graph or just $n$.  I would say that it is more natural to take the graph as input, in which case, an NP machine can guess $n^2$ bits (which is a polynomial, linear even, in the size of the input) and can check in polynomial time, linear even, if all your constraints are satisfied.  If the input is just $n$, then $n^2$ is exponentially larger than the input size $\log(n)$, so we can't say your problem is in #P, but it is in the counting class related to NEXP (in the same way that #P is the counting class related to NP).</p>

<p>Second, this input issue also affects what types of hardness we can expect to prove. If the input is the grid graph, then you have at most one input for each input length.  Such problems are said to be sparse (which means there is at most a polynomial number of inputs for each input length) and are not expected to be hard by (a generalization of) <a href="http://en.wikipedia.org/wiki/Sparse_language" rel="nofollow">Mahaney's theorem</a>.  But if you pick $n$ to be your input so that set of instances is no longer sparse, then your output is exponentially larger than your input.  What I am trying to say here is that the typical notions of hardness don't apply very well to your problem.</p>

<p>Third, I can say something about the possibility of this problem being tractable.  My research is in counting problems defined by local constraints, which we formally define as Holant problems. The difference between Holant problems and your problem is that we don't put such tight restrictions on the inputs graphs.  We allow restrictions like planar, bipartie, and prescribed degree (such at $k$-regular or at most degree $k$), none of which defines a sparse set of graphs.</p>

<p>The best I can do to cast your problem as a Holant problem is as follows.  For omitted definitions, see the preliminary section in a <a href="http://arxiv.org/abs/1204.6445" rel="nofollow">recent paper of mine</a>.  In the Holant framework, edges take values from a finite domain and vertices impose constraints on the values assigned to its incident edges.  To (partially) model your problem, we consider the Boolean domain $\{0,1\}$.  As a first attempt to capture your problem, think of an $n$-by-$n$ grid graph as the input.  To associate a bit with each vertex $v$, we add an edge $e_v$ incident $v$ and to a new vertex $u_v$.  To communicate this bit value to the neighboring internal vertices, we duplicate all the edges between internal vertices (i.e. vertices not on the boundary) in the original $n$-by-$n$ grid graph.</p>

<p>The vertices on the boundary have no constraint, which is represented by the signature $[1,1]$ tensored with itself twice for the corner vertices and three times for the vertices on the sides.  The remaining interior vertices pick an edge in each direction and require these four edges and the other edge added above (with its associated bit) to take the same value. Then we impose your constraint by comparing this value with the four values assigned to the remaining four edges (one edge in each direction).  Of course, between each pair of internal vertices, they have to agree on which edge each uses to communicate their bit value.  One way to decide this, in a planar embedding of this graph, is that each vertex should use the edge that is encountered first in a clockwise traversal of its incident edges.</p>

<p>The paper of mine that I linked to above is a dichotomy for Holant problems that use symmetric signatures (which means that the output is invariant under any permutation of the input).  Unfortunately, the constraint that I used to capture your problem at internal vertices is not symmetric and it is still an open problem to prove the generalization of that dichotomy for general (i.e. not necessarily symmetric) signatures.  Worse yet, we currently do not even know how to decide if this Holant problem is easy or hard according to what we conjecture the dichotomy to be.  Furthermore, we can impose restrictions on the input graphs like being planar and bipartite that are satisfied by your grid graph, the hope being that this Holant problem may become tractable under these restrictions. However, a dichotomy for such Holant problems is years, maybe even a decade away.</p>

<p>In closing, let me emphasize that this Holant problem that I have described is "more difficult" than your problem (when the input is the grid graph).  The input to this (planar, bipartite) Holant problem can only use the complicated arity 9 constraint (that was assigned to the internal vertices) and the (unconstraining) unary constraint $[1,1]$ but the graph is not restricted to grid graphs. Formally speaking, your problem (when the input is the grid graph) reduces to this Holant problem. So, if this Holant problem were easy, then your problem (when the input is the grid graph) is easy too, but if this Holant problem is hard, then I want to say that your problem is hard, but I don't know how to do so (as I discussed above).</p>

CC BY-SA 3.0
2012-09-30T06:29:39.333Z
Thanks Tyson. I am going through your paper to understand it in more details.
Rajeev Kumar
CC BY-SA 3.0
2012-09-27T15:44:04.727Z
2012-09-27T15:49:23.567Z
2012-09-27T15:49:23.567Z
Tyson Williams
<p>If I understand what you're asking, this is a very structured problem.  Have you tried just counting the solutions?</p>

<p>For example, consider the odd case, n = 2m + 1.  Then it looks to me that you can fill in the grid in a checkerboard pattern without worry (the asterisks below): </p>

<pre><code>* * * * *
* ? * ? *
* * ? * *
* ? * ? *
* * * * *
</code></pre>

<p>Further, once you've done so, you either have a free choice of what to make the question marks (7/8s of the time) or are forced to make a particular choice (1/8 of the time, when surrounded by all the same bit).  Thus, the number of solutions should be:</p>

<p>$$ 
2^{2^n} (\frac{7}{8})^{m^2 + (m-1)^2}
$$</p>

<p>I think you can make the probabilistic reasoning exact with a little care.  And of course, this leaves the even case, but I wouldn't be surprised if it also admits a closed form solution.  </p>

CC BY-SA 3.0
2012-10-04T02:26:19.647Z
I have the following questions:-  
1. Shouldn't $2^{2^n}$ be $2^{n^2}$ in the expression?
2. Also, the values assigned to question marks can affect the validity of any bit marked with $*$. Since, $*$ are also surrounded by $?$, wouldn't the choice of $?$ render some $*$ bit invalid? So, the expression you wrote would be an upper bound..  
3. I am not sure if exact counting follows directly from the probabilistic argument, can you please elaborate if you have any ideas in that regard.
Rajeev Kumar
CC BY-SA 3.0
2012-10-04T13:04:29.403Z
Yes, you're right on all counts.  The 2nd could possibly be fixed, but your question 3 is fatal - I had hoped the choices were independent but they are not and that cannot be fixed easily.
Matt M
CC BY-SA 3.0
2012-10-03T19:46:49.560Z
2012-10-03T22:10:35.740Z
2012-10-03T22:10:35.740Z
Matt M
<p>I have a n×n grid of binary bits, where n is a natural number. I want to count the number of bit patterns which have the following property: out of the four (North, West, South and East) adjacent bits of any bit, at most 3 can have a value different from it. Alternatively, if C is the center bit, and N, W, E and S are its four adjacent neighbours, then
              (C xor W)∧(C xor S)∧(C xor E)∧(C xor N)=0  </p>

<pre><code>              N
            W-C-E
              S
</code></pre>

<p>This should hold for every bit in any valid pattern. I am not sure if this is a #P problem. The counting for 1D version of this problem (a 1×n or n×1 grid), where every bit has only two adjacent neighbours, and at most one can be different from the bit, can be done in polynomial time. I am not sure if the same is true for this problem or not..</p>

<p><strong>Inductive Proof for the case of a $n \times 1$ grid:</strong>  </p>

<p>Counting for the 1D case can be done using the following inductive argument:  </p>

<p>For an $n \times 1$ grid, let $b_{n}b_{n-1}...b_{1}b_{0}$ be a unique bit pattern. For this pattern to be valid, for any $b_{i}$, $i \in [1, n-1]$, atmost one of $b_{i-1}$ or $b_{i+1}$ can be equal to $\neg b_{i}$.<br>
We now define the following quantities for a $n \times 1$ grid:<br>
• $T(n)$ is the total number of distinct $n$ bit patterns<br>
• $T_{v}(n)$ is the total number of valid patterns<br>
• $T_{iv}(n)$ is the total number of invalid patterns<br>
• $T_{vs}(n)$ is the total number of valid patterns which satisfy the property $b_{n} = b_{n-1}$<br>
• $T_{vd}(n)$ is the total number of valid patterns which satisfy the property $b_{n} \neq b_{n-1}$  </p>

<p>Then, for $n \geq 3$:<br>
$T_{v}(n) = 2 \times T_{vs}(n-1) + T_{vd}(n-1)$<br>
$T_{vs}(n) = T_{vs}(n-1) + T_{vd}(n-1)$<br>
$T_{vd}(n) = T_{vs}(n-1)$  </p>

<p>Also, by the definition of $T_{v}(n)$ and $T_{vs}(n)$, we have:<br>
$T_{v}(n)=T_{vs}(n)+T_{vd}(n)$<br>
$T_{vs}(n)=T_{v}(n-1)$  (Only one pattern of the type $T_{vs}$ for a $1 \times n$ grid can be created from a $T_{v}$ pattern for a $1 \times n-1$ grid)</p>

<p>Now,<br>
$T_{v}(n) = 2 \times T_{vs}(n-1) + T_{vd}(n-1)$<br>
$T_{v}(n) = T_{vs}(n-1) + T_{vs}(n-1) + T_{vd}(n-1)$<br>
$T_{v}(n) = (T_{vs}(n-1) + T_{vd}(n-1)) + T_{vs}(n-1)$<br>
$T_{v}(n) = T_{v}(n-1) + T_{v}(n-2)$  </p>

<p>By using $n=2$ and $n=1$ as the base cases, we can compute the number of valid patterns for a $n \times 1$ grid for any $n$. This inductive method breaks for a $n \times n$ grid, because it would require creating exponential intermediate variables to do an exact counting.</p>

<p>Thanks,
Rajeev</p>

CC BY-SA 3.0
2012-09-23T03:37:22.533Z
Next time, please use spell checker.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-23T03:40:31.760Z
What happens at the borders?
Realz Slaw
CC BY-SA 3.0
2012-09-23T04:17:28.783Z
Apologies for not using the spell checker. I am using this forum for the first time.
Rajeev Kumar
CC BY-SA 3.0
2012-09-23T04:20:51.437Z
As any bit on the borders will have atmost 3 adjacent neighbouring bits, they satisfy this constraint for any pattern.
Rajeev Kumar
CC BY-SA 3.0
2012-09-23T07:01:36.513Z
What is the question?
Dave Clarke
CC BY-SA 3.0
2012-09-23T09:13:35.393Z
I can see two (different) problems, and I am not sure the one you are interested in. Let us say that a bit $b$ is *valid* if it is surrounded by at most three bits of value $\neg b$, and that an $(n\times n)$ grid is *valid* if each of its bits is valid. Here are two problems we can define: 1. You are given an $(n\times n)$ grid of bits, and you want to check whether it is valid (or alternatively, to count its number of valid bits). 2. You are given $n$, and you want to count the number of *valid* $(n\times n)$ grids. Which problem are you interested in? Another one maybe?
Bruno
CC BY-SA 3.0
2012-09-23T12:26:04.940Z
What is the poly time algorithm for the 1D case?
Tyson Williams
CC BY-SA 3.0
2012-09-23T13:57:58.320Z
@Bruno: I would assume interpretation 2.  Isn’t interpretation 1 a little bit silly?  I think that in the question, “grid” means a grid of blank cells, and “bit pattern” means a grid of filled cells.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-23T16:19:18.780Z
@TsuyoshiIto: You're right...
Bruno
CC BY-SA 3.0
2012-09-23T22:58:50.083Z
@Bruno: I am interested in the problem specified by your interpretation 2. As Tsuyoshi mentioned, a "bit pattern" means a grid of filled cells.
Rajeev Kumar
CC BY-SA 3.0
2012-09-23T23:37:40.753Z
If you have the values in the case of n×n for small n, you might want to try [OEIS](http://oeis.org/).
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-24T00:22:47.590Z
@TysonWilliams: I have added the method for the 1D case in the description of the question. I could not add the whole thing in one comment in the reply.
Rajeev Kumar
CC BY-SA 3.0
2012-09-24T12:49:55.143Z
Are you sure your recurrence is correct?. I get $T_v(n) = 2 T_v(n-2) + 2 T_v(n-3)$.
Tyson Williams
CC BY-SA 3.0
2012-09-24T23:09:46.493Z
@TysonWilliams: Sorry, I skipped a few steps. I have edited it to make it clearer. I am interested in the following:- If instead of counting the number of satisfying patterns, we consider the problem of determining whether a satisfying assignment exists for this constraint, then, both the 1D and 2D cases are poly-time solvable as per Schafer's dichotomy theorem. However, for the 1D case, couting the number of satisfying assignments is also polytime solvable. I can not understand why counting for the 2D case is not polytime solvable, despite the problem structure being similar in both cases.
Rajeev Kumar
CC BY-SA 3.0
2012-09-25T03:07:03.050Z
Your recursion checks out for $n=3,4$. Why is $T_{v}(n) = 2 \times T_{vs}(n-1) + T_{vd}(n-1)$ true?
Tyson Williams
CC BY-SA 3.0
2012-09-25T05:28:47.150Z
That is because, for every $T_{vs}(n-1)$, since the value of $n-1^{th}$ bit is same as the value of $n-2^{th}$ bit, we can choose the $n^{th}$ bit to be either 0 or 1, and the resulting pattern would still be valid. However, for a $T_{vd}(n-1)$ type of pattern, value of $n-1^{th}$ bit is the opposite of the value of $n-2^{th}$ bit, and we have to set the value of $n^{th}$ bit to be the same as the $n-1^{th}$ bit. Otherwise, the constraint will be violated at $n-1^{th}$ bit, rendering the pattern invalid.
Rajeev Kumar
CC BY-SA 3.0
2012-09-25T12:43:02.427Z
Ok, I understand now and agree with your conclusion.
Tyson Williams
CC BY-SA 3.0
2012-09-27T05:41:36.873Z
@TysonWilliams, Do you have any suggestions on analyzing this problem?
Rajeev Kumar
CC BY-SA 3.0
2012-09-27T15:44:55.803Z
Yes. My thoughts are too long for a comment, so I put them in an answer.
Tyson Williams
CC BY-SA 3.0
2012-09-27T15:57:20.437Z
For the 1D case, there are [some partial OEIS matches](http://oeis.org/search?q=2%2C4%2C6%2C10%2C16%2C26%2C42%2C68%2C110&sort=&language=english&go=Search) (meaning that these sequences contain your sequence as a sub-sequence) but no exact match.
Tyson Williams
<cc.complexity-theory><counting-complexity><application-of-theory>
Counting number of solutions to a specific SAT formula
Rajeev Kumar
# Counting number of solutions to a specific SAT formula

(Asked by: username_0 on 2012-09-23)

I have a n×n grid of binary bits, where n is a natural number. I want to count the number of bit patterns which have the following property: out of the four (North, West, South and East) adjacent bits of any bit, at most 3 can have a value different from it. Alternatively, if C is the center bit, and N, W, E and S are its four adjacent neighbours, then
              (C xor W)∧(C xor S)∧(C xor E)∧(C xor N)=0  
              N
            W-C-E
              S

This should hold for every bit in any valid pattern. I am not sure if this is a #P problem. The counting for 1D version of this problem (a 1×n or n×1 grid), where every bit has only two adjacent neighbours, and at most one can be different from the bit, can be done in polynomial time. I am not sure if the same is true for this problem or not..
Inductive Proof for the case of a $n \times 1$ grid: 
Counting for the 1D case can be done using the following inductive argument:  
For an $n \times 1$ grid, let $b_{n}b_{n-1}...b_{1}b_{0}$ be a unique bit pattern. For this pattern to be valid, for any $b_{i}$, $i \in [1, n-1]$, atmost one of $b_{i-1}$ or $b_{i+1}$ can be equal to $\neg b_{i}$.
We now define the following quantities for a $n \times 1$ grid:
• $T(n)$ is the total number of distinct $n$ bit patterns
• $T_{v}(n)$ is the total number of valid patterns
• $T_{iv}(n)$ is the total number of invalid patterns
• $T_{vs}(n)$ is the total number of valid patterns which satisfy the property $b_{n} = b_{n-1}$
• $T_{vd}(n)$ is the total number of valid patterns which satisfy the property $b_{n} \neq b_{n-1}$  
Then, for $n \geq 3$:
$T_{v}(n) = 2 \times T_{vs}(n-1) + T_{vd}(n-1)$
$T_{vs}(n) = T_{vs}(n-1) + T_{vd}(n-1)$
$T_{vd}(n) = T_{vs}(n-1)$  
Also, by the definition of $T_{v}(n)$ and $T_{vs}(n)$, we have:
$T_{v}(n)=T_{vs}(n)+T_{vd}(n)$
$T_{vs}(n)=T_{v}(n-1)$  (Only one pattern of the type $T_{vs}$ for a $1 \times n$ grid can be created from a $T_{v}$ pattern for a $1 \times n-1$ grid)
Now,
$T_{v}(n) = 2 \times T_{vs}(n-1) + T_{vd}(n-1)$
$T_{v}(n) = T_{vs}(n-1) + T_{vs}(n-1) + T_{vd}(n-1)$
$T_{v}(n) = (T_{vs}(n-1) + T_{vd}(n-1)) + T_{vs}(n-1)$
$T_{v}(n) = T_{v}(n-1) + T_{v}(n-2)$  
By using $n=2$ and $n=1$ as the base cases, we can compute the number of valid patterns for a $n \times 1$ grid for any $n$. This inductive method breaks for a $n \times n$ grid, because it would require creating exponential intermediate variables to do an exact counting.
Thanks,
Rajeev

**Tags:** cc.complexity-theory, counting-complexity, application-of-theory
> **Comments:**
> **username_1**: Next time, please use spell checker.  
> **username_2**: What happens at the borders?  
> **username_0**: Apologies for not using the spell checker. I am using this forum for the first time.  
> **username_0**: As any bit on the borders will have atmost 3 adjacent neighbouring bits, they satisfy this constraint for any pattern.  
> **username_3**: What is the question?  
> **username_4**: I can see two (different) problems, and I am not sure the one you are interested in. Let us say that a bit $b$ is *valid* if it is surrounded by at most three bits of value $\neg b$, and that an $(n\times n)$ grid is *valid* if each of its bits is valid. Here are two problems we can define: 1. You are given an $(n\times n)$ grid of bits, and you want to check whether it is valid (or alternatively, to count its number of valid bits). 2. You are given $n$, and you want to count the number of *valid* $(n\times n)$ grids. Which problem are you interested in? Another one maybe?  
> **username_5**: What is the poly time algorithm for the 1D case?  
> **username_1**: @Bruno: I would assume interpretation 2.  Isn’t interpretation 1 a little bit silly?  I think that in the question, “grid” means a grid of blank cells, and “bit pattern” means a grid of filled cells.  
> **username_4**: @TsuyoshiIto: You're right...  
> **username_0**: @Bruno: I am interested in the problem specified by your interpretation 2. As Tsuyoshi mentioned, a "bit pattern" means a grid of filled cells.  
> **username_1**: If you have the values in the case of n×n for small n, you might want to try [OEIS](http://oeis.org/).  
> **username_0**: @TysonWilliams: I have added the method for the 1D case in the description of the question. I could not add the whole thing in one comment in the reply.  
> **username_5**: Are you sure your recurrence is correct?. I get $T_v(n) = 2 T_v(n-2) + 2 T_v(n-3)$.  
> **username_0**: @TysonWilliams: Sorry, I skipped a few steps. I have edited it to make it clearer. I am interested in the following:- If instead of counting the number of satisfying patterns, we consider the problem of determining whether a satisfying assignment exists for this constraint, then, both the 1D and 2D cases are poly-time solvable as per Schafer's dichotomy theorem. However, for the 1D case, couting the number of satisfying assignments is also polytime solvable. I can not understand why counting for the 2D case is not polytime solvable, despite the problem structure being similar in both cases.  
> **username_5**: Your recursion checks out for $n=3,4$. Why is $T_{v}(n) = 2 \times T_{vs}(n-1) + T_{vd}(n-1)$ true?  
> **username_0**: That is because, for every $T_{vs}(n-1)$, since the value of $n-1^{th}$ bit is same as the value of $n-2^{th}$ bit, we can choose the $n^{th}$ bit to be either 0 or 1, and the resulting pattern would still be valid. However, for a $T_{vd}(n-1)$ type of pattern, value of $n-1^{th}$ bit is the opposite of the value of $n-2^{th}$ bit, and we have to set the value of $n^{th}$ bit to be the same as the $n-1^{th}$ bit. Otherwise, the constraint will be violated at $n-1^{th}$ bit, rendering the pattern invalid.  
> **username_5**: Ok, I understand now and agree with your conclusion.  
> **username_0**: @TysonWilliams, Do you have any suggestions on analyzing this problem?  
> **username_5**: Yes. My thoughts are too long for a comment, so I put them in an answer.  
> **username_5**: For the 1D case, there are [some partial OEIS matches](http://oeis.org/search?q=2%2C4%2C6%2C10%2C16%2C26%2C42%2C68%2C110&sort=&language=english&go=Search) (meaning that these sequences contain your sequence as a sub-sequence) but no exact match.  

---

## 2 answers

### Answer by username_5 on 2012-09-27. Score: 4

This is not an answer, just a long comment.

First, you say that you are unsure if this problem in in #P. It depends on how you define your input, which can either be the $n$-by-$n$ graph or just $n$. I would say that it is more natural to take the graph as input, in which case, an NP machine can guess $n^2$ bits (which is a polynomial, linear even, in the size of the input) and can check in polynomial time, linear even, if all your constraints are satisfied. If the input is just $n$, then $n^2$ is exponentially larger than the input size $\log(n)$, so we can't say your problem is in #P, but it is in the counting class related to NEXP (in the same way that #P is the counting class related to NP).

Second, this input issue also affects what types of hardness we can expect to prove. If the input is the grid graph, then you have at most one input for each input length. Such problems are said to be sparse (which means there is at most a polynomial number of inputs for each input length) and are not expected to be hard by (a generalization of) [Mahaney's theorem](http://en.wikipedia.org/wiki/Sparse_language). But if you pick $n$ to be your input so that set of instances is no longer sparse, then your output is exponentially larger than your input. What I am trying to say here is that the typical notions of hardness don't apply very well to your problem.

Third, I can say something about the possibility of this problem being tractable. My research is in counting problems defined by local constraints, which we formally define as Holant problems. The difference between Holant problems and your problem is that we don't put such tight restrictions on the inputs graphs. We allow restrictions like planar, bipartie, and prescribed degree (such at $k$-regular or at most degree $k$), none of which defines a sparse set of graphs.

The best I can do to cast your problem as a Holant problem is as follows. For omitted definitions, see the preliminary section in a [recent paper of mine](http://arxiv.org/abs/1204.6445). In the Holant framework, edges take values from a finite domain and vertices impose constraints on the values assigned to its incident edges. To (partially) model your problem, we consider the Boolean domain $\{0,1\}$. As a first attempt to capture your problem, think of an $n$-by-$n$ grid graph as the input. To associate a bit with each vertex $v$, we add an edge $e\_v$ incident $v$ and to a new vertex $u\_v$. To communicate this bit value to the neighboring internal vertices, we duplicate all the edges between internal vertices (i.e. vertices not on the boundary) in the original $n$-by-$n$ grid graph.

The vertices on the boundary have no constraint, which is represented by the signature $[1,1]$ tensored with itself twice for the corner vertices and three times for the vertices on the sides. The remaining interior vertices pick an edge in each direction and require these four edges and the other edge added above (with its associated bit) to take the same value. Then we impose your constraint by comparing this value with the four values assigned to the remaining four edges (one edge in each direction). Of course, between each pair of internal vertices, they have to agree on which edge each uses to communicate their bit value. One way to decide this, in a planar embedding of this graph, is that each vertex should use the edge that is encountered first in a clockwise traversal of its incident edges.

The paper of mine that I linked to above is a dichotomy for Holant problems that use symmetric signatures (which means that the output is invariant under any permutation of the input). Unfortunately, the constraint that I used to capture your problem at internal vertices is not symmetric and it is still an open problem to prove the generalization of that dichotomy for general (i.e. not necessarily symmetric) signatures. Worse yet, we currently do not even know how to decide if this Holant problem is easy or hard according to what we conjecture the dichotomy to be. Furthermore, we can impose restrictions on the input graphs like being planar and bipartite that are satisfied by your grid graph, the hope being that this Holant problem may become tractable under these restrictions. However, a dichotomy for such Holant problems is years, maybe even a decade away.

In closing, let me emphasize that this Holant problem that I have described is "more difficult" than your problem (when the input is the grid graph). The input to this (planar, bipartite) Holant problem can only use the complicated arity 9 constraint (that was assigned to the internal vertices) and the (unconstraining) unary constraint $[1,1]$ but the graph is not restricted to grid graphs. Formally speaking, your problem (when the input is the grid graph) reduces to this Holant problem. So, if this Holant problem were easy, then your problem (when the input is the grid graph) is easy too, but if this Holant problem is hard, then I want to say that your problem is hard, but I don't know how to do so (as I discussed above).

> **Comments:**
> **username_0**: Thanks Tyson. I am going through your paper to understand it in more details.  

---

### Answer by username_6 on 2012-10-03. Score: 1

If I understand what you're asking, this is a very structured problem.  Have you tried just counting the solutions?
For example, consider the odd case, n = 2m + 1.  Then it looks to me that you can fill in the grid in a checkerboard pattern without worry (the asterisks below): 
* * * * *
* ? * ? *
* * ? * *
* ? * ? *
* * * * *

Further, once you've done so, you either have a free choice of what to make the question marks (7/8s of the time) or are forced to make a particular choice (1/8 of the time, when surrounded by all the same bit).  Thus, the number of solutions should be:
$$ 
2^{2^n} (\frac{7}{8})^{m^2 + (m-1)^2}
$$
I think you can make the probabilistic reasoning exact with a little care.  And of course, this leaves the even case, but I wouldn't be surprised if it also admits a closed form solution.

> **Comments:**
> **username_0**: I have the following questions:-   1. Shouldn't $2^{2^n}$ be $2^{n^2}$ in the expression? 2. Also, the values assigned to question marks can affect the validity of any bit marked with $*$. Since, $*$ are also surrounded by $?$, wouldn't the choice of $?$ render some $*$ bit invalid? So, the expression you wrote would be an upper bound..   3. I am not sure if exact counting follows directly from the probabilistic argument, can you please elaborate if you have any ideas in that regard.  
> **username_6**: Yes, you're right on all counts.  The 2nd could possibly be fixed, but your question 3 is fatal - I had hoped the choices were independent but they are not and that cannot be fixed easily.  

---

