Author 
Message 
JeeBee science forum beginner
Joined: 18 Dec 2005
Posts: 9

Posted: Wed Dec 21, 2005 9:22 am Post subject:
number of grid network combinations



Suppose I have a MxN grid network,
(MxN nodes, (M1)(N1) boxes (cells),
2M(N1) edges).
But cells surrounded by three edges are not allowed (I call these invalid
positions).
Example: (the grid does not have to be connected)
++ ++
  
+ +++
If the number of edges e = 2M(N1), then a simple upperbound
on the number of grid networks is 2^e.
I already found that the number of valid 2xn positions is
p_n + q_n, defined as:
p_n = (4 3)^n * 7
q_n (3 2) 5
(2x2 matrix to the nth power multiplied by vector (7 5)).
 Can somebody generalize this equation to MxN networks?
 Can somebody specify a function that maps the numbers
{0,1,2,...,p} exactly to all valid positions?
(where p is the total number of valid positions).
The former I think is very well possible, though I'm a bit stuck there.
The latter might be very difficult.
Maybe it can be done in a different way, starting like this:
There are 12 valid 2x2 boxes:
2^4  4 invalid boxes = 12. The 4 invalid boxes are:
++ ++ + + ++
     
+ + ++ ++ ++
For two boxes AB, there are about half of 12^2 boxes, because they
share one edge (using the above function I know the exact answer is
74, indeed about half of 12^2).
+ + +
A B
+ + +
Then perhaps add a third box C, and (later?) fourth box D
+ + +
A B
+ + +
C D
+ + +
Maybe it is possible to construct a difference equation like I did for
this case?
Any comments are very welcome,
JeeBee. 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Thu Dec 22, 2005 6:30 am Post subject:
Re: number of grid network combinations



JeeBee wrote:
Quote:  Suppose I have a MxN grid network,
(MxN nodes, (M1)(N1) boxes (cells),
2M(N1) edges).
But cells surrounded by three edges are not allowed (I call these invalid
positions).

I assume you can have two or one or no edges around a cell ...
Quote:  Example: (the grid does not have to be connected)
++ ++
  
+ +++
If the number of edges e = 2M(N1), then a simple upperbound
on the number of grid networks is 2^e.
I already found that the number of valid 2xn positions is
p_n + q_n, defined as:
p_n = (4 3)^n * 7
q_n (3 2) 5
(2x2 matrix to the nth power multiplied by vector (7 5)).

You can probably also get this by setting up and solving a recurrance.
Quote:   Can somebody generalize this equation to MxN networks?

I mention a possible approach below. Difficult but not impossible.
Quote:   Can somebody specify a function that maps the numbers
{0,1,2,...,p} exactly to all valid positions?
(where p is the total number of valid positions).

That would be interesting. You could think of mapping p to a binary
string of length 4mn, where a 1 means there's a certain edge present,
next to a certain square, and a 0 means otherwise. The hard part would
be making sure that the network is consistent; i.e., the edge between
two neighboring squares is either there for both squares or absent for
both squares. I'll have to think about the map from p to the binary
strings for a while.
Your example above (of a bad network) 
Quote:  ++ ++
  
+ +++

 could be coded as 1111 1111 1011, where each block of 4 refers to
the corresponding square, and whether the edges are present is
determined by the block of 4. The edges, in order, are top, right,
bottom, left.
You can tell this is a bad network, because one of the blocks (the last
one) has 3 1's in it. The hard part is maintaining "consistency"; for
instance, there is no network for the binary string
1111 1110 1111.
Quote:  The former I think is very well possible, though I'm a bit stuck there.
The latter might be very difficult.

The second might be easier (for the 2xn case) than the first (for the
mxn case).
Quote:  Maybe it can be done in a different way, starting like this:
There are 12 valid 2x2 boxes:
2^4  4 invalid boxes = 12. The 4 invalid boxes are:
++ ++ + + ++
     
+ + ++ ++ ++
For two boxes AB, there are about half of 12^2 boxes, because they
share one edge (using the above function I know the exact answer is
74, indeed about half of 12^2).
+ + +
A B
+ + +
Then perhaps add a third box C, and (later?) fourth box D
+ + +
A B
+ + +
C D
+ + +
Maybe it is possible to construct a difference equation like I did for
this case?

You might want to try using InclusionExclusion, where you let A(m,n)
be the set of all networks where the (m,n) cell has exactly 3 edges
around it. That will get messy, but you can truncate the formula and
get a lower or upper bound. (Bonferroni's Inequalities)
The IE formula is at
http://mathworld.wolfram.com/InclusionExclusionPrinciple.html (You'd
be using formula (3).)
A(m,n) = 2^(e4) * 4, since there are 4 edges around the (m,n) cell,
and you're choosing the one which is not in the network. (We're
counting "bad guys" here.) Then there are 2^(e4) ways to choose
whether each of the other edges is in the network or not; these edges
don't affect whether the network is in A(m,n).
Thus the number of "bad guys" is at most (mn) * 2^(e4) * 4, so the
number of good networks is at least
2^e  m n 2^(e2). (I incorporated the 4 into the 2^*.)
Now if you can count the number of networks where the (m,n) and (p,q)
cells have exactly 3 edges around them, you can use the next term of
the IE formula to get a lower bound on the number of bad networks. This
has to be broken into cases, whether (m,n) is adjacent to (p,q) or not,
and whether at least one of these squares is in a corner or along an
edge.
It's messy, but not too bad. I wouldn't want to take the next step,
though.
 Christopher Heckman 

Back to top 


JeeBee science forum beginner
Joined: 18 Dec 2005
Posts: 9

Posted: Thu Dec 22, 2005 10:19 am Post subject:
Re: number of grid network combinations



Thanks Christopher!
Quote:  I assume you can have two or one or no edges around a cell ...

Sorry if I wasn't really clear here. I meant one or two or four,
but not three.
I am talking about the game dotsandboxes. If there are exactly three
moves around a box, the value does not need to be stored in the database,
because it can be looked up from several other positions quickly
(by either taking all boxes or leaving one or two doublecrosses).
(later I will also add rotation/mirrorring and the fact that the outer
two corner moves (for all four corners) are exactly equal to each other).
Quote:  p_n = (4 3)^n * 7
q_n (3 2) 5
(2x2 matrix to the nth power multiplied by vector (7 5)).
You can probably also get this by setting up and solving a recurrance.

I did, and this was the solution of those recurrent equations
p_n = 4 * p_{n1} + 3 * q_{n1}
q_n = 3 * p_{n1} + 2 * q_{n1} (if i'm not mistaking...)
with p_2=7, q_2=5
Quote:   Can somebody specify a function that maps the numbers
{0,1,2,...,p} exactly to all valid positions? (where p is the total
number of valid positions).

The above function is needed to compute the database index given a
position. That is why I don't want any numbers skipped, because that would
increase the size of my database.
Quote:  Your example above (of a bad network) 

So this network is actually a good one (one I do want in the database).
It's value should be 2, because the player to move will lose the two
remaining boxes.
Quote:  ++ ++
  
+ +++
You might want to try using InclusionExclusion, where you let A(m,n) be
the set of all networks where the (m,n) cell has exactly 3 edges around
it. That will get messy, but you can truncate the formula and get a lower
or upper bound. (Bonferroni's Inequalities)
The IE formula is at
http://mathworld.wolfram.com/InclusionExclusionPrinciple.html (You'd be
using formula (3).)

Thank you for this!
JeeBee. 

Back to top 


Google


Back to top 



The time now is Thu Sep 20, 2018 2:09 pm  All times are GMT

