One case where a sudoku arrangement is possible is when $G$ has a subgroup $H$ of order $n$. Let $Ha_1, Ha_2, \ldots Ha_n$ be the right cosets of $H$ and let $T_1, T_2, \ldots, T_n$ be a partition of $G$ into complete sets of left coset representatives. That is, each $T_i$ contains exactly one element from each left coset of $H$ and $T_i \cap T_j = \emptyset$ for $i \neq j$.
Order the columns by listing every element of $Ha_1$ first, then every element of $Ha_2$ and so on until $Ha_n$. Similarly order the rows by listing each element of $T_1$ first, then $T_2$ and so on until $T_n$. Then each $n \times n$ block is contains elements of a $Ha_i$ in the columns and elements of some $T_j$ in the rows. It turns out that this arrangement gives us a sudoku table.
We should show that every element of $G$ occurs exactly once in the block corresponding to $Ha_i$ and $T_j$. That is, we want to show that $T_jHa_i = G$, and this follows from the fact that there are no repetitions in the block. Suppose that $s_k, s_{k_0} \in T_j$ and $h, h_0 \in H$. If $s_kha_i = s_{k_0}h_0a_i$, then $s_kH = s_{k_0}H$ so $s_k = s_{k_0}$ since $T_j$ contains exactly one representative for each left coset. Thus $h = h_0$ as well.
I found the idea for the construction here, where a bit more general problem is considered. If $|G| = ab$ and $[G:H] = a$, then the same construction as in this answer gives you a sudoku table with blocks of size $a \times b$.
Basically this is about bipartite graphs: graphs where the vertex set is split into two parts that I will call type $X$ vertices and type $Y$ vertices, and where all edges have one end of type $X$ and another of type $Y$. These graphs represent a relation between elements of type $X$ and $Y$, the relation holding between $x$ and $y$ if there is an edge between $x$ and $y$. In your example type $X$ elements would be row indices and type $Y$ elements would be column indices (so a number that is both a row index and a column index gives rise both to a type $X$ vertex and an unrelated type $Y$ vertex), and the edges of the graph are between pairs $(x,y)$ where the matrix has a nonzero entry in position $(x,y)$. Permuting rows respectively columns now just means renumbering the type $X$ respectively type $Y$ vertices, so you can think of these sets as being unlabelled, which helps you abstract away from the order in which rows and columns are initially given.
Now what you want amounts to partitioning the whole graph into chunks such that there are no edges between different chunks (and moreover you want each chunk to have specified numbers of type $X$ and type $Y$ vertices). The finest partitioning with this property is obtained by computing the connected components of you bipartite graph. There is a straightforward and efficient algorithm to compute connected components. Even for sparse graphs, it is quite possible that there is only one connected component, in which case you are out of luck. Supposing however that there are many connected components, then you next task is to group together connected components into chunks so that the number of type $X$ and type $Y$ vertices matches your specification for each chunk. This is a kind of bin packing problem, but with an extra twist that sizes of items to be packed are pairs of numbers rather than single numbers (namely the numbers of type $X$ and type $Y$ vertices), which sizes are added together as $2$-component vectors.
This does not look as an easy problem, neither with respect to it being likely that there is a solution at all, nor with respect to allowing efficient algorithms for solving the general solvable case. I would personally be somewhat demotivated to even spend much effort on this problem.
Best Answer
Not a strong answer, but probably worth writing everything. Any sudoku with less than 17 numbers does not have a unique solution. So, randomly guessing 16 numbers will likely have at least one solution, and could be found by lots of trial and error. Computers could make this easier.
Mind you, even with 16 numbers, no solution is guaranteed, but there are multiple "paths" to check.
A sudoku with 17 or more numbers MAY have a unique solution, or MAY not have a solution. It also MAY have multiple solutions. If you want to be sure you have multiple paths to take, don't work up to 17.