# 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

## 1 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

-
@Gerhard : I agree my use of the word "simple" was unfortunate. I'll edit the OP accordingly – Ewan Delanoy Jan 4 '11 at 18:00
Finite Geometries are "Sudoku spoilers": they have too many sets to rainbow color. Short proof sketch: color a point. If a line is supposed to be rainbow colored, then no other point on that line gets the same color. But every two distinct points determine a line. So one needs as many colors as points. Gerhard "It's Amazing How Thinking Helps" Paseman, 2011.01.04 – Gerhard Paseman Jan 4 '11 at 22:05