# 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 '11 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 '11 at 10:24
• @Ewan, thank you for clarification. – Wadim Zudilin Jan 4 '11 at 10:26
• Fano plane? Gerhard "Ask Me About System Design" Paseman, 2011.01.04 – Gerhard Paseman Jan 4 '11 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 '11 at 18:19