2
$\begingroup$

Let us build a square array in the following manner, which I would like to call a modified sudoku:

1) Every row and column contains only one copy of a positive entry and there are exactly $t$ such entries, and it is less than $n$, the order of the array.

2) The zeros must repeat a fixed number of times, equal to $n-\text{number of distinct positive entries}=n-t$(the entries left blank without positive entries is filled by zeros).

3) Every row should have a distinct vector from each of its corresponding column vectors to positive entries.

4) The positive entries are from a set of given positive integers which is atmost the order of the array, i.e, the vectors((t tuples of positive entries) are chosen from a set of an $t+1$ positive entries where $t+1$ is atmost the order of array $n$.

What could be a probable algorithm to build such an array? One probable combination satisfying the above rules for order of array$=4$, and cardinality of the set of positive integers is $4$: $$\begin{pmatrix}1&2&3&0\\4&3&0&1\\2&0&4&3\\0&4&1&2\end{pmatrix}$$

Another example involving the order of array $=6$ and number of positive integer options $=4$, i.e length of tuple of positive entries $=3$ is: \begin{pmatrix}1&2&3&0&0&0\\4&3&0&0&0&1\\2&0&0&0&4&3\\0&0&0&4&3&2\\0&0&4&2&1&0\\0&4&1&3&0&0\end{pmatrix}

Also, a very important question is, whether such a n array can be built for every $n$ and $t$? Or, are there any constraints on $n,t$? I find that barring the case of $t=2$, other cases are possible, by combinatorial arguments, since we need to choose at most $t=1$ distinct vectors, which is possible as we are choosing the $t$ positive entries from $t+1$ entries. Any hints? Thanks beforehand.

$\endgroup$
  • $\begingroup$ The question seems to contradict itself on a number of points. The meaning of $t$ seems to vary: sometimes it seems to be the number of positive entries in each row, at other times the number of distinct positive entries in the entire array. Point 1 says (AIUI) that there is at least one zero in each row, but point 2 seems to fix an exact number of zeroes in each row. I have no idea what point 3 means. $\endgroup$ – Peter Taylor Feb 6 at 12:58
  • $\begingroup$ @PeterTaylor edited the post. see now if it is meaningful $\endgroup$ – vidyarthi Feb 6 at 13:12
  • $\begingroup$ I still have no idea what point 3 means. And point 4 still seems self-contradictory: I would interpret the part before "i.e." as saying that the positive entries cannot exceed $n$. $\endgroup$ – Peter Taylor Feb 6 at 13:36
  • 1
    $\begingroup$ Okay, let me clarify the rules for everyone: $\tag*{}$ 1. You must fill an $n\times n$ matrix with non-negative integers between $0$ and $t+1$, inclusive. $\tag*{}$ 2. No positive number may repeat in any row or column. $\tag*{}$ 3. There must be exactly $t$ positive numbers in each row and column, so each row and column is missing one positive number. $\tag*{}$ 4. If a row and column intersect at a positive number, then the missing numbers of that row and column must be different. $\endgroup$ – Mike Earnest Feb 6 at 18:51
  • $\begingroup$ @MikeEarnest thanks. That is what I meant! $\endgroup$ – vidyarthi Feb 7 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.