## Simplest examples of unique-solution and unsolvable-without-backtracking Sudoku-like problems

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

-
 Did you check with David's answer mathoverflow.net/questions/27361/… ? – Wadim Zudilin Jan 4 2011 at 9:50 @Wadim : Yes, of course. AFAIK, all the sudoku-like problems studied are ordinary sudoku problems or more complicated variants : in my notation, the value of $r$ is $9$ or higher. I, on the contrary, am looking for simpler examples, say $r=3$. – Ewan Delanoy Jan 4 2011 at 10:24 @Ewan, thank you for clarification. – Wadim Zudilin Jan 4 2011 at 10:26 Fano plane? Gerhard "Ask Me About System Design" Paseman, 2011.01.04 – Gerhard Paseman Jan 4 2011 at 18:13 Except there is no nice 3-coloring. Perhaps some sub-configuration of the Fano plane? Gerhard "Ask Me About System Design" Paseman, 2011.01.04 – Gerhard Paseman Jan 4 2011 at 18:19

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.