Count number of ways to place integers such that sum of 2x2 sub grid equals to n

88 Views Asked by At

You are given a kxk grid. You can place an integer m (a ≤ m ≤ b) in each cell. How many ways are there to place integers in the cells such that the sum of each 2x2 subgrid is n ?

For example These are the cases for k=3, a=1, b=2 and n=5.

2 1 2
1 1 1
2 1 2

or

2 1 2
1 1 1
1 2 1

or

2 1 1
1 1 2
2 1 1

or

1 2 1
1 1 1
2 1 2

or

1 2 1
1 1 1
1 2 1

or

1 1 2 
2 1 1
1 1 2

or

1 1 1
2 1 2
1 1 1

or

1 1 1
1 2 1
1 1 1

Hence answer for this case would be 8 ways.

My approach: is to solve the problem in for a linear list of k elements with moving window of size 2. and then for each possible valid pairs find all ordered partitions,