How to find the number of ways in which the above $9$-by-$9$ grid can be filled using the digits $(1-9)$ (repetition is allowed) such that all of the following conditions are satisfied:
Any $3$-by-$3$ grid is not totally empty.
Any $3$-by-$3$ grid is not totally filled.
Any $3$-by-$3$ grid must not contain repeated digits.
Any row must not contain repeated digits.
Any column must not contain repeated digits.
There must not be any empty row.
There must not be any row which is totally filled.
There must not be any empty column.
There must not be any column which is totally filled.
Here are examples of INVALID cases (according to the above conditions, respectively):
- An empty $3$-by-$3$ grid:
- A totally filled $3$-by-$3$ grid:
- Repeated digits in a $3$-by-$3$ grid:
- Repeated digits in a row:
- Repeated digits in a column:
- An empty row:
- A totally filled row:
- An empty column:
- A totally filled column:
Note that $C1,C2,C3,\dots,C9,R1,R2,R3,\dots,R9$ are positioned/attached to the $9$-by-$9$ grid to indicate that a rotated or transposed $9$-by-$9$ grid is considered as a different way (i.e. a rotated or transposed $9$-by-$9$ grid must be counted). Here are three examples of different VALID cases:
First example:
Second example:
Third example:
I saw similar question in this forum (sudoku problems), but those questions are not exact to this one.
Your help would be really appreciated. THANKS!
We can improve the upper bound of the required number $N$ of ways from my comment as follows.
Consider the first column of the filled grid. Assume it has $k$ zeroes. Then $1\le k\le 8$ and there are ${9\choose k}$ ways to place them in the column and $\tfrac {9!}{k!}$ ways to fill the remaining $9-k$ cells with positive numbers.
Now consider the possibilities to fill a row.
Assume that a row starts from a zero. It there are $m$ remaining zeroes in the row then $0\le m\le 7$ and there are ${8\choose m}$ ways to place them in the row and $\tfrac {9!}{(m+1)!}$ ways to fill the remaining $8-m$ cells with positive numbers. This give us in total $N_0=\sum_{m=0}^7 {8\choose m}\tfrac {9!}{(m+1)!}=4596552$ possibilities to fill a row.
Assume that a row starts from a positive number. It there are $m$ zeroes in the row then $1\le m\le 8$ and there are ${8\choose m}$ ways to place them in the row and $\tfrac {8!}{m!}$ ways to fill the remaining $8-m$ cells with positive numbers. This give us in total $N_+=\sum_{m=1}^8 {8\choose m}\tfrac {8!}{m!}=1401409$ possibilities to fill a row.
In total, we have a bound
$N\le \sum_{k=1}^8 {9\choose k} \tfrac {9!}{k!} N_0^k N_+^{9-k}\approx 1.438\cdot 10^{64}$.
Again, this bound can be improved if we take into account that the rows are not independent but cannot contain a common positive number in the same column. But it seems this way leads to more complicted calculations and not a very big improvement.