A
The Sudoku game admits a broad generalization as follows : let $r$ be an integer $\geq 2$
and let $X$ be a finite set, and ${\cal X}$ be a collection of $r$-subsets of $X$
(i.e, a $r$-uniform hypergraph on $X$). We call any mapping $X \to \lbrace 1,2, \ldots ,r\rbrace$ a coloring of $X$.
Then, the Sudoku-like problem associated to any partial colouring $g$ of $X$ (i.e. $g$ is
a mapping from a subset of $X$ to $\lbrace 1,2, \ldots ,r$) is to extend $g$ to a colouring $f$
such that $f$ restricts to a bijection onto $\lbrace 1,2, \ldots ,r\rbrace$
(a "rainbow coloring") on each $X\in {\cal X}$. To avoid trivialties, we always assume
that $X$ is not fully colored from the start, i.e. that $g$ is not defined on the whole of $X$.
We say that a Sudoku-like problem is perfect if it admits a unique solution, and reducible
if there is a non-backtracking rule that allows one to deduce the color
of an initially uncolored vertex $x\in X$ (formally this means
that $g$ is not defined at $x$ and that there is a color $c\in \lbrace 1,2, \ldots ,r$ such that either (1) for any color $c' \neq c$ there is a $Y\in {\cal X}$ containing $x$ such that $c'\in g(Y)$ or (2) for any vertex $x' \neq x$ there is a $Y\in {\cal X}$ containing $x'$ such that $c\in g(Y)$).
Perfect irreducible Sudoku-like problems do exist (the ordinary Sudoku problem in the end of David Eppstein's arXiv paper http://arxiv.org/abs/cs/0507053v1 is one such). It is natural then to look for "simpler" perfect irreducible Sudoku-like problems,
i.e. with the smallest possible value for $r$, and with as few hypergarph edges as possible. It is easy to see that we must have $r>2$. Are there examples with $r=3$ ?
Best Answer
I have a hard time interpreting "simple" in this context. "Simple" might be a fully colored object (so there is no work to do), or an object with few r-subsets present. Let me suggest a related but possibly alternative route.
Given an underlying set X and a collection of r-subsets of X all of which are to be rainbow colored, we call a subset U of X universal iff [for any (unique) allowed coloring of X, there is a unique induced coloring on U and vice versa] . U is a minimal universal set if no proper subset stirctly contained in U is universal. Simple here is again ambiguous: X may be a simple universal set, or X - {x} for any singleton set {x}. Or it may be those U which are minimal universal. I prefer to look at the latter out of mathematical interest.
Some unverified results of mine are minimal universal sets of size 5 for the 4-color, 16-square sudoku, and 48 for the popular 81-square version. It strikes me that projective planes and certain other combinatorial designs are also good candidates for the study of your generalized Sudoku problems.
Gerhard "Ask Me About System Design" Paseman, 2011.01.04