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$ ?
